\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{tikz}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\DeclareMathOperator{\Exp}{E}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\set}[1]{\{#1\}}
\newcommand{\real}{\mathbb{R}}
\newcommand{\nn}{\mathbb{N}}
\newcommand{\z}{\mathbb{Z}}
\newcommand{\complex}{\mathbb{C}}
\newcommand{\sd}{\,|\,}
\newcommand{\goesto}{\rightarrow}
\newcommand{\struct}[1]{\mathcal{#1}}
\newcommand{\wo}{\backslash}
\newcommand{\abs}[1]{\bigl\lvert #1\bigr\rvert}
\newcommand{\length}[1]{\left\lvert #1\right\rvert}
\begin{center}
\vskip 1cm{\LARGE\bf Restricted Weighted Integer Compositions \\
\vskip .1in and Extended Binomial Coefficients
}
\vskip 1cm
\large
Steffen Eger \\
School of Computer Science \\
Carnegie Mellon University \\
Pittsburgh, PA 15213 \\
USA\\
\href{mailto:seger@cs.cmu.edu}{\tt seger@cs.cmu.edu}\\
\end{center}
\vskip .2 in
\begin{abstract}
We prove a simple relationship between extended binomial coefficients ---
natural extensions of the well-known binomial coefficients --- and
weighted restricted integer compositions.
Moreover, we
give a very useful interpretation of extended binomial coefficients as
representing distributions of sums of independent
discrete random variables. We apply our results,
e.g., to determine the distribution
of the sum of $k$ logarithmically distributed random variables, and to
determining the distribution, specifying all moments, of the
random variable whose values are
part-products of random restricted integer compositions. Based on our
findings and using the central limit theorem, we also give
generalized Stirling formulae
for central
extended binomial coefficients. We enlarge the list of known properties
of extended binomial coefficients.
\end{abstract}
\section{Introduction}\label{sec:introduction}
An
\emph{integer composition} of a
nonnegative
integer $n$ with $k$ summands, or \emph{parts}, is a way of writing
$n$ as a sum of $k$
nonnegative integers, where the order of parts is significant. We
call the integer composition
\emph{$S$-restricted} if all parts lie within a subset $S$
of the nonnegative integers.
Compositions with (various types of) restrictions on part sizes have
recently been
studied in, e.g.,
\cite{chinn,chinn2,heubach,jaklic,sagan} and for
probabilistic results on such compositions see
\cite{hitczenko,bender2,bender3,bender4,malandro,schmutz,shapcott2}.
A classical result in combinatorics is
then
that
the number of $S$-restricted integer compositions of $n$ with $k$ parts
is given by the coefficient of $x^n$ of the
polynomial or power series (see, e.g., \cite{heubach})
\begin{align*}
\bigl(\sum_{s\in S}x^s\bigr)^k.
\end{align*}
These coefficients, in turn, which generalize the ordinary binomial
coefficients, and are usually called \emph{polynomial coefficients} or
\emph{extended binomial coefficients},
exhibit fascinating mathematical properties, closely resembling those
of binomial coefficients. Although they appeared explicitly as far
back as De Moivre's \emph{The Doctrine of Chances} \cite{moivre} in
1756, their systematic
study has apparently only recently
been investigated (cf.\ \cite{fahssi}).
In the present paper, we
give a complete characterization of extended binomial coefficients, over
commutative rings $\struct{R}$, in
terms of sums, over restricted integer compositions, of part-products
of integer compositions, where each part is
mapped, via a function $f$, to a value in the ring (Theorem
\ref{theorem:main}).
It is a straightforward exercise to show that
these sums,
when $f$ is integer-valued,
count
colored monotone lattice paths
or, simply, colored integer compositions (third proof of Theorem
\ref{theorem:main} and Remark \ref{remark:ccolor}). Colored integer
compositions, in turn, have recently been studied
(cf.\ \cite{agarwal:2000,guo:2012,narang:2006,narang:2008}), for example, in
the situation
when part $s\in S$ comes
in $s$ different colors (`\emph{$n$-colored compositions}') and,
simultaneously with, but independently of the present paper, when part
$s\in S$ may take on
$c_s\in\struct{C}$ different colors \cite{shapcott:2012}
(`\emph{$\struct{C}$-colored compositions}'), where $c_s$ is a
nonnegative
integer.
We term
the generalization of these two concepts considered in the present
work analogously \emph{$f$-weighted compositions}, and, under
restrictions on part sizes, \emph{$S$-restricted $f$-weighted
compositions}.
We give
three proofs of the named simple
result, Theorem \ref{theorem:main}, each shedding new light on the
problem. Our first proof is
a direct rewriting of extended binomial coefficients in terms of
integer partitions, using commutativity of $\struct{R}$ and the
multinomial theorem. Our second proof, which yields a very useful
characterization of extended binomial coefficients as giving the distribution
of the sum of $k$ independent multinomials,
generalizes
De Moivre's original observation
that extended binomial coefficients arise as
the distribution of the sum of $k$ independent random variables,
distributed uniformly on
the set $\set{0,1,\ldots,l}$ for some $l>0$; our proof is
inspired, too, by \cite{balas} and \cite{caiado}, who discuss related
settings.
Our third proof may be
considered a direct application of our second proof due to the
well-known characterization of sums of independent discrete random
variables, i.e., random walks, as directed lattice paths, but we give
an independent proof that uses the Vandermonde property (Lemma
\ref{lemma:vandermonde}) of extended binomial coefficients.
After having proven our main theorem, we specify, in Section
\ref{sec:applications}, a variety of applications of our main result,
which indicate the generality of our approach.
We structure our applications in three parts:
\begin{itemize}
\item Firstly, we discuss $S$-restricted $f$-weighted integer
compositions for particular choices of $S$ and $f$, as have been
considered in the literature. For example, we consider the case
where $S$ is the finite set $\set{0,1,\ldots,l}$; where
$S=\nn\wo\set{s_0}$ \cite{chinn2}, the nonnegative integers without a
particular element $s_0$; the cases when $f(s)=s$, which yields,
as mentioned, $n$-colored compositions; when $f(s)=s^r$, which
allows the derivation of moments of random integer compositions
\cite{schmutz,shapcott2};
and a few other cases, such as when $f$ is complex-valued or takes
values in the power set of a set $S$. In all these situations, our main
theorem allows us to effortlessly derive a closed-form solution
(and associated identities and properties)
for the combinatorial object we consider, the total weight of all
$S$-restricted integer compositions of $n$ with $k$ parts under
the weighting function $f$, in terms of
extended binomial coefficients.
\item Secondly, we present the most important application of our
main result, as we feel, namely, the situation when $f$ is a discrete
probability measure. In this case, our main theorem allows us to
derive a closed-form formula for the distribution of the sum of
$k$ independent random variables, which we use, e.g., to specify a
novel closed-form formula for the sum of $k$ logarithmically distributed
random variables. In the same context, we are able to derive
generalized Stirling formulae for central extended binomial
coefficients, by equating the exact closed-form solution with the
asymptotic distribution, as implied by the central limit theorem.
We also show, and make use of the fact, that extended binomial
coefficient
identities admit intriguing and convenient probabilistic proofs.
\item Finally, we derive a few combinatorial proofs of extended
binomial coefficient identities, based on their interpretation as
representing (the total weight of all) $S$-restricted $f$-weighted integer
compositions.
\end{itemize}
\section{Notation and preliminaries}\label{sec:notation}
By $\z$ we denote the set of integers, by $\nn$ we denote the set
of nonnegative integers and by $\mathbb{P}$ we denote the set of
positive
integers. Then,
an \emph{integer composition} of a nonnegative integer $n\in\nn$ is a
tuple $\pi = (\pi_1,\ldots,\pi_k)\in\nn^k$, $k\in\nn$, of nonnegative
integers such that
\begin{align*}
n = \pi_1+\cdots+\pi_k,
\end{align*}
where the $\pi_i$ are called \emph{parts}.
We call an integer composition of $n$ \emph{$S$-restricted}
(cf.\ \cite{malandro})
for a finite subset $S$ of $\nn$ if all parts satisfy $\pi_i\in
S$.
We denote the set of $S$-restricted integer compositions by
$\mathcal{C}_S(n,k)$ and by $c_S(n,k)$ we denote its size,
$c_S(n,k)=\abs{\struct{C}_S(n,k)}$.
Furthermore, we call a tuple of nonnegative integers
$(\lambda_1,\ldots,\lambda_k)\in\nn^k$ where $\lambda_1\ge
\lambda_2\ge \cdots\ge \lambda_k$ an \emph{integer partition} of $n$
(`unordered composition')
and analogously denote by $\struct{P}_S(n,k)$ the set of
$S$-restricted integer partitions and by $p_S(n,k)$ its
size. Obviously, each $S$-restricted integer partition
$\lambda=(\lambda_1,\ldots,\lambda_k)$
may be uniquely represented by a tuple $(\alpha_s)_{s\in S}$
--- $\alpha_s$, $\alpha_s\in\nn$, denoting the
\emph{multiplicity} of $s\in S$ in $\lambda$ ---
where $\sum_{s\in S}\alpha_s=k$ and
$\sum_{s\in S}s\alpha_s=n$. We silently identify the two
representations.
Next, let $\struct{R}=(R,+,\cdot,\mathbf{0},\mathbf{1})$ be a
commutative ring with addition $+$, multiplication $\cdot$ and
additive and multiplicative identities $\mathbf{0}$ and $\mathbf{1}$,
respectively. Let $f$ be
a function $f:S\goesto R$. In the current work, our interest lies,
in particular, in the quantity
\begin{align}\label{eq:dsf}
d_{S,f}(n,k)=\sum_{\pi =
(\pi_1,\ldots,\pi_k)\in\struct{C}_S(n,k)}f(\pi_1)\cdots
f(\pi_k),
\end{align}
where, obviously, the summation symbol refers to the addition
operation $+$ in $\struct{R}$, and likewise for multiplication $\cdot$.
We also remind the reader of the multinomial
theorem.
For $m\in\nn$, $x_1,\ldots,x_m\in R$, and $k\in\nn$ as above,
\begin{align}\label{eq:leibniz}
(x_1+\cdots+x_m)^k = \sum_{\overset{\alpha_1\ge
0,\ldots,\alpha_m\ge
0}{\alpha_1+\cdots+\alpha_m=k}}\binom{k}{\alpha_1,\ldots,\alpha_m}x_1^{\alpha_1}\cdots x_m^{\alpha_m},
\end{align}
where
$\binom{k}{\alpha_1,\ldots,\alpha_m}$ are
the respective \emph{multinomial coefficients} \cite{balas},
which,
for $\alpha_s\in\nn$, $s\in S$, and
$k=\sum_{s\in S}\alpha_s$, denote
the number of arrangements of $k$ objects of $\abs{S}$ different types
--- $\alpha_s$ of type $s$ for $s\in S$ --- in a sequence
of length $k$.
Finally, for $S$, $k$, and $n$ as above, we denote the coefficient,
called \emph{polynomial coefficient} or \emph{extended binomial
coefficient} in the literature (cf.\ \cite{balas,caiado,comtet,fahssi}), of
$x^n$ in the expansion of the univariate polynomial
$(\sum_{s\in S}f(s)x^s)^k\in \struct{R}[x]$ as
$\binom{k}{n}_{(f(s))_{s\in S}}$. More
precisely, we let
\begin{align}\label{eq:multinomial_coeff1}
\binom{k}{n}_{(f(s))_{s\in S}} =
[x^n](\sum_{s\in S}f(s)x^s)^k
\end{align}
where we use the standard notation $[x^n]h(x)$ to denote the
coefficient of $x^n$ of the polynomial $h(x)=\sum_i a_ix^i$,
i.e., $[x^n]h(x)=a_n$.
\section{Main theorem}\label{main:theorem}
\begin{theorem}\label{theorem:main}
With notation as in Section \ref{sec:notation},
\begin{align*}
d_{S,f}(n,k) = \binom{k}{n}_{(f(s))_{s\in S}}.
\end{align*}
\end{theorem}
\section{Proofs of the main theorem}
\begin{proof}[Proof of Theorem \ref{theorem:main}, 1]
Rewriting \eqref{eq:dsf} in terms of partitions, we find that
$d_{S,f}$
allows the following representation, because of commutativity of
multiplication in $\mathcal{R}$ and the combinatorial interpretation
of multinomial coefficients as above,
\begin{align}\label{eq:repr}
d_{S,f}(n,k) = \sum_{(\alpha_s)_{s\in S}\in
\struct{P}_S(n,k)}\binom{k}{(\alpha_s)_{s\in S}}\prod_{s\in S}f(s)^{\alpha_s} =
\sum_{\overset{\alpha_s\ge 0}{\overset{\sum_s\alpha_s =k}{\sum_s
s\alpha_s =n}}} \binom{k}{(\alpha_s)_{s\in S}}\prod_{s\in S}f(s)^{\alpha_s}.
\end{align}
On the other hand, substituting $x_s=f(s)x^s$, $s\in S$, in the
multinomial theorem
\eqref{eq:leibniz},
we find that
\begin{align}\label{eq:2}
\Bigl(\sum_{s\in S} f(s)x^s\Bigr)^k = \sum_{\overset{\alpha_s\ge
0}{\sum_s \alpha_s=k}}\binom{k}{(\alpha_s)_{s\in S}}\Bigl(\prod_{s\in
S}f(s)^{\alpha_s}\Bigr)x^{\sum_s s\alpha_s}.
\end{align}
Thus,
\begin{align*}
\binom{k}{n}_{(f(s))_{s\in S}}=[x^n]\Bigl(\sum_{s\in S}
f(s)x^s\Bigr)^k=d_{S,f}(n,k)
\end{align*}
as required.
\end{proof}
For our next proof, we assume that $\mathcal{R}$ is the field of real
numbers, that $f(s)\ge 0$ for all $s\in S$ and that $\sum_{s\in
S}f(s)\neq 0$. We also make use of the following observation.
If
\begin{align*}
X_1 + \cdots + X_k = n,
\end{align*}
where $X_1,\ldots,X_k$ are $S$-valued random variables,
then the $X_j$ variables form an $S$-restricted integer composition of
the integer $n$ with $k$ parts. Thus, by mutual disjointness of any
two distinct `composition events' and additivity of
probability measures,
\begin{align}\label{eq:4}
P[X_1+\cdots+X_k=n] =
\sum_{\pi=(\pi_1,\ldots,\pi_k)\in\mathcal{C}_S(n,k)}P[X_1=\pi_1,\ldots,X_k=\pi_k],
\end{align}
for every suitable probability measure $P$.
\begin{proof}[Proof of Theorem \ref{theorem:main}, 2]
Let $X_i$, $i=1,\ldots,k$, be identically and independently
distributed random variables, where each $X_i$ is multinomially distributed
on the set
$S$, where the probability that $X_i$ takes on the value $s\in S$ is
$p(s)=\frac{f(s)}{\sum_{s'\in S}f(s')}$. We derive the distribution of
the sum $X_1+\cdots+X_k$ in two ways, first by considering its
probability generating function (pgf) and then by a combinatorial
argument using \eqref{eq:4}.
Consider the pgf
$G_{X_i}(x)=\sum_{n=0}^\infty p(n)x^n$ of $X_i$.
Because $X_1,\ldots,X_k$ are independent, we have by elementary facts about
pgf's that
\begin{align*}
G_{X_1+\cdots+X_k}(x) = G_{X_1}(x)\cdots G_{X_k}(x) =
\Bigl(\sum_{s\in S}p(s)x^s\Bigr)^k = \sum_{n\ge 0}\binom{k}{n}_{(p(s))_{s\in
S}}x^n.
\end{align*}
Therefore,
\begin{align}\label{eq:one}
P[X_1+\cdots+X_k=n] &= \frac{G_{X_1+\cdots+X_k}^{(n)}(0)}{n!} =
\frac{n!}{n!}\binom{k}{n}_{(p(s))_{s\in S}} =
\binom{k}{n}_{(p(s))_{s\in S}},
\end{align}
where by $G_X^{(n)}(0)$ we denote the $n$-th derivative of $G_X$,
evaluated at zero.
On the other hand, by
\eqref{eq:4} and using independence of
$X_1,\ldots,X_k$, $P[X_1+\cdots+X_k=n]$ is given by,
\begin{equation}\label{eq:two}
\begin{split}
P[X_1+\cdots+X_k=n] &= \sum_{\pi=(\pi_1,\ldots,\pi_k)\in
\struct{C}_S(n,k)}P[X_1=\pi_1]\cdots P[X_k=\pi_k] \\ &= \sum_{\pi\in
\struct{C}_S(n,k)} p({\pi_1})\cdots p({\pi_k})=
d_{S,p}(n,k).
\end{split}
\end{equation}
Thus, equating \eqref{eq:one} and \eqref{eq:two} yields
$d_{S,p}(n,k)=\binom{k}{n}_{(p(s))_{s\in S}}$, but this suffices,
since, as can easily be
verified by factoring out the
normalizer
$c=\sum_{s'\in S}f(s')$,
\begin{align*}
d_{S,f}(n,k) =
{c^k}d_{S,p}(n,k)={c^k}\binom{k}{n}_{(p(s))_{s\in
S}}=\binom{k}{n}_{(f(s))_{s\in S}}.
\end{align*}
\end{proof}
For our final proof, we use the following inductive characterizations
of extended binomial coefficients, which generalize the corresponding
properties of ordinary binomial coefficients.
\begin{lemma}\label{lemma:vandermonde}
With notation as in Section \ref{sec:notation},
\begin{align*}
\text{(i)} &\quad \binom{k}{n}_{(f(s))_{s\in S}} =
\sum_{\mu+\nu=n}\binom{j}{\mu}_{(f(s))_{s\in S}}\binom{k-j}{\nu}_{(f(s))_{s\in
S}},\\
\text{(ii)} &\quad \binom{k}{n}_{(f(s))_{s\in S}} = \sum_{s\in
S}f(s)\binom{k-1}{n-s}_{(f(s))_{s\in S}},\\
\end{align*}
where $0\le j\le k$. For (ii), we have the `initial condition'
$\binom{0}{0}_{(f(s))_{s\in
S}}=\mathbf{1}$.
\end{lemma}
\begin{figure}[!h]
\centering
\begin{tikzpicture}
\draw[very thin,step=0.8cm,color=gray] (0,0) grid (2.4,1.6);
\draw[->] (0,0) -- (2.4,0.8);
\draw[->,color=blue] (2.4,0.8) -- (2.4,1.6);
\end{tikzpicture}
\hspace{1cm}
\begin{tikzpicture}
\draw[very thin,step=0.8cm,color=gray] (0,0) grid (2.4,1.6);
\draw[->,color=red] (0,0) -- (1.6,0.8);
\draw[->] (1.6,0.8) -- (2.4,1.6);
\end{tikzpicture}
\hspace{1cm}
\begin{tikzpicture}
\draw[very thin,step=0.8cm,color=gray] (0,0) grid (2.4,1.6);
\draw[->] (0,0) -- (0.8,0.8);
\draw[->,color=red] (0.8,0.8) -- (2.4,1.6);
\end{tikzpicture}
\hspace{1cm}
\begin{tikzpicture}
\draw[very thin,step=0.8cm,color=gray] (0,0) grid (2.4,1.6);
\draw[->,color=blue] (0,0) -- (0,0.8);
\draw[->] (0,0.8) -- (2.4,1.6);
\end{tikzpicture}\\ \vspace{0.2cm}
\begin{tikzpicture}
\draw[very thin,step=0.8cm,color=gray] (0,0) grid (2.4,1.6);
\draw[->] (0,0) -- (2.4,0.8);
\draw[->,color=green] (2.4,0.8) -- (2.4,1.6);
\end{tikzpicture}
\hspace{1cm}
\begin{tikzpicture}
\draw[very thin,step=0.8cm,color=gray] (0,0) grid (2.4,1.6);
\draw[->,color=violet] (0,0) -- (1.6,0.8);
\draw[->] (1.6,0.8) -- (2.4,1.6);
\end{tikzpicture}
\hspace{1cm}
\begin{tikzpicture}
\draw[very thin,step=0.8cm,color=gray] (0,0) grid (2.4,1.6);
\draw[->] (0,0) -- (0.8,0.8);
\draw[->,color=violet] (0.8,0.8) -- (2.4,1.6);
\end{tikzpicture}
\hspace{1cm}
\begin{tikzpicture}
\draw[very thin,step=0.8cm,color=gray] (0,0) grid (2.4,1.6);
\draw[->,color=green] (0,0) -- (0,0.8);
\draw[->] (0,0.8) -- (2.4,1.6);
\end{tikzpicture}
\caption
{
The eight colored paths from $(0,0)$ to $(3,2)$ with steps in
$\set{(0,1),(1,1),(2,1),(3,1)}$, where $(0,1)$ and $(2,1)$ come in
two different colors and the remaining steps in one.
}
\label{fig:latticePaths}
\end{figure}
\begin{proof}
As in the ordinary binomial case, the \emph{Vandermonde convolution} (i)
follows from equating coefficients on both sides of $\bigl(\sum_{s\in
S}f(s)x^s\bigr)^k = \bigl(\sum_{s\in
S}f(s)x^s\bigr)^{j}\bigl(\sum_{s\in
S}f(s)x^s\bigr)^{k-j}$. The \emph{addition/induction} property (ii)
is a special case of (i) with $j=1$. See also \cite{fahssi}.
\end{proof}
For our final proof of Theorem \ref{theorem:main}, let $\mathcal{R}$
be the ring of
integers and $f(s)\in\nn$, in which case Fahssi \cite{fahssi}
refers to the array of extended binomial coefficients as
\emph{arithmetical polynomial triangle}.
\begin{proof}[Proof of Theorem \ref{theorem:main}, 3]
Consider \emph{two-dimensional monotone colored lattice paths} from $(0,0)$ to
$(n,k)$ as illustrated in Figure \ref{fig:latticePaths}, i.e., paths in
the lattice $\z^2$ from $(0,0)$ to $(n,k)$
in which only steps $(a,b)$ for $a\ge 0$, $b\ge
0$,
are allowed and each step $r=(a,b)$ comes in $g(r)$, $g(r)\in\nn$, different
colors. If $R\subseteq\nn^2\wo\set{(0,0)}$ specifies the allowed
steps,
the number $T_{R,g}(i,j)$ of monotone colored lattice paths from
$(0,0)$ to
$(i,j)$ with steps in $R$ satisfies the recurrence,
\begin{align}\label{eq:paths}
T_{R,g}(i,j) = \sum_{r=(a,b)\in R} g(r)T_{R,g}(i-a,j-b),
\end{align}
with $T_{R,g}(0,0)=1$ and $T_{R,g}(i,j)=0$ for $i<0$ or $j<0$. Now consider
$R=\set{(s,1)\sd s\in S}$ (`simple steps') and $g((s,1))=f(s)$. Then
$T_{R,g}(n,k)$ satisfies, thus,
\begin{align*}
T_{R,g}(n,k)=\sum_{s\in S} f(s)T_{R,g}(n-s,k-1),
\end{align*}
with $T_{R,g}(0,0)=1$ and is hence, considering Lemma \ref{lemma:vandermonde},
precisely the number $\binom{k}{n}_{(f(s))_{s\in S}}$.
On the other hand, the number $T_{R,g}(n,k)$ of monotone colored lattice
paths with steps in
$R=\set{(s,1)\sd s\in S}$ and $g((s,1))=1$ is obviously
the number
$c_S(n,k)$ since
\begin{align*}
(\pi_1,\ldots,\pi_k)\mapsto \bigl((\pi_1,1),\ldots,(\pi_k,1)\bigr)
\end{align*}
with $\pi_1,\ldots,\pi_k\in S$
represents an obvious bijection between $\struct{C}_S(n,k)$ and the
set of
monotone paths from $(0,0)$ to $(n,k)$ with steps in $R$. For general
$g((s,1))=f(s)\in \nn$, $T_{R,g}(n,k)$ analogously retrieves general
$d_{S,f}(n,k)$.
\end{proof}
\section{Discussion}\label{sec:discussion}
\begin{remark}
We first note that the assumption of finiteness of $S$, which we
have made throughout, is not
a restriction of generality, since,
e.g., $\struct{C}_{S}(n,k)=\struct{C}_{S\cap\set{0,1,\ldots,n}}(n,k)$
so that our main result also holds for infinite $S$, when we, e.g., define
$\binom{k}{n}_{(f(s))_{s\in S}}$ by $\binom{k}{n}_{(f(s))_{s\in
S\cap\set{0,1,\ldots,n}}}$ in this case. Also note that,
e.g., \eqref{eq:4} holds whether or not $S$ is finite.
\end{remark}
\begin{remark}\label{remark:ccolor}
Next, we remark that by the third proof of Theorem
\ref{theorem:main}, the quantities $d_{S,f}(n,k)$, with $f(s)\in\nn$
for all $s\in S$, have
the interpretation of counting colored monotone lattice
paths with steps in
$R=\set{(s,1)\sd s\in S}$. Thus, by the trivial correspondence of such
paths and restricted integer compositions, $d_{S,f}(n,k)$ counts the
number of $S$-restricted $\struct{C}$-color compositions
\cite{shapcott:2012}, where
$\struct{C}=(f(s))_{s\in S}$, in this case, which
generalize $n$-color compositions,
for
which $f(s)=s$,
i.e., part $s$ comes in $s$ different colors. Analogously, as indicated
in Section \ref{sec:introduction}, we call
compositions with arbitrary $f$, \emph{$S$-restricted $f$-weighted
compositions} and note that $d_{S,f}(n,k)$ represents their
`quantification' --- a value in a commutative ring that may be considered
the `total weight' of all $S$-restricted integer compositions of $n$
with $k$ parts under the weighting function $f$ ---
for fixed $n$ and fixed number $k$ of parts.
\end{remark}
We also note the following immediate consequences of Theorem
\ref{theorem:main}, the first two of which are shown in
\cite{shapcott:2012}.
\begin{corollary}\label{cor:1}
\begin{itemize}
\item[(a)] The quantity $d_{S,f}(n)=\sum_{k\ge 0} d_{S,f}(n,k)$
is given by
\begin{align*}
[x^n]\frac{1}{1-\sum_{s\in S}f(s)x^s}.
\end{align*}
For $\nn$-valued $f$, $d_{S,f}(n)$ counts the total number of
$S$-restricted $f$-weighted compositions of $n$.
\item[(b)]
The quantity
$\sum_{k\ge 0} kd_{S,f}(n,k)$ is given by
\begin{align*}
[x^n]\frac{\sum_{s\in S}f(s)x^s}{\Bigl(1-\sum_{s\in
S}f(s)x^s\Bigr)^2}.
\end{align*}
For $\nn$-valued $f$, $\sum_{k\ge 0} kd_{S,f}(n,k)$ counts the
total number of parts over all $S$-restricted $f$-weighted
compositions.
\item[(c)] The quantity $\sum_{n\ge 0} nd_{S,f}(n,k)$ is given by
\begin{align*}
k\bigl(\sum_{s\in S} f(s)\bigr)^{k-1}\cdot \bigl(\sum_{s\in S}sf(s)\bigr).
\end{align*}
If $f$ is a probability distribution, $\sum_{n\ge 0}
nd_{S,f}(n,k)$ is the expected value of the sum of the underlying
random variables.\footnote{Which, of course, due to linearity of
the expectation operator and identical distribution of
$X_1,\ldots,X_k$,
must equal
$k\Exp[X_1]$, as verified by formula (c).}
\item[(d)] The quantity $\sum_{n\ge 0} n^2d_{S,f}(n,k)$ is given
by
\begin{align*}
k\bigl(\sum_{s\in S}f(s)\bigr)^{k-2}\Bigl(
\sum_{s\in S}f(s)\sum_{s\in S}s^2f(s)+(k-1)\bigl(\sum_{s\in S}sf(s)\bigr)^2
\Bigr).
\end{align*}
If $f$ is a probability
distribution, $\sum_{n\ge 0}
n^2d_{S,f}(n,k)$ is the second moment of the sum of the underlying
random variables.
\end{itemize}
\end{corollary}
\begin{proof}
Properties (a) and (b) immediately follow from the characterization
of $d_{S,f}(n,k)$ given in Theorem \ref{theorem:main} and well-known
explicit formulae for geometric series. Property (c) follows from
differentiating $(\sum_{s\in S}f(s)x^s)^k =\sum_{n\ge 0}
\binom{k}{n}_{(f(s))_{s\in S}}x^n$ with respect to $x$ and
evaluating at $x=1$. A simpler proof of (c) for nonnegative $f$ is
obtained by noting that, with notation as in the second proof of Theorem
\ref{theorem:main},
\begin{align*}
\sum_{n\ge 0} nd_{S,f}(n,k) &= \sum_{n\ge 0} nc^kd_{S,p}(n,k) =
(\sum_{s\in S}f(s))^k \sum_{n\ge 0}nd_{S,p}(n,k)
=(\sum_{s\in S}f(s))^k\Exp[X_1+\cdots+X_k]\\
&=(\sum_{s\in S}f(s))^kk(\sum_{s\in S}sp(s))=(\sum_{s\in
S}f(s))^{k-1}k(\sum_{s\in S}sf(s)).
\end{align*}
Property (d) follows from differentiating $(\sum_{s\in S}f(s)x^s)^k =\sum_n
\binom{k}{n}_{(f(s))_{s\in S}}x^n$ twice with respect to $x$ and
evaluating at $x=1$, or, for nonnegative $f$, by referring to the
second moment of $X_1+\cdots+X_k$ analogous as for (c).
\end{proof}
\begin{remark}
Properties (c) and (d) in the above corollary read as
\begin{align*}
\sum_{n=0}^k n\binom{k}{n} = k2^{k-1},\quad\quad \sum_{n=0}^k n^2
\binom{k}{n} = (k+k^2)2^{k-2},
\end{align*}
respectively,
for ordinary binomial coefficients.
\end{remark}
\section{Applications}\label{sec:applications}
In this section, we discuss a variety of applications of
Theorem \ref{theorem:main} and its proofs. We
thereby omit the choice of the ring $\struct{R}$ when it
is clear from the context. We split our applications in three parts:
Applications based on selected $S$ and $f$ (Section \ref{sec:sf}),
applications based on selected $S$ and where $f$ is a probability
measure (Section \ref{sec:pm}), which apparently yields the most
interesting results, and applications for proving identities of the
coefficients $\binom{k}{n}_{(f(s))_{s\in S}}$ based on their combinatorial
interpretation as representing restricted colored monotone lattice
paths and
restricted colored integer compositions (Section \ref{sec:comb}).
\subsection{$S$-restricted $f$-weighted compositions for particular
$S$ and $f$}\label{sec:sf}
To start, we discuss quantities $d_{S,f}(n,k)$ for selected
$S$ and $f$, thereby showing how Theorem \ref{theorem:main} can
be applied to easily tackle problems discussed in the literature. We
also present a few problems that, to our knowledge, have not been
previously considered, because the literature so far has focussed on
problems where $f$ is an indicator function or, at best, where $f$
is arithmetical.
We first note that problems where $f$ is an indicator function,
i.e., $f(s)=1$ for $s\in B$ and $f(s)=0$ for $s\in S\wo B$, are not
particularly interesting because $d_{S,f}(n,k)=c_B(n,k)$ in this case. Still,
we begin with this situation because it introduces the important class
of coefficients $\binom{k}{n}_{l+1}$.
\begin{example}[Compositions with no occurrence of $s_0$]\label{example:s0}
Chinn and Heubach \cite{chinn2} discuss compositions of $n$ with no
occurrence of a
particular integer $s_0$.
We obtain this case by setting $f(s)=0$ for $s=s_0$ and $f(s)=1$
otherwise.
We
find, for
example, for $S=\mathbb{P}$ and $s_0=1$,
\begin{align*}
\Bigl(d_{S,f}(n,k)\Bigr)_n=\Bigl(\binom{k}{n}_{(0,1,1,1,\ldots)}\Bigr)_n = (1,3,6,10,15,21,28,\ldots)
\end{align*}
for $k=3$ and $n=6,7,8,9,10,11,12,13,\ldots$. We note that
the recursion which Chinn and Heubach \cite[Theorem 5, p.\ 44]{chinn2}
give for the
number of
compositions of $n$ with $k$ parts without $s_0$
is nothing but the
addition/induction property, Lemma \ref{lemma:vandermonde} (ii), of
extended binomial coefficients for their particular setting.
\end{example}
\begin{example}[Compositions with parts in
$\set{0,1,\ldots,l}$]\label{example:ordinary}
Let $S=\set{0,1,\ldots,l}$ for some $l\ge 0$, and $f(s)=1$ for all $s\in S$,
$\struct{R}=(\z,+,\cdot,0,1)$. Then
$d_{S,f}(n,k)=c_{S}(n,k)=\binom{k}{n}_{(1,1,\ldots,1)}$. This coefficient is
ordinarily denoted by $\binom{k}{n}_{l+1}$
(cf.\ \cite{andrews,caiado,fahssi}). The upper bound $l=1$
yields the ordinary binomial coefficients.
\end{example}
\begin{example}[Sum of part-products]
Let $f(s)=s$ for all $s\in S$, $\struct{R}=(\z,+,\cdot,0,1)$. Then,
\begin{align*}
d_{S,f}(n,k)=\sum_{\pi\in
\struct{C}_S(n,k)}\pi_1\cdots\pi_k
\end{align*}
is the sum of the $S$-restricted part-products of integer
compositions of $n$ with $k$ parts. For $S=\set{1,2,\ldots,l}$,
$d_{S,f}(n,k)$ is hence $\binom{k}{n}_{{(1,2,\ldots,l)}}$.
\end{example}
\begin{example}[$n$-color compositions]\label{example:ncolor}
As mentioned, the case when $f(s)=s$ also counts the $n$-color
compositions.
Agarwal \cite{agarwal:2000} discusses generating functions for the number of
$n$-color compositions of $n$ with $k$ parts and Guo \cite{guo:2012}
studies
generating functions for the number of $n$-color odd compositions of
$n$ with $k$ parts (i.e., all parts are odd).
Then, (a) $S$-restricted $n$-color compositions of $n$ with $k$ parts
resp. (b) $S$-restricted $n$-color odd compositions of $n$ with $k$
parts
are obtained within our framework
as the numbers $d_{S,f}(n,k)$ with
(a) $f(s)=s$ for all $s\in S$ and (b) $f(s)=s$ for
all odd $s\in S$ and $f(s)=0$ otherwise. By Theorem
\ref{theorem:main}, the generating functions for (a) and (b) are hence,
\begin{align*}
\Bigl(\sum_{s\in S}sx^s\Bigr)^k,\quad\text{and}\quad \Bigl(\sum_{\overset{s\in S}{s \text{ odd}}}sx^s\Bigr)^k.
\end{align*}
If we let $S=\mathbb{P}$, the set of positive integers, then
the closed-form solutions (\cite[Theorem 1, p.\ 1423]{agarwal:2000} and
\cite[Theorem 4, p.\ 3]{guo:2012}, respectively)
\begin{align*}
\frac{x^k}{(1-x)^{2k}},\quad\text{and}\quad \frac{x^k(1+x^2)^k}{(1-x^2)^{2k}}
\end{align*}
for (a) and (b) are readily obtained.
In this context, the closed-form solution $\binom{n+k-1}{2k-1}$ for
the number of $n$-color compositions of $n$ with $k$ parts in
$S=\mathbb{P}$ \cite[Theorem 1, p.\ 1423]{agarwal:2000}, can
be shown inductively, using the addition/induction property of
extended binomial coefficients,
\begin{align*}
\binom{k}{n}_{(f(s))_{s\in S}} =
\sum_{s=1}^{n-1}s\binom{k-1}{n-s}_{(f(s))_{s\in
S}}=\binom{k}{n-1}_{(f(s))_{s\in
S}}+\sum_{s=1}^{n-1}\binom{k-1}{n-s}_{(f(s))_{s\in S}},
\end{align*}
where $f(s)=s$ for $s\in\mathbb{P}$. By the induction hypothesis
\begin{align*}
\sum_{s=1}^{n-1}\binom{k-1}{n-s}_{(f(s))_{s\in S}} =
\sum_{s=1}^{n-1}\binom{n-s+k-2}{2k-3} = \binom{n-2+k}{2k-2}
\end{align*}
and $\binom{k}{n-1}_{(f(s))_{s\in S}}=\binom{n-2+k}{2k-1}$, so that
the formula is verified.
\end{example}
\begin{example}[Part-products of uniform random
compositions]\label{example:partProducts}
Still in a similar context,
let $X_{S,k,n}$ be the random variable that, for a random (uniformly
chosen) $S$-restricted
integer
composition $\pi=(\pi_1,\ldots,\pi_k)$ of $n$ with $k$ parts, takes
on the part-product
$\pi_1\cdots\pi_k$. Then, $X_{S,k,n}$ takes on
$p_S(n,k)$ different values, where $p_S(n,k)=\length{\struct{P}_S(n,k)}$, and
the probability that it
takes on value $\prod_{s\in S}s^{\alpha_s}$ for $(\alpha_s)_{s\in
S}\in \struct{P}_S(n,k)$ is $\frac{\binom{k}{(\alpha_s)_{s\in
S}}}{c_S(n,k)}$. Hence, the expected value of $X_{S,k,n}$ is
\begin{align*}
\Exp[X_{S,k,n}] = \sum_{(\alpha_s)_{s\in S}\in
\struct{P}_S(n,k)}\frac{\binom{k}{(\alpha_s)_{s\in
S}}}{c_S(n,k)}\prod_{s\in S}s^{\alpha_s} = \frac{d_{S,f}(n,k)}{c_S(n,k)},
\end{align*}
where $f$ is the identity map. More generally, the $r$-th moment,
$r\in\nn$, of $X_{S,k,n}$ is given as
\begin{align*}
\Exp[X_{S,k,n}^r] = \frac{d_{S,f}(n,k)}{c_S(n,k)} =
\binom{k}{n}_{(g(s))_{s\in S}},
\end{align*}
where $f(s)=s^r$ for $s\in S$ and where
$g(s)=\frac{s^r}{c_S(n,k)^{1/k}}$. The variables $X_{S,k,n}$,
together with
asymptotics of related variables, are discussed
in \cite{schmutz} and \cite{shapcott2}.
But note that, in fact, it also holds that
\begin{align*}
\Exp[f(X_{S,k,n})] = \frac{d_{S,f}(n,k)}{c_S(n,k)} =
\binom{k}{n}_{(g(s))_{s\in S}},\quad g(s)=\frac{f(s)}{c_S(n,k)^{1/k}},
\end{align*}
whenever $f$ is multiplicatively linear, i.e., when $f(ab)=f(a)f(b)$,
which includes all powers $f(s)=s^{\beta}$, with $\beta\in\real$,
where $\real$ denotes the set of real numbers,
since in this case $f(\prod_{s\in S}s^{\alpha_s})=\prod_{s\in
S}f(s)^{\alpha_s}$.
We finally remark that since
$\Exp[f(X_{S,k,n})]$ can be expressed as an extended binomial
coefficient, this expected value allows a representation as a
convolution of expected values, e.g., via the Vandermonde property in Lemma
\ref{lemma:vandermonde},
\begin{align*}
\Exp[f(X_{S,k,n})] = \sum_{\mu=0}^n \Exp[f(X_{S,j,\mu})] \Exp[f(X_{S,k-j,n-\mu})]
\end{align*}
for all $0\le j\le k$.
\end{example}
\begin{example}
We can of course also, e.g., define $Y_{S,k,n}$ as the variable whose values
are $\log\bigl(\pi_1\cdots\pi_k\bigr)$ for random uniform
$S$-restricted integer compositions,
so that its moment
generating function turns out to be
\begin{align*}
M(t) = \exp(tY_{S,k,n}) = \binom{k}{n}_{(g(s))_{s\in S}},
\end{align*}
with $g(s)=\frac{s^t}{c_{S}(n,k)^{1/k}}$.
\end{example}
\begin{example}[Odd number of compositions with odd parts]\label{example:odd}
Let $f(s)=1$ if $s\in S$ is odd and zero otherwise. Then
$\binom{k}{n}_{(0,1,0,1,0,1,\ldots)}$ is the number of
$S$-restricted integer compositions with no even parts. For example,
$\binom{2}{4}_{(0,1,0,1,0,1,\ldots)}=2$ since $4=1+3=3+1$.
To make the example more interesting,
let $f:S\goesto T$ with $T={\z}/({2\z})$ with $s\mapsto [s]$, where
$[s]$ is the congruence class of
the integer $s$ in the Boolean ring ${\z}/({2\z})$. Then
$\binom{k}{n}_{([0],[1],[0],[1],[0],[1],\ldots)}$ is $[1]$ if $n$
has an odd number of compositions with all parts odd ($k$ parts fixed).
\end{example}
\begin{example}[Parity of extended binomial
coefficients]\label{example:parity}
Relatedly, $\binom{k}{n}_{(f(s))_{s\in S}}$ with $f(s)=[1]$ for all
$s\in S$ (with notation as in Example \ref{example:odd}) is $[1]$ if
and only if
there are an odd number of $S$-restricted integer compositions of
$n$ with $k$ parts. In
other words,
$[\binom{k}{n}_{(1,1,\ldots)}]=\binom{k}{n}_{([1],[1],\ldots)}$,
where $[x]$ denotes the \emph{parity} of $x\in\nn$, as above. We
find the
following characterization for $S=\set{0,1,\ldots,l}$,
\begin{align}\label{eq:parity}
\binom{k}{n}_{([1],[1],\ldots,[1])} =
\begin{cases}
[0], & \text{if $k$ even and $n$ odd};\\
\binom{k/2}{n/2}_{([1],[1],\ldots,[1])}, & \text{if $k$ even and
$n$ even};\\
\sum_{i=0}^{\lfloor \frac{l-r(n)}{2}\rfloor}\binom{\lfloor
k/2\rfloor}{\lfloor n/2\rfloor-i}_{([1],[1],\ldots,[1])}, &
\text{otherwise,}
\end{cases}
\end{align}
where we let $r(n)=1$ if $n$ is odd and $r(n)=0$ otherwise.
To prove \eqref{eq:parity}, note
that for $k$ even and $n$ odd, $\binom{k}{n}_{l+1}$ must be even by
the absorption/extraction property of extended binomial coefficients,
Example \ref{ex:panjer} below (bringing $n$ to the left-hand
side in the example). Moreover, if $k$ and $n$ are even, then by the
Vandermonde property, Lemma \ref{lemma:vandermonde}, of extended
binomial coefficients with $j=k/2$,
\begin{align*}
\binom{k}{n}_{([1],[1],\ldots,[1])} = \sum_{x=0}^n
\binom{k/2}{x}_{([1],[1],\ldots,[1])}\binom{k/2}{n-x}_{([1],[1],\ldots,[1])}.
\end{align*}
All summands on the right-hand side, except for
$\binom{k/2}{n/2}_{([1],[1],\ldots,[1])}^2=\binom{k/2}{n/2}_{([1],[1],\ldots,[1])}$,
appear exactly twice;
hence, since $[0]+[0]=[1]+[1]=[0]$, their
contribution is $[0]$. Finally, to prove the above relation for odd $k$,
one can use the addition/induction property (Vandermonde
property for $j=1$); since $k-1$ is even when $k$ is odd,
the two cases when $k$ is even may be applied. Note how
\eqref{eq:parity} generalizes the well-known `parity relationship' for
ordinary binomial coefficients (see Table \ref{table:identities}).
\end{example}
\begin{example}[Minimal parts]
Let $f:S\goesto 2^S$ with $s\mapsto\set{0,1,\ldots,s}$ and let
$\struct{R}=(2^S,\Delta,\cap,\emptyset,S)$, where $2^S$ is the power
set of $S$, and $\Delta$ denotes the symmetric
difference on sets. Then, if $x\in S$ is the maximal
element of $d_{S,f}(n,k)$, the part $x$ is the minimal part of an
$S$-restricted integer composition of $n$ with $k$ parts an odd
number of times. For example, for $S=\set{0,1,2,3}$,
$\binom{3}{8}_{(\set{0},\set{0,1},\set{0,1,2},\set{0,1,2,3})}=\set{0,1,2}$
and $2$ is the minimal part exactly three
times here, $8=3+3+2=3+2+3=2+3+3$.
\end{example}
\begin{example}[`Alternating trinomial coefficients']
Let $S=A\cup B$ where $A$ and $B$ are disjoint. Let $f(s)=1$ if
$s\in A$ and $f(s)=-1$ if $s\in B$. Then $d_{S,f}(n,k)$ denotes the
difference between the number of compositions of $n$ with $k$ parts
that have an even number of parts in $B$ and those that have an odd
number of parts in $B$. For example, for $S=\set{0,1,2}$ and
$B=\set{1}$, we have $\binom{4}{1}_{(1,-1,1)}=-4$ since
$1=0+0+0+1=0+0+1+0=0+1+0+0=1+0+0+0$, i.e., all compositions have an odd
number of $1$. In general here,
$\binom{k}{n}_{(1,-1,1)}=(-1)^n\binom{k}{n}_{(1,1,1)}$ (`alternating
trinomial coefficients'), since if and
only if
$n$ is odd, an odd number of $1$ is required to form a composition
of $n$.
\end{example}
\begin{example}[`Complex alternating quadrinomial coefficients']
Let $f(s)=e^{\frac{\pi}{2}i\cdot s}$, where
$i$ is the
imaginary unit.
For $S=\set{0,1,2,3}$, we
have, e.g.,
\begin{align*}
\bigl(\binom{k}{n}_{(1,i,-1,-i)}\bigr)_n = (1,3i,-6,10i,12,12i,-10,-6i,3,i),
\end{align*}
for $n=0,1,\ldots,9$ and $k=3$, which, in general, yields the
`complex alternating quadrinomial coefficients'.
\end{example}
\begin{example}[Individual $f_i$'s]\label{example:fi}
Note also the following generalization of the quantities
$d_{S,f}(n,k)$. Instead of using the \emph{same} $f$ for each part,
we may consider \emph{different} $f_i$'s for different parts
$\pi_i$. For example, we might consider the ring element
\begin{align*}
d_{S,f_1,\ldots,f_j,f}(n,k) = \sum_{\pi}
f_1(\pi_1)\cdots f_j(\pi_j)\cdot f(\pi_{j+1})
\cdots f(\pi_k),
\end{align*}
i.e., where the first $j\le k$ parts are individually mapped to ring
elements while the remaining $(k-j)$ parts have homogeneous
$f$. Probabilistically, this corresponds to the distribution of the
sum of $k$ \emph{independent but not identically} distributed random
variables.
We find by simple
rewriting using Theorem \ref{theorem:main} that
\begin{align*}
d_{S,f_1,\ldots,f_j,f}(n,k) =
\sum_{x_1+\cdots+x_j+y=n}f_1(x_1)\cdots
f_j(x_j)\cdot\binom{k-j}{y}_{(f(s))_{s\in S}}.
\end{align*}
Using $f_1=\cdots=f_j=g$,
we find
\begin{align*}
d_{S,f_1,\ldots,f_j,f}(n,k) =
\sum_{x+y=n}\binom{j}{x}_{(g(s))_{s\in
S}}\binom{k-j}{y}_{(f(s))_{s\in S}},
\end{align*}
which can be considered a generalized Vandermonde relationship.
In this context, Heubach and Mansour \cite{heubach} consider the
number of $S$-restricted compositions of $n$ (with $k$ parts) with
exactly $m$ parts in a
set $B\subseteq S$. Using the above,
where $g$
and $f$ are the indicator functions of the sets $B$ and $S\wo B$,
respectively,
we find the
closed-form solution for this quantity,
\begin{align*}
\binom{k}{m}\sum_{x=0}^n\binom{m}{x}_{(1)_{s\in
B}}\binom{k-m}{n-x}_{(1)_{s\in S\wo{B}}}.
\end{align*}
For $B=\set{s_0}$ with $s_0\in S$, this yields the number of
$S$-restricted compositions of $n$ with $k$ parts with exactly $m$
occurrences of $s_0$. Then, assuming $ms_0\le n$,
\begin{align*}
\sum_{m\ge 0} m\binom{k}{m}\binom{k-m}{n-ms_0}_{(1)_{s\in
S\wo{B}}}
\end{align*}
counts the number of times
part $s_0$ occurs in all
$S$-restricted
compositions of $n$ with $k$ parts
(cf.\ \cite[Example 2.11, p.\ 131]{heubach} and
\cite{chinn2}).
Similarly, for, e.g., $S=\set{1,2,s_0}$ and $B=\set{s_0}$
\cite[Example 2.14, p.\ 132]{heubach}, we find for the number $N_{S,\set{s_0}}(n,m)$ of $S$-restricted
compositions of $n$ (with
arbitrary number of parts) and exactly $m$ occurrences of $s_0$ the
closed-form formula
\begin{align*}
N_{S,\set{s_0}}(n,m)=\sum_{k\ge m}\binom{k}{m}\binom{k-m}{n-ms_0}_{(1,1)}.
\end{align*}
Since
$\binom{k-m}{n-ms_0}_{(1,1)}=\binom{k-1-m}{n-1-ms_0}_{(1,1)}+\binom{k-1-m}{n-2-ms_0}_{(1,1)}$ (addition/induction property),
we can rewrite as
\begin{align*}
N_{S,\set{s_0}}(n,m) =
N_{S,\set{s_0}}(n-1,m)+N_{S,\set{s_0}}(n-2,m)+N_{S,\set{s_0}}(n-s_0,m-1).
\end{align*}
The combinatorial interpretation thereof is clear: By adding $1$,
$2$, and $s_0$ at the end of $\set{1,2,s_0}$-restricted compositions
of $n-1$, $n-2$, and
$n-s_0$ with exactly $m$, $m$, and $m-1$ occurrences of $s_0$, we
obtain the $\set{1,2,s_0}$-restricted compositions of $n$ with
exactly $m$ occurrences of
$s_0$. This formula obviously generalizes:
\begin{align*}
N_{S,B}(n,m) = \sum_{s\in S\wo B}N_{S,B}(n-s,m) + \sum_{s_0\in
B}N_{S,B}(n-s_0,m-1),
\end{align*}
where $N_{S,B}(n,m)$ denotes the $S$-restricted compositions of $n$
(with arbitrarily many parts) with exactly $m$ parts in $B$ (denoted
$C_B^S(n,m)$ in \cite{heubach}).
Using this recursion gives another convenient way of deriving the generating
function for
$N_{S,B}(n,m)$ \cite[Corollary 2.12, p.\ 131]{heubach} as
\begin{align*}
\frac{(\sum_{s_0\in B}x^{s_0})^m}{\bigl(1-\sum_{s\in S\wo
B}x^s\bigr)^{m+1}}.
\end{align*}
\end{example}
\begin{example}
Of course, the last example can be arbitrarily extended. For
example, the number of $S$-restricted compositions of $n$ with $k$
parts with exactly $m_0$ parts in $B_0\subseteq S$ and $m_1$ parts
in $B_1\subseteq S$, $B_0\cap B_1=\emptyset$, is given by
\begin{align*}
\binom{k}{m_0,m_1,k-m_0-m_1}\sum_{z+y+x=n}\binom{m_0}{z}_{(1)_{s\in
B_0}}\binom{m_1}{y}_{(1)_{s\in
B_1}}\binom{k-m_0-m_1}{x}_{(1)_{s\in S\wo{(B_0\cup B_1)}}}.
\end{align*}
\end{example}
\begin{example}[Palindromic compositions]
Palindromic compositions, also called self-inverse compositions
\cite{narang:2006}, are
compositions where $\pi_i=\pi_{k+1-i}$
for all $i=1,\ldots,k$. Heubach and Mansour \cite{heubach} provide
generating functions for
the number of $S$-restricted palindromic compositions of $n$ with
$k$ parts. We can easily give closed-forms solutions for
our generalized setting of $S$-restricted $f$-weighted palindromic
compositions.
Define $\tilde{d}_{S,f}(n,k)=\sum_{\overset{\pi\in
\struct{C}_{S}(n,k)}{\pi_i=\pi_{k+1-i}}}f(\pi_1)\cdots
f(\pi_{\lceil k/2\rceil})$ and note that, when $f$ is $\nn$-valued,
$\tilde{d}_{S,f}(n,k)$ counts the number of colored palindromic
compositions where parts $\pi_i$ and $\pi_{k+1-i}$ have the same
color.
Then, it obviously holds
that,
\begin{align*}
\tilde{d}_{S,f}(n,k)=
\begin{cases}
\binom{k/2}{n/2}_{(f(s))_{s\in S}}, & \text{if $k$ is even};\\
\sum_{s\in S}
f(s)\binom{\frac{k-1}{2}}{\frac{n-s}{2}}_{(f(s))_{s\in S}}, & \text{otherwise},
\end{cases}
\end{align*}
where we let $\binom{k}{n}_{(f(s))_{s\in S}}=0$ if $n$ or $k$ are
not integral.
\end{example}
\subsection{Sums of independent random variables}\label{sec:pm}
Now, we consider situations where the weighting function $f$ is a
discrete probability measure.
In this context, we first note that
relationship \eqref{eq:4}
often reduces proofs about
sums of
independent variables to
one-liners when known results about integer compositions are taken
into consideration.
\begin{example}[Sum of geometrically distributed RVs]
For example,
if $X_j\sim \text{Geometric}(p)$, $j=1,\ldots,k$, i.e., each $X_j$ has
probability distribution function (pdf) $g(y)=(1-p)^yp$, for
$y\in\nn$,
then, denoting by $S_k$ the sum
$X_1+\cdots+X_k$,
\begin{align*}
P[S_k=n] &= \sum_{\pi\in\struct{C}_\nn(n,k)} (1-p)^{\pi_1}p\cdots
(1-p)^{\pi_k}p = p^k(1-p)^{n}c_\nn(n,k)=p^k(1-p)^n\binom{n+k-1}{k-1},
\end{align*}
which is the negative binomial distribution with parameters $(1-p)$
and $k$, and where we have used the well-known fact that the number of
$\nn$-restricted integer compositions of an integer $n$ with $k$
parts is the number $\binom{n+k-1}{k-1}$.
\end{example}
Another interesting case arises for the sum of logarithmically
distributed random variables, for which, to our knowledge, no
closed-form solution has been brought forward hitherto.
\begin{example}[Sum of logarithmically distributed RVs]\label{example:log}
If all $X_j$, $j=1,\ldots,k$, have logarithmic distribution with
parameter $p$, i.e., $g(y)=\frac{-1}{\log{(1-p)}}\frac{p^y}{y}$, for
$y\in\mathbb{P}$, then
\begin{align*}
P[S_k=n] &=
\sum_{\pi\in\struct{C}_{\mathbb{P}}(n,k)}\prod_{i=1}^k\frac{-1}{\log(1-p)}\frac{p^{\pi_i}}{\pi_i}
=
\Bigl(\frac{-1}{\log(1-p)}\Bigr)^kp^n\sum_{\pi\in
\struct{C}_{\mathbb{P}}(n,k)}\frac{1}{\pi_1\cdots
\pi_k}.
\end{align*}
Note that the quantity
$\sum_{\pi\in\struct{C}_{\mathbb{P}}(n,k)}\frac{1}{\pi_1\cdots\pi_k}$
is
precisely $d_{\mathbb{P},f}(n,k)$ with $f(s)=\frac{1}{s}$ for
$s\in\mathbb{P}$. Thus,
\begin{align*}
P[S_k=n]
&=\Bigl(\frac{-1}{\log(1-p)}\Bigr)^kp^n\binom{k}{n}_{(1,\frac{1}{2},\frac{1}{3},\ldots,\frac{1}{n})}.
\end{align*}
\end{example}
\begin{example}[Sum of multinomially distributed
RVs]\label{example:multinomial}
If all $X_j$, $j=1,\ldots,k$, have multinomial distribution on the set
$S$ with parameters $p_s$ for $s\in S$, i.e., the
number $s\in S$ is taken on with probability $p_s$, then
\begin{align*}
P[S_k=n] = \sum_{\pi\in\struct{C}_S(n,k)} p_{\pi_1}\cdots p_{\pi_k}.
\end{align*}
Intriguingly, $P[S_k=n]$ is thus precisely
$d_{S,f}(n,k)$ with $f(s)=p_s$.
Of course, this is the result derived in the second proof of
Theorem \ref{theorem:main} already.
It allows another interpretation of
the quantity $\binom{k}{n}_{(a_s)_{s\in S}}$. For nonnegative
real numbers $(a_s)_{s\in S}$ with $\sum_{s\in S}a_s\neq 0$, the
number $\frac{1}{c}\binom{k}{n}_{(a_s)_{s\in S}}$, where
$c=\sum_{j}\binom{k}{j}_{(a_s)_{s\in S}}$, is the probability of
obtaining
the integer $n$ when $k$ numbers are drawn (with replacement) from the
set $S$, where
the probability to draw $s\in S$ is $\frac{a_s}{\sum_{s'\in
S}a_{s'}}=\frac{a_s}{c^{1/k}}$.
For $S=\set{1,\ldots,m+1}$ and $p_s=\frac{1}{m+1}$, we
obtain De Moivre's original problem setting, and for
$S=\set{0,\ldots,m-1}$ and $p_s=p^sq^{m-s-1}$ (for appropriate $p$ and
$q$), we obtain the distribution discussed in \cite{balas}.
\end{example}
Continuing with this example,
we
find that,
by the central limit theorem,
the
`probabilities' $\frac{1}{c}\binom{k}{n}_{(a_s)_{s\in S}}$
are
asymptotically normal;
in other words,
the random variable $S_k$
that is the sum
of $k$ independent multinomials on the set $S$ with parameters
$p_s=\frac{a_s}{\sum_{s'\in S}a_{s'}}$ and whose exact distribution is
$P[S_k=n]=\frac{1}{c}\binom{k}{n}_{(a_s)_{s\in S}}$,
is, for large $k$, approximately
normally distributed
with mean value $\mu=k\sum_{s\in
S}sp_s$ and variance $\sigma^2=k(\sum_{s\in S}s^2p_s-(\sum_{s\in
S}sp_s)^2)$.
\begin{example}[Stirling's approximation to central extended binomial
coefficients]
Thus, by equating the exact distribution with the approximate (and
asymptotic) distribution
$\frac{1}{\sqrt{2\pi\sigma^2}}e^{-\frac{1}{2}\bigl(\frac{n-\mu}{2\sigma}\bigr)^2}$
at their mean value,
this entails, for example, for $S=\set{0,1,\ldots,l}$, $(a_s)_{s\in
S}=(1,1,\ldots,1)$, and $p_s=\frac{1}{l+1}$ (uniform distribution),
\begin{align}\label{eq:central}
\binom{k}{n}_{l+1} \sim \frac{(l+1)^k}{\sqrt{2\pi
k\frac{(l+1)^2-1}{12}}}
\end{align}
for $n=\lfloor \frac{kl}{2}\rfloor$, and where we write $a_k\sim b_k$
as short-hand for $\lim_{k\goesto\infty} \frac{a_k}{b_k}=1$.
For $l=1$, we have Stirling's approximation for central binomial
coefficients; the asymptotics of the central trinomial coefficient
also seems to be known (cf.\ \href{http://oeis.org/A002426}{A002426}
in Sloane
\cite{sloane}). To explicitly list asymptotics, we, e.g., have
\begin{align*}
\binom{k}{\frac{k}{2}} \sim \frac{2^{k+1}}{\sqrt{2\pi k}}, \quad
\binom{k}{k}_3 \sim \frac{3^k}{\sqrt{\frac{4}{3}\pi k}}, \quad
\binom{k}{\frac{3}{2}k}_4 \sim \frac{4^k}{\sqrt{\frac{5}{2}\pi
k}},\quad
\binom{k}{2k}_5 \sim \frac{5^k}{2\sqrt{\pi k}},
\end{align*}
for $l=1,2,3,4$. Apparently, Walsh \cite{walsh} has been
the first to derive Stirling's formula (for factorials) via the
central limit theorem, by equating Poisson and
normal density functions, while we equate here the distribution of a
sum of independent
multinomials with the normal density function; to the best of our
knowledge, the general Formula \eqref{eq:central} for central extended
binomial coefficients is novel.\footnote{However, Fahssi \cite{fahssi}
indicates a
very general formula, based on the Daniels-Good theorem, for the asymptotic of $[x^n](h(x))^k$, where
$h(x)$ is a polynomial or power series, in the case
when $n=O(k)$, which
is used to derive the asymptotic of the central trinomial
coefficient.}
\end{example}
\begin{example}
Analogously, for
$\binom{k}{n}_{(0,1,0,1,0,1,\ldots)}$,
Example \ref{example:odd}, we find for $S=\set{0,1,2,\ldots,2m}$ for
some $m\in\nn$, $p_s=\frac{1}{m}$ for $s\in S$, $s$ odd, and $p_s=0$
otherwise,
\begin{align*}
\binom{k}{n}_{(0,1,0,1,0,1,\ldots)}\sim 2\cdot\frac{m^k}{\sqrt{2\pi
k\frac{m^2-1}{3}}},
\end{align*}
for $n=km$ if $k$ is even or $m$ is odd and $n=km\pm 1$
otherwise.\footnote{The factor $2$ in the formula is a correction
because the exact distribution takes on strictly positive values
only for odd respectively even numbers.} For
example, for
$k=10$, $m=2$ and $n=20$,
we have
$\binom{k}{n}_{(0,1,0,1,0)}=252$ and the approximation
formula yields $258.37...$
\end{example}
Next, in the context of distributions of sums of
(discrete) random variables, (efficient) recursive evaluations of the
distributions $P[S_k=n]$, in the absence of closed-form solutions,
are of great interest to
practitioners.
Since, as shown, distributions of sums of independent $S$-valued variables are
just (the total weight of) $S$-restricted weighted integer
compositions, which in turn yield the
extended binomial coefficients,
these recursions
have direct correspondences with analogous properties of extended
binomial coefficients. Often, these properties have intriguing
probabilistic proofs.
\begin{example}[Absorption/extraction property]\label{ex:panjer}
The following recursive evaluation of the distribution of the sum
$S_k=X_1+\cdots+X_k$ goes back to B\"{u}hlmann and Gerber's discussion of
Panjer \cite{buhlmann} and
Panjer \cite{panjer}.
\begin{align}\label{eq:panjer}
P[S_k=n] = \frac{k}{n}\sum_{s\in S} sg(s)P[S_{k-1}=n-s],
\end{align}
where $g(y)$ is the pdf of the $X_i$'s.
This recursion corresponds to the `absorption/extraction' property
of
extended binomial coefficients \cite{fahssi},
\begin{align*}
\binom{k}{n}_{(f(s))_{s\in S}} = \frac{k}{n}\sum_{s\in
S}sf(s)\binom{k-1}{n-s}_{(f(s))_{s\in S}}.
\end{align*}
For ordinary binomial coefficients, this is just the property
\begin{align*}
\binom{k}{n}=\frac{k}{n}\binom{k-1}{n-1}.
\end{align*}
Fahssi \cite{fahssi} proves the absorption/extraction property
by
taking the derivative of both sides of $(\sum_{s\in S}f(s)x^s)^k =
\sum_{n\ge 0} \binom{k}{n}_{(f(s))_{s\in S}}x^n$ with respect $x$ and
equating coefficients of $x^n$. The probabilistic proof given in
Panjer \cite{buhlmann} and Panjer \cite{panjer} is slightly more
intriguing. We
have for the conditional expectation of $X_k$ given $S_{k}$,
\begin{align*}
\Exp[X_k \sd S_{k}=n] = \frac{n}{k},
\end{align*}
by independence and identical distribution of the variables
$X_1,\ldots,X_k$. By the definition of conditional expectation, this
immediately implies \eqref{eq:panjer}.
\end{example}
\begin{example}
Analogously, we find the following recursion, which goes back to De
Pril \cite{depril}.
Let $0\in S$. Then,
\begin{align}\label{eq:depril}
P[S_{k}=n] = \frac{1}{g(0)}\sum_{s\in S\wo\set{0}}
\Bigl(\frac{k+1}{n}s-1\Bigr)g(s)P[S_{k}=n-s],
\end{align}
which translates into the corresponding property of extended binomial
coefficients,
\begin{align*}
\binom{k}{n}_{(f(s))_{s\in S}} = \frac{1}{f(0)}\sum_{s\in S\wo\set{0}}
\Bigl(\frac{k+1}{n}s-1\Bigr)f(s)\binom{k}{n-s}_{(f(s))_{s\in S}},
\end{align*}
which is proven in \cite{knuth}.
For $S=\set{0,1}$ and $f(s)=1$ for $s\in S$, this reads as the
following property of ordinary
binomial coefficients,
\begin{align*}
\binom{k}{n} = \frac{k+1-n}{n}\binom{k}{n-1}.
\end{align*}
A very similar proof of \eqref{eq:depril} in terms of conditional
expectation as
in Example \ref{ex:panjer} is easily derivable \cite{depril}.
\end{example}
Finally, Sagan \cite{sagan} considers integer compositions `inside a
rectangle', i.e., those which have two-dimensional restrictions, one on
their part sizes and one on the number of parts. He then shows that
the sequence $\bigl(h_{l,m}(n)\bigr)_{n}$ is unimodal, that is, there
exists an index $i$ such that $h_{l,m}(0)\le \cdots \le h_{l,m}(i)\ge
h_{l,m}(i+1)\ge \cdots\ge h_{l,m}(lm)$, where $h_{l,m}(n)$ is the
number of integer compositions of $n$ with at most $m$ parts, each of
which has size at most $l$.
In the light of the previous discussions,
this result is very intuitive, at least `asymptotically'.
Namely, if we interpret
$h_{l,m}(n)$ probabilistically, it is (proportional to) the probability
that a randomly chosen
integer composition inside the rectangle $(l,m)$ represents the
integer $n$. Note that there are $(l+1)^m\approx l^m$ integer
compositions with $m$
parts and upper bound $l$, and $\sum_{k=0}^{m-1}(l+1)^k =
\frac{(l+1)^m-1}{l}\approx
l^{m-1}$ integer compositions with fewer than $m$ parts, so that, for
large
$l$ and $m$, we will most likely `hit' a composition with $m$ parts.
Then, the numbers
$\bigl(\binom{m}{n}_{l+1}\bigr)_n$ are `Gaussian' in nature,
representing
sums of independent multinomials; see also our discussion in
\cite{eger3}.
\subsection{Lattice paths \& combinatorial proofs of extended binomial
coefficient identities}\label{sec:comb}
Here, we present two combinatorial proofs relating to objects
involving
lattice paths. Our proofs are an application of the third proof of
Theorem \ref{theorem:main}. We also give four combinatorial
proofs of identities of extended binomial coefficients which are based
on their interpretation given in Theorem \ref{theorem:main} as
representing $S$-restricted $f$-weighted integer compositions.
\begin{example}[Counting lattice paths]\label{example:paths1}
Consider
monotone lattice paths from $(0,0)$ to $(n,k)$ with steps in
$\set{(0,1),(1,0)}$. Of course, there are exactly $\binom{n+k}{n}$
such paths --- we take $(n+k)$ steps in total and may choose the $n$
$(1,0)$ steps. We can derive this alternatively by noting that we may
replace each $(1,0)$ step by a $(1,1)$ step; thus, we arrive at
lattice point
$(n,n+k)$ using steps in $\set{(0,1),(1,1)}$, and by the
interpretation of such paths given in
the named proof,
their number is exactly $\binom{n+k}{n}_{l+1}$,
for $l=1$.
\end{example}
\begin{example}[Combinatorial proofs of Fibonacci
identities]\label{example:paths2}
Relatedly (but a bit more challenging), consider
monotone
paths from $(0,0)$
to $(0,n)$ with steps in $\set{(0,1),(0,2)}$. Of course, by Equation
\eqref{eq:paths} or simple reflection, there are $F_{n+1}$ such paths
where $F_n$ denotes
the $n$-th Fibonacci number. Now, replace each of $s$, where $0\le
s\le\lfloor\frac{n}{2}\rfloor$, $(0,2)$ steps by a
$(1,1)$ step, leaving the $(n-2s)$ $(0,1)$ steps unchanged. Then we
arrive at lattice point $(s,n-2s+s)=(s,n-s)$ with steps in
$\set{(0,1),(1,1)}$ and by the third proof of Theorem
\ref{theorem:main}, there are $\binom{n-s}{s}_{2}$ such
paths. Hence,
\begin{align*}
\sum_{s=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n-s}{s}_{2} = F_{n+1},
\end{align*}
i.e., the sum of diagonal binomial coefficients yields a Fibonacci
number.
To continue on this, note that
\begin{align*}
\sum_{s=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n-s}{s}=\sum_{s=\lceil
\frac{n}{2}\rceil}^{n}\binom{s}{n-s},
\end{align*}
which can be shown, combinatorically,
by
summing over
the number of steps used.
We illustrate in the more general case of monotone paths
from $(0,0)$ to $(0,n)$ with steps in $\set{(0,1),(0,2),\ldots,(0,l)}$
for $l\ge 1$.
As above,
there are $F_{n+1,l}$ such paths, where $F_{n,l}$
denotes the the $n$-th $l$-generalized Fibonacci number
\cite{flores}, i.e., $F_{n,l}=F_{n-1,l}+\cdots+F_{n-l,l}$. Replace all
$s_i$ $(0,i)$ steps, $i=2,\ldots,l$, by a
step $(i-1,1)$, leaving the $s_1$ $(0,1)$ steps unchanged. This yields a
path from $(0,0)$ to $(\alpha,\beta)=\bigl(
(2-1)s_2+\cdots+(l-1)s_l,s_1+\cdots+s_l\bigr)$
with steps in $\set{(0,1),(1,1),\ldots,(l-1,1)}$. Now, note that
$s_1+2s_2+\cdots+ls_l=n$ and denote by $k:=s_1+\cdots+s_l$ the total number
of steps. Then
$(\alpha,\beta)=(n-s_1-(s_2+\cdots+s_l),k)=(n-k,k)$. Surely, there can be at
most $n$ steps and there must be at least $\lceil\frac{n}{l}\rfloor$
steps; thus,
\begin{align*}
\sum_{k=\lceil
\frac{n}{l}\rceil}^{n}\binom{k}{n-k}_{l} =
F_{n+1,l}.
\end{align*}
Of course, this identity can more easily be seen by noting that
$\binom{k}{n-k}_{l}=c_{\set{1,\ldots,l}}(n,k)$ and, certainly, paths from
$(0,0)$ to $(0,n)$ with steps in $\set{(0,1),\ldots,(0,l)}$ are
equivalent to compositions of $n$
with an arbitrary number of parts in
$\set{1,\ldots,l}$.\footnote{The identity
$\binom{k}{n-k}_{l}=c_{\set{1,\ldots,l}}(n,k)$ is seen as
follows. By Example \ref{example:ordinary},
$c_{\set{0,\ldots,l}}(n,k)=\binom{k}{n}_{l+1}$. Subtracting $1$ from
each part in a composition $\pi\in\struct{C}_{\set{1,\ldots,l}}(n,k)$
yields a composition of $n-k$ with $k$ parts, each between $0$ and $l-1$.}
\end{example}
Finally, we mention that many interesting properties of extended
binomial
coefficients can very elegantly be proven by referring to our
established combinatorial interpretation of them (Theorem
\ref{theorem:main}). We exemplify with the Vandermonde
convolution (Example \ref{example:vandermonde}), Fielder and
Alford's recursion
(Example \ref{example:fielder}), and two further results (Examples
\ref{example:inclusion} and \ref{example:inclusion2}). We assume that
$f(s)\in\nn$
for all
$s\in S$.
\begin{example}[Combinatorial proof of Vandermonde identity]\label{example:vandermonde}
Let $j\in\nn$, $0\le j\le k$, be fixed. Consider the set
\begin{align}\label{eq:union}
\struct{D}:=\bigcup_{m=0}^n \struct{D}_{S,f}(m,j)\times \struct{D}_{S,f}(n-m,k-j),
\end{align}
where we denote by $\struct{D}_{S,f}(n,k)$ the set of all $S$-restricted
$f$-weighted integer compositions of $n$ with $k$ parts and
where we identify the pair
$\bigl((\pi_1,\ldots,\pi_j),(\tilde{\pi}_1,\ldots,\tilde{\pi}_{k-j}))$
with the tuple
$(\pi_1,\ldots,\pi_j,\tilde{\pi}_1,\ldots,\tilde{\pi}_{k-j})$.
Obviously, the union in \eqref{eq:union} is over pairwise disjoint
sets. Moreover,
each $\pi\in\struct{D}$ is an $f$-weighted integer composition of $n$
with $k$
parts $p\in S$. Conversely, let
$\pi=(\pi_1,\ldots,\pi_j,\pi_{j+1},\ldots,\pi_k)\in
\struct{D}_{S,f}(n,k)$. Then $(\pi_1,\ldots,\pi_j)\in
\struct{D}_{S,f}(m,j)$ for some $m$ between $0$ and $n$ and
$(\pi_{j+1},\ldots,\pi_k)\in \struct{D}_{S,f}(n-m,k-j)$. Hence,
$\pi\in\struct{D}$. Therefore
\begin{align*}
d_{S,f}(n,k)=\abs{\struct{D}_{S,f}(n,k)}=\abs{\struct{D}}=\sum_{m=0}^n
d_{S,f}(m,j)\cdot d_{S,f}(n-m,k-j).
\end{align*}
\end{example}
\begin{example}[Combinatorial proof of Fielder and Alford's result]\label{example:fielder}
Note that in writing $n=\pi_1+\cdots+\pi_k$ with $
\pi_i\in S$, we can use integer $l\in S$ among the $\pi_i$'s either $0$
times, $1$ time,
$\ldots$, $\lfloor \frac{n}{l}\rfloor$ times (and at most $k$ times;
e.g., for $l=0$). If we use $l$ $i$
times we are left with the problem of solving $n-li =
q_1+\cdots+q_{k-i}$ with $q_1,\ldots,q_{k-i}\in S\wo\set{l}$. Hence,
accounting for all orders of the $i$ parts among $k$ and for all
possible colorings,
\begin{align*}
d_{S,f}(n,k) &=
\sum_{i=0}^{\min\set{k,\lfloor
\frac{n}{l}\rfloor}}f(l)^i\binom{k}{i}d_{S\wo\set{l},f}(n-li,k-i).
\end{align*}
Using $S=\set{0,1,\ldots,l}$ and $f(s)=1$ for all $s\in S$, we
obtain Fielder and Alford's \cite{fielder} result
about the outstanding position of the binomial triangle among
the class of multinomial triangles (i.e., the following recursion may
be used iteratively, so that $\binom{k}{n}_{l+1}$ has the
representation as a convolution of binomial coefficients),
\begin{align*}
\binom{k}{n}_{l+1}=\sum_{i=0}^{\min\set{k,\lfloor
\frac{n}{l}\rfloor}}\binom{k}{i}\binom{k-i}{n-il}_l.
\end{align*}
\end{example}
\begin{example}\label{example:inclusion}
For $S=\set{0,1,\ldots,l}$ and $f(s)=1$ for all $s\in S$,
we also find the following noteworthy representation of
$\binom{k}{n}_{l+1}$ by applying the inclusion/exclusion formula to
the sets $A_i = $ ``set of all $\set{0,1,\ldots,l}$-restricted
integer compositions
of $n$ with $k$ parts that have a positive part
$\pi_i$''. Obviously, if $n>0$,
$\struct{C}_{\set{0,1,\ldots,l}}(n,k)=A_1\cup\cdots\cup A_k$, so
that, by the inclusion/exclusion formula
\begin{align*}
c_{\set{0,1,\ldots,l}}(n,k) = \abs{A_1\cup\cdots\cup A_k} =
\sum_{\overset{B\subseteq
[k]}{B\neq\emptyset}}(-1)^{\length{B}-1}\abs{\bigcap_{j\in
B}A_j}.
\end{align*}
We find
\begin{align*}
\abs{\bigcap_{j\in B}A_j} &=
\sum_{i=0}^n
c_{\set{1,\ldots,l}}(i,\abs{B})\cdot
c_{\set{0,\ldots,l}}(n-i,k-\abs{B}) \\ &=
\sum_{i=0}^n
c_{\set{0,\ldots,l-1}}(i-\abs{B},\abs{B})\cdot c_{\set{0,\ldots,l}}(n-i,k-\abs{B}),
\end{align*}
so that by applying Examples \ref{example:fielder} and
\ref{example:vandermonde}, we finally arrive at
\begin{align*}
\binom{k}{n}_{l+1} =
\sum_{j\in[k],\nu\in[0,k]}(-1)^{j-1}\binom{k}{j}\binom{k-j}{\nu}\binom{k-\nu}{n-j-\nu
l}_l,
\end{align*}
where we use the notation $[k]=\set{1,\ldots,k}$ and
$[0,k]=\set{0,1,\ldots,k}$.
\end{example}
\begin{example}\label{example:inclusion2}
Relatedly, consider the formula for the number $c_S(n)$ of compositions of
$n$ with arbitrarily many parts, each in the set $S=\set{1,\ldots,l}$,
given in \cite{flajolet}, p.\ 43, derived from
the generating function
for $c_S(n)$, $c_S(x)=\frac{1}{1-\sum_{s\in S}x^s}$ (cf.\ Corollary
\ref{cor:1}),
\begin{align*}
c_S(n)=\sum_{k\ge 0,j\ge 0}(-1)^j\binom{k}{j}\binom{n-lj-1}{k-1},
\end{align*}
whence the corresponding formula for fixed number $k$ of parts is,
\begin{align}\label{eq:flajolet}
c_S(n,k) = \sum_{j\ge 0}(-1)^j\binom{k}{j}\binom{n-lj-1}{k-1}.
\end{align}
The beauty of this formula, also given in
\cite{fielder}, is that it
directly links integer
compositions with parts in $S=\set{1,\ldots,l}$, or extended binomial
coefficients, to ordinary binomial coefficients. A combinatorial
proof is as follows. Let $A_i$ be the set ``$\mathbb{P}$-restricted
compositions of $n$ with
$k$ parts such that part $i$ is strictly
greater than $l$'', and denote by $A_i^c$ its complement. Then the set of $S$-restricted integer
compositions of $n$ with $k$ parts is given as
\begin{align*}
c_S(n,k)=\abs{A_1^c\cap\cdots\cap A_k^c}.
\end{align*}
For any subset of indices $B\subseteq[k]$, we find that
$\abs{\bigcap_{j\in B}A_j}$ is the set of
$\mathbb{P}$-restricted compositions of $n$ with $k$ parts where the
parts indexed by $B$ are strictly greater than $l$. Subtracting $l$
from these parts yields
\begin{align*}
\abs{\bigcap_{j\in B}A_j} = c_{\mathbb{P}}(n-\abs{B}l,k) =
\binom{n-l\abs{B}-1}{k-1},
\end{align*}
where the last equality is elementary (see,
e.g., \cite{flajolet}). Applying the principle of
inclusion/exclusion yields \eqref{eq:flajolet}. The corresponding
formula when $S$ is $\set{0,1,\ldots,l}$ is
\begin{align*}
\binom{k}{n}_{l+1}=\sum_{j\ge 0} (-1)^j\binom{k}{j}\binom{n+k-(l+1)j-1}{k-1}.
\end{align*}
\end{example}
\section{Conclusion}
In the current work, we have investigated the quantities
\begin{align*}
\sum_{\pi}f(\pi_1)\cdots f(\pi_k),
\end{align*}
showing that they precisely yield the
extended binomial coefficients $\binom{k}{n}_{(f(s))_{s\in S}}$.
There are various ways to extend this work. One way to do so is to
derive further
identities, in addition to those investigated in \cite{fahssi}
and in the
current exposition, of the coefficients $\binom{k}{n}_{(f(s))_{s\in
S}}$, based, for instance, on their
combinatorial interpretation as representing
(the total weight of all)
$S$-restricted $f$-weighted
integer compositions, colored monotone lattice paths, or, most
intriguingly, as denoting the distributions of independent
identically distributed discrete random variables. As generalizations of
the binomial coefficients, it is quite likely that many interesting
of the myriad of known properties (cf., e.g., \cite{gould}) of
binomial coefficients extend to
the coefficients $\binom{k}{n}_{(f(s))_{s\in S}}$. Fahssi
\cite{fahssi} generalizes
the top ten identities from \cite{knuth2}, and we have
investigated further relationships (summarized in Table \ref{table:identities}),
but many more results (e.g., concerning further identities, extended
binomial congruences, etc.) are awaiting.
\begin{table}[!htb]
\renewcommand*\arraystretch{1}
\centering
{\footnotesize
\begin{tabular}{c|c}
\textbf{Binomial} & \textbf{Extended binomial}\\ \hline\hline
$\sum_{n=0}^k n\binom{k}{n}=k2^{k-1}$ & $\sum_{n\ge 0}
n\binom{k}{n}_{(f(s))_{s\in S}} = kc^{k-1}\cdot \bigl(\sum_{s\in S}sf(s)\bigr)$\\
$\sum_{n=0}^k n^2
\binom{k}{n} = (k+k^2)2^{k-2}$ & $\sum_{n\ge 0}
n^2\binom{k}{n}_{(f(s))_{s\in S}}
=
kc^{k-2}\Bigl(
c\sum_{s\in S}s^2f(s)+(k-1)\bigl(\sum_{s\in S}sf(s)\bigr)^2
\Bigr)$\\
$\binom{k}{n}=\frac{k+1-n}{n}\binom{k}{n-1}$ & $\binom{k}{n}_{(f(s))_{s\in S}} = \frac{1}{f(0)}\sum_{s\in S\wo\set{0}}
\Bigl(\frac{k+1}{n}s-1\Bigr)f(s)\binom{k}{n-s}_{(f(s))_{s\in S}}$ \\
$\binom{k}{n}=\binom{k}{n}$ & $ \binom{k}{n}_{(f(s))_{s\in S}} =
\sum_{i=0}^{\min\set{k,\lfloor
\frac{n}{l}\rfloor}}f(l)^i\binom{k}{i}\binom{k-i}{n-li}_{(f(s))_{s\in
S\wo\set{l}}}$ \\
$\sum_{k=\lceil n/2\rceil}^n \binom{k}{n-k}=F_{n+1}$ &
$\sum_{k=\lceil n/l\rceil}^n \binom{k}{n-k}_l=F_{n+1,l}$\\
$\binom{k}{n}=\sum_{\nu=0}^{n-1}(-1)^{n-\nu-1}\binom{k}{n-\nu}\binom{k+\nu-n}{\nu}$
& $\binom{k}{n}_{l+1} =
\sum_{j\in[k],\nu\in[0,k]}(-1)^{j-1}\binom{k}{j}\binom{k-j}{\nu}\binom{k-\nu}{n-j-\nu
l}_l$\\
$\binom{k}{n}=\sum_{j\ge 0}
(-1)^j\binom{k}{j}\binom{n+k-2j-1}{k-1}$ &
$\binom{k}{n}_{l+1}=\sum_{j\ge 0}
(-1)^j\binom{k}{j}\binom{n+k-(l+1)j-1}{k-1}$\\
$\binom{k}{k/2}\sim \frac{2^{k+1}}{\sqrt{2\pi k}}$ &
$\binom{k}{kl/2}_{l+1}\sim \frac{(l+1)^k}{\sqrt{2\pi
k\frac{(l+1)^2-1}{12}}}$ \\
$[\binom{k}{n}] =
\begin{cases}
[0], & \text{if $k$ even and $n$ odd};\\
[\binom{\lfloor
k/2\rfloor}{\lfloor n/2\rfloor}], &
\text{otherwise.}
\end{cases}$
& $[\binom{k}{n}_{l+1}] =
\begin{cases}
[0], & \text{if $k$ even and $n$ odd};\\
[\binom{k/2}{n/2}_{l+1}], & \text{if $k$ even and
$n$ even};\\
\sum_{i=0}^{\lfloor \frac{l-r(n)}{2}\rfloor}[\binom{\lfloor
k/2\rfloor}{\lfloor n/2\rfloor-i}_{l+1}], &
\text{otherwise.}
\end{cases}$\\
\end{tabular}
}
\caption{List of properties of extended binomial coefficients
derived in the current work and not included in
\cite{fahssi}. The constant $c$ is $\sum_{s\in S}f(s)$. By $[x]$
we denote the parity of $x\in\nn$; moreover, $r(n)$ is as defined
in Example \ref{example:parity}.}
\label{table:identities}
\end{table}
Furthermore, in the current work, we have considered the
quantities
\begin{align*}
\sum_{\pi}
f_1(\pi_1)\cdots f_j(\pi_j)\cdot f(\pi_{j+1})
\cdots f(\pi_k),
\end{align*}
which correspond to independently but not identically distributed
random variables. The most general objects to consider, within this
framework, would be the quantities,
\begin{align*}
\sum_{\pi} F(\pi_1,\ldots,\pi_k),
\end{align*}
which, by identity \eqref{eq:4}, correspond to the distribution of
the sum of $k$ (possibly dependent and not identically distributed) random
variables. For example, Carlitz compositions, introduced in
\cite{carlitz}, require
dependence between
parts of an integer composition, namely, that two adjacent parts must be
different (see also \cite{bender1} and \cite{bender3} for such, and
more general, local dependencies), which could be described by
quantities such as
\begin{align*}
\sum_{\pi} g(\pi_1,\pi_2)\cdot g(\pi_2,\pi_3)\cdots
g(\pi_{k-1},\pi_k),
\end{align*}
with
$g(m,l)=1$ if and only if $m\neq l$. This is the situation of
the distribution of the sum of $k$ dependent discrete random
variables, where the dependence
satisfies the `Markov' property that random variable $X_{i+1}$ is
independent of the variables
$X_{i-r}$ for $r\ge 1$, given knowledge of $X_{i}$. Analysis of
these distributions promises to yield new insight into the counting of
various types
of restricted weighted integer compositions, where the
restrictions/weights include
dependencies between individual parts,
another valuable extension of the situation
considered
in this work.
\section{Acknowledgements}
The author would like to thank the anonymous referee for many helpful
comments.
\begin{thebibliography}{}
\bibitem{agarwal:2000} A. K. Agarwal, $n$-color compositions,
\emph{Indian J. Pure Appl. Math.} \textbf{31} (2000), 1421--1427.
\bibitem{andrews} G. E. Andrews, Euler's `exemplum memorabile
inductionis fallacis' and $q$-trinomial
coefficients, \emph{J. Amer. Math. Soc.} \textbf{3} (1990), 653-669.
\bibitem{balas} K. Balasubramanian, R. Viperos, and N. Balakrishnan,
Some discrete distributions related to extended Pascal
triangles, \emph{Fibonacci Quart.} \textbf{33} (1995), 415--425.
\bibitem{hitczenko} C. Banderier and P. Hitczenko, Enumeration and
asymptotics of restricted compositions having the same number of
parts, \emph{Discrete Appl. Math.} \textbf{160} (2012), 2542--2554.
\bibitem{bender1}
E. A. Bender and E. R. Canfield, Locally restricted compositions
I. Restricted adjacent
differences, \emph{Electron. J. Combin.} \textbf{12} (2005), Paper
R57. Available at
\url{http://www.combinatorics.org/Volume_12/Abstracts/v12i1r57.html}.
\bibitem{bender2} E. A. Bender and E. R. Canfield, Locally restricted
compositions II. General restrictions and infinite matrices,
\emph{Electron. J. Combin.} \textbf{16} (2009), Paper
R108. Available at
\url{http://www.combinatorics.org/Volume_16/Abstracts/v16i1r108.html}.
\bibitem{bender3} E. A. Bender and E. R. Canfield, Locally restricted
compositions III. Adjacent-part periodic inequalities.
\emph{Electron. J. Combin.}, \textbf{17} (2010), Paper
R145. Available at
\url{http://www.combinatorics.org/Volume_17/Abstracts/v17i1r145.html}.
\bibitem{bender4} E. A. Bender, E. R. Canfield, and Z. Gao,
Locally restricted compositions IV. Nearly free large
parts and gap-freeness. \emph{Electron. J. Combin.}, \textbf{19} (2012), Paper
P14. Available at
\url{http://www.combinatorics.org/Volume_19/Abstracts/v19i4p14.html}.
\bibitem{caiado}
C. C. S. Caiado and P. N. Rathie, Polynomial coefficients and
distribution of the sum of discrete uniform variables, in
A. M. Mathai, M. A. Pathan, K. K. Jose, and J. Jacob, eds., \emph{Eighth
Annual Conference of the Society of Special Functions and their
Applications}, Pala, India, Society for Special Functions and their
Applications, 2007.
\bibitem{carlitz} L. Carlitz, Restricted compositions,
\emph{Fibonacci Quart.} \textbf{14} (1976), 254--264.
\bibitem{chinn} P. Chinn and S. Heubach, $(1,k)$-compositions,
\emph{Congr. Numer.} \textbf{164} (2003), 183--194.
\bibitem{chinn2}
P. Chinn and S. Heubach, Compositions of $n$ with no occurrence of
$k$, in \emph{Proceedings of the Thirty-Fourth Southeastern International
Conference on Combinatorics, Graph Theory and Computing}, vol.
164, 2003, pp. 33--51.
\bibitem{comtet} L. Comtet, \emph{Advanced Combinatorics},
D. Reidel Publishing Company, 1974.
\bibitem{moivre} A. De Moivre, \emph{The Doctrine of Chances:
or, A Method of Calculating the Probabilities of Events in
Play}, 3rd ed., Millar, 1756, reprint, Chelsea, 1967.
\bibitem{depril} N. De Pril, Recursions for convolutions of
arithmetic distributions, \emph{Astin Bull.} \textbf{15} (1985),
135--139.
\bibitem{eger3} S. Eger, Asymptotic normality of integer
compositions inside a rectangle, preprint,
\url{http://arxiv.org/abs/1203.0690}.
\bibitem{fahssi} N.-E. Fahssi, The polynomial triangles
revisited, preprint, \url{http://arxiv.org/abs/1202.0228}.
\bibitem{fielder}
D. C. Fielder and C. O. Alford, Pascal's triangle: top gun or just
one of the gang?, in G. E. Bergum, A. N. Philippou, and
A. F. Horadam, eds., \emph{Applications of
Fibonacci Numbers}, Kluwer, 1991, pp. 77--90.
\bibitem{flajolet} P. Flajolet and R. Sedgewick, \emph{Analytic
Combinatorics}, Cambridge University Press, 2009.
\bibitem{flores}
I. Flores, $k$-generalized Fibonacci numbers, \emph{Fibonacci
Quart.} \textbf{5} (1967), 258--266.
\bibitem{gould} H. W. Gould, \emph{Combinatorial Identities: A
Standardized Set of Tables Listing 500 Binomial Coefficient
Summations}, West Virginia University Press, 1972.
\bibitem{knuth2} R. L. Graham, D. E. Knuth, and O. Patashnik, \emph{Concrete
Mathematics}, Addison-Wesley, 1994.
\bibitem{guo:2012} Y.-H. Guo, Some $n$-color
compositions, \emph{J. Integer Seq.} \textbf{15} (2012).
\bibitem{heubach} S. Heubach and T. Mansour, Compositions of
$n$ with parts in a set, \emph{Congr. Numer.} \textbf{164} (2004),
127--143.
\bibitem{jaklic} G. Jakli\v{c}, V. Vitrih, and E. \v{Z}agar, Closed
form formula for the number of restricted compositions,
\emph{Bull. Aust. Math. Soc.} \textbf{81}
(2010), 289--297.
\bibitem{knuth} D. E. Knuth, \emph{The Art of Computer
Programming, Vol 2, Seminumerical Algorithms}, Addison-Wesley, 1969.
\bibitem{malandro} M. E. Malandro, Asymptotics for restricted
integer compositions, preprint, \url{http://arxiv.org/pdf/1108.0337v1}.
\bibitem{narang:2006} G. Narang and A. K. Agarwal, $n$-color
self-inverse compositions, \emph{Proc. Indian
Acad. Sci. Math. Sci.} \textbf{116} (2006), 257--266.
\bibitem{narang:2008} G. Narang and A. K. Agarwal, Lattice paths
and $n$-colour compositions, \emph{Discrete Math.} \textbf{308} (2008),
1732--1740.
\bibitem{buhlmann} H. H. Panjer, The aggregate claims
distribution and stop-loss reinsurance, \emph{Transactions of the
Society of Actuaries} \textbf{32} (1980), 537--538.
\bibitem{panjer} H. H. Panjer, Recursive evaluation of a
family of compound distributions, \emph{Astin Bull.} \textbf{12} (1981),
22--26.
\bibitem{sagan} B. E. Sagan, Compositions inside a rectangle and
unimodality, \emph{J. Algebraic Combin.} \textbf{29} (2009),
405--411.
\bibitem{schmutz} E. Schmutz and C. Shapcott, Part-products
of $S$-restricted integer compositions, \emph{Appl. Anal.
Discrete Math.}, to appear. Available at
\url{http://pefmath.etf.rs/accepted/rad1442.pdf}.
\bibitem{shapcott:2012} C. Shapcott, $\struct{C}$-color compositions
and palindromes, \emph{Fibonacci Quart.} \textbf{50} (2012),
297--303.
\bibitem{shapcott2} C. Shapcott, Part-products of $1$-free integer
compositions, \emph{Electron. J. Combin.} \textbf{18} (2011), \#P235.
\bibitem{sloane} N. J. A. Sloane, ed., \emph{The On-Line Encyclopedia
of Integer Sequences}, \url{http://oeis.org}.
\bibitem{walsh} D. P. Walsh, Equating Poisson and normal
probability functions to derive Stirling's formula,
\emph{Amer. Statist.} \textbf{49} (1995), 270--271.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2013 {\it Mathematics Subject Classification}:
Primary 05A10; Secondary 05A17, 60G50.
\noindent \emph{Keywords: }
integer composition, extended binomial coefficient, polynomial
coefficient, sum of discrete random variables.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequence
\seqnum{A002426}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received April 16 2012;
revised versions received April 23 2012; September 7 2012; October 13 2012; January 3 2013.
Published in {\it Journal of Integer Sequences}, January 4 2013.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}