\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}