Restricted Weighted Integer Compositions and Extended Binomial Coefficients

Steffen Eger School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 USA

                   seger@cs.cmu.edu

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.

1 Introduction

An integer composition of a nonnegative integer n with k summands, or 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 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., [11, 12, 24, 25, 32] and for probabilistic results on such compositions see [4, 6, 7, 8, 27, 33, 35]. A classical result in combinatorics is then that the number of Srestricted integer compositions of n with k parts is given by the coefficient of x^{n} of the polynomial or power series (see, e.g., [24])

(∑_{s∈S} x^{s})^{k}.

These coefficients, in turn, which generalize the ordinary binomial coefficients, and are usually called polynomial coefficients or extended binomial coefficients, exhibit fascinating mathematical properties, closely resembling those of binomial coefficients. Although they appeared explicitly as far back as De Moivre’s The Doctrine of Chances [14] in 1756, their systematic study has apparently only recently been investigated (cf. [17]). In the present paper, we give a complete characterization of extended binomial coefficients, over commutative rings 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 1). 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 1 and Remark 4). Colored integer compositions, in turn, have recently been studied (cf. [1, 23, 28, 29]), for example, in the situation when part s ∈ S comes in s different colors (‘n-colored compositions’) and, simultaneously with, but independently of the present paper, when part s ∈ S may take on c_{s} ∈ C different colors [34] (‘C-colored compositions’), where c_{s} is a nonnegative integer. We term the generalization of these two concepts considered in the present work analogously f-weighted compositions, and, under restrictions on part sizes, S-restricted f-weighted compositions.

We give three proofs of the named simple result, Theorem 1, 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 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 {0, 1, …, l} for some l > 0; our proof is inspired, too, by [3] and [9], 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 2) of extended binomial coefficients.

After having proven our main theorem, we specify, in Section 6, a variety of applications of our main result, which indicate the generality of our approach. We structure our applications in three parts:

• 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 {0, 1, …, l}; where S = ℕ\{s_{0}} [12], 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 [33, 35]; 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.

• 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 closedform 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.

• 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 fweighted integer compositions.

2 Notation and preliminaries

By ℤ we denote the set of integers, by ℕ we denote the set of nonnegative integers and by ℙ we denote the set of positive integers. Then, an integer composition of a nonnegative integer n ∈ ℕ is a tuple π = (π_{1}, …, π_{k}) ∈ ℕ^{k}, k ∈ ℕ, of nonnegative integers such that

n = π_{1} + ⋯ + π_{k},

where the π_{i} are called parts. We call an integer composition of n S-restricted (cf. [27]) for a finite subset S of ℕ if all parts satisfy π_{i} ∈ S. We denote the set of S-restricted integer compositions by C_{S}(n, k) and by c_{S}(n, k) we denote its size, c_{S}(n, k) = |C_{S}(n, k)|.

Furthermore, we call a tuple of nonnegative integers (λ_{1}, …, λ_{k}) ∈ ℕ^{k} where λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{k} an integer partition of n (‘unordered composition’) and analogously denote by P_{S}(n, k) the set of S-restricted integer partitions and by p_{S}(n, k) its size. Obviously, each Srestricted integer partition λ = (λ_{1}, …, λ_{k}) may be uniquely represented by a tuple (α_{s})_{s∈S} — α_{s}, α_{s} ∈ ℕ, denoting the multiplicity of s ∈ S in λ — where ∑_{s∈S} α_{s} = k and ∑_{s∈S} sα_{s} = n. We silently identify the two representations.

Next, let R = (R, +, ·, 0, 1) be a commutative ring with addition +, multiplication · and additive and multiplicative identities 0 and 1, respectively. Let f be a function f : S → R. In the current work, our interest lies, in particular, in the quantity

d_{S,f}(n, k) = ∑_{π=(π_{1},...,π_{k})∈C_{S}(n,k)} f(π_{1}) ⋯ f(π_{k}),  (1)

where, obviously, the summation symbol refers to the addition operation + in R, and likewise for multiplication ·.

We also remind the reader of the multinomial theorem. For m ∈ ℕ, x_{1}, …, x_{m} ∈ R, and k ∈ ℕ as above,

(x_{1} + ⋯ + x_{m})^{k} = ∑_{α_{1}+···+α_{m}=k^{α_{1}≥0,...,αm≥0}} \binom{k}{α_{1}, …, α_{m}}x_{1}^{α_{1}} ⋯ x_{m}^{α_{m}},  (2)

where \binom{k}{α_{1},...,α_{m}} are the respective multinomial coefficients [3], which, for α_{s} ∈ ℕ, s ∈ S, and k = ∑_{s∈S} α_{s}, denote the number of arrangements of k objects of |S| different types — α_{s} of type s for s ∈ S — in a sequence of length k.

Finally, for S, k, and n as above, we denote the coefficient, called polynomial coefficient or extended binomial coefficient in the literature (cf. [3, 9, 13, 17]), of x^{n} in the expansion of the univariate polynomial (∑_{s∈S} f(s)x^{s})^{k} ∈ R[x] as \binom{k}{n}_{(f(s))_{s∈S}}. More precisely, we let

\binom{k}{n}_{(f(s))_{s∈S}} = [x^{n}](∑_{s∈S} f(s)x^{s})^{k}  (3)

where we use the standard notation [x^{n}]h(x) to denote the coefficient of x^{n} of the polynomial h(x) = ∑_{i} a_{i}x^{i}, i.e., [x^{n}]h(x) = a_{n}.

3 Main theorem

Theorem 1. With notation as in Section 2,

d_{S,f}(n, k) = \binom{k}{n}_{(f(s))_{s∈S}}.

4 Proofs of the main theorem

Proof of Theorem 1, 1. Rewriting (1) in terms of partitions, we find that d_{S,f} allows the following representation, because of commutativity of multiplication in R and the combinatorial interpretation of multinomial coefficients as above,

d_{S,f}(n, k) = ∑_{(α_{s})_{s∈S}∈P_{S}(n,k)} \binom{k}{(α_{s})_{s∈S}} ∏_{s∈S} f(s)^{α_{s}} = ∑_{∑_{s} αs=k ; ∑_{s} sα_{s}=n^{αs≥0}} \binom{k}{(α_{s})_{s∈S}} ∏_{s∈S} f(s)^{α_{s}}. (4)

On the other hand, substituting x_{s} = f(s)x^{s}, s ∈ S, in the multinomial theorem (2), we find that

(∑_{s∈S} f(s)x^{s})^{k} = ∑_{∑_{s} α_{s}=k^{αs≥0}} \binom{k}{(α_{s})_{s∈S}}(∏_{s∈S} f(s)^{α_{s}})x^{∑_{s} sα_{s}}.  (5)

Thus,

\binom{k}{n}_{(f(s))_{s∈S}} = [x^{n}](∑_{s∈S} f(s)x^{s})^{k} = d_{S,f}(n, k)

as required.

For our next proof, we assume that R is the field of real numbers, that f(s) ≥ 0 for all s ∈ S and that ∑_{s∈S} f(s) ≠ 0. We also make use of the following observation. If

X_{1} + ⋯ + X_{k} = n,

where X_{1}, …, 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,

P [X_{1} + ⋯ + X_{k} = n] = ∑_{π=(π_{1},...,π_{k})∈C_{S}(n,k)} P [X_{1} = π_{1}, …, X_{k} = π_{k}],  (6)

for every suitable probability measure P.

Proof of Theorem 1, 2. Let X_{i}, i = 1, …, 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 ∈ S is p(s) = \frac{f(s)}{∑_{s′∈S} f(s′)}. We derive the distribution of the sum X_{1} + ⋯ + X_{k} in two ways, first by considering its probability generating function (pgf) and then by a combinatorial argument using (6).

Consider the pgf G_{X_{i}}(x) = ∑_{n=0}^{∞} p(n)x^{n} of X_{i}. Because X_{1}, …, X_{k} are independent, we have by elementary facts about pgf’s that

G_{X_{1}+···+X_{k}}(x) = G_{X_{1}}(x) ⋯ G_{X_{k}}(x) = (∑_{s∈S} p(s)x^{s})^{k} = ∑_{n≥0} \binom{k}{n}_{(p(s))_{s∈S}}x^{n}.

Therefore,

P [X_{1} + ⋯ + X_{k} = n] = \frac{G_{X_{1}+···+X_{k}}^{(n)}(0)}{n!} = \frac{n!}{n!}\binom{k}{n}_{(p(s))_{s∈S}} = \binom{k}{n}_{(p(s))_{s∈S}},  (7)

where by G_{X}^{(n)}(0) we denote the n-th derivative of G_{X}, evaluated at zero.

On the other hand, by (6) and using independence of X_{1}, …, X_{k}, P [X_{1} + ⋯ + X_{k} = n] is given by,

\begin{aligned}P [X_{1} + ⋯ + X_{k} = n] & = ∑_{π=(π_{1},...,π_{k})∈C_{S}(n,k)} P [X_{1} = π_{1}] ⋯ P [X_{k} = π_{k}] \\ & = ∑_{π∈C_{S}(n,k)} p(π_{1}) ⋯ p(π_{k}) = d_{S,p}(n, k). \end{aligned}  (8)

Thus, equating (7) and (8) yields d_{S,p}(n, k) = \binom{k}{n}_{(p(s))_{s∈S}}, but this suffices, since, as can easily be verified by factoring out the normalizer c = ∑_{s′∈S} f(s′),

d_{S,f}(n, k) = c^{k}d_{S,p}(n, k) = c^{k}\binom{k}{n}_{(p(s))_{s∈S}} = \binom{k}{n}_{(f(s))_{s∈S}}.

For our final proof, we use the following inductive characterizations of extended binomial coefficients, which generalize the corresponding properties of ordinary binomial coefficients.

Lemma 2. With notation as in Section 2,

(i) \binom{k}{n}_{(f(s))_{s∈S}} = ∑_{μ+ν=n} \binom{j}{μ}_{(f(s))_{s∈S}} \binom{k − j}{ν}_{(f(s))_{s∈S}},

(ii) \binom{k}{n}_{(f(s))_{s∈S}} = ∑_{s∈S} f(s)\binom{k − 1}{n − s}_{(f(s))_{s∈S}},

where 0 ≤ j ≤ k. For (ii), we have the ‘initial condition’ \binom{0}{0}_{(f(s))_{s∈S}} = 1.

Figure 1: The eight colored paths from (0, 0) to (3, 2) with steps in {(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.

Proof. As in the ordinary binomial case, the Vandermonde convolution (i) follows from equating coefficients on both sides of (∑_{s∈S} f(s)x^{s})^{k} = (∑_{s∈S} f(s)x^{s})^{j}(∑_{s∈S} f(s)x^{s})^{k−j}. The addition/induction property (ii) is a special case of (i) with j = 1. See also [17].

For our final proof of Theorem 1, let R be the ring of integers and f(s) ∈ ℕ, in which case Fahssi [17] refers to the array of extended binomial coefficients as arithmetical polynomial triangle.

Proof of Theorem 1, 3. Consider two-dimensional monotone colored lattice paths from (0, 0) to (n, k) as illustrated in Figure 1, i.e., paths in the lattice ℤ^{2} from (0, 0) to (n, k) in which only steps (a, b) for a ≥ 0, b ≥ 0, are allowed and each step r = (a, b) comes in g(r), g(r) ∈ ℕ, different colors. If R ⊆ ℕ^{2}\{(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,

T_{R,g}(i, j) = ∑_{r=(a,b)∈R} g(r)T_{R,g}(i − a, j − b),  (9)

with T_{R,g}(0, 0) = 1 and T_{R,g}(i, j) = 0 for i < 0 or j < 0. Now consider R = {(s, 1) | s ∈ S} (‘simple steps’) and g((s, 1)) = f(s). Then T_{R,g}(n, k) satisfies, thus,

T_{R,g}(n, k) = ∑_{s∈S} f(s)T_{R,g}(n − s, k − 1),

with T_{R,g}(0, 0) = 1 and is hence, considering Lemma 2, precisely the number \binom{k}{n}_{(f(s))_{s∈S}}.

On the other hand, the number T_{R,g}(n, k) of monotone colored lattice paths with steps in R = {(s, 1) | s ∈ S} and g((s, 1)) = 1 is obviously the number c_{S}(n, k) since

(π_{1}, …, π_{k}) ↦ ((π_{1}, 1), …, (π_{k}, 1))

with π_{1}, …, π_{k} ∈ S represents an obvious bijection between 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) ∈ ℕ, T_{R,g}(n, k) analogously retrieves general d_{S,f}(n, k).

5 Discussion

Remark 3. We first note that the assumption of finiteness of S, which we have made throughout, is not a restriction of generality, since, e.g., C_{S}(n, k) = C_{S∩{0,1,...,n}}(n, k) so that our main result also holds for infinite S, when we, e.g., define \binom{k}{n}_{(f(s))_{s∈S}} by \binom{k}{n}_{(f(s))_{s∈S∩\{0,1,...,n\}}} in this case. Also note that, e.g., (6) holds whether or not S is finite.

Remark 4. Next, we remark that by the third proof of Theorem 1, the quantities d_{S,f}(n, k), with f(s) ∈ ℕ for all s ∈ S, have the interpretation of counting colored monotone lattice paths with steps in R = {(s, 1) | s ∈ S}. Thus, by the trivial correspondence of such paths and restricted integer compositions, d_{S,f}(n, k) counts the number of S-restricted C-color compositions [34], where C = (f(s))_{s∈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 1, we call compositions with arbitrary f, 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.

We also note the following immediate consequences of Theorem 1, the first two of which are shown in [34].

Corollary 5. (a) The quantity d_{S,f}(n) = ∑_{k≥0} d_{S,f}(n, k) is given by

[x^{n}]\frac{1}{1 − ∑_{s∈S} f(s)x^{s}} .

For ℕ-valued f, d_{S,f}(n) counts the total number of S-restricted f-weighted compositions of n.

(b) The quantity ∑_{k≥0} kd_{S,f}(n, k) is given by

[x^{n}]\frac{∑_{s∈S} f(s)x^{s}}{(1 − ∑_{s∈S} f(s)x^{s})^{2}} .

For ℕ-valued f, ∑_{k≥0} kd_{S,f}(n, k) counts the total number of parts over all S-restricted f-weighted compositions.

(c) The quantity ∑_{n≥0} nd_{S,f}(n, k) is given by

k(∑_{s∈S} f(s))^{k−1} · (∑_{s∈S} sf(s)).

If f is a probability distribution, ∑_{n≥0} nd_{S,f}(n, k) is the expected value of the sum of the underlying random variables.^{1}

(d) The quantity ∑_{n≥0} n^{2}d_{S,f}(n, k) is given by

k(∑_{s∈S} f(s))^{k−2}(∑_{s∈S} f(s) ∑_{s∈S} s^{2}f(s) + (k − 1)(∑_{s∈S} sf(s))^{2}).

If f is a probability distribution, ∑_{n≥0} n^{2}d_{S,f}(n, k) is the second moment of the sum of the underlying random variables.

Proof. Properties (a) and (b) immediately follow from the characterization of d_{S,f}(n, k) given in Theorem 1 and well-known explicit formulae for geometric series. Property (c) follows from differentiating (∑_{s∈S} f(s)x^{s})^{k} = ∑_{n≥0} \binom{k}{n}_{(f(s))_{s∈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 1,

∑_{n≥0} nd_{S,f}(n, k) = ∑_{n≥0} nc^{k}d_{S,p}(n, k) = (∑_{s∈S} f(s))^{k} ∑_{n≥0} nd_{S,p}(n, k) = (∑_{s∈S} f(s))^{k} E[X_{1} + ⋯ + X_{k}]

= (∑_{s∈S} f(s))^{k}k(∑_{s∈S} sp(s)) = (∑_{s∈S} f(s))^{k−1}k(∑_{s∈S} sf(s)).

Property (d) follows from differentiating (∑_{s∈S} f(s)x^{s})^{k} = ∑_{n} \binom{k}{n}_{(f(s))_{s∈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} + ⋯ + X_{k} analogous as for (c).

Remark 6. Properties (c) and (d) in the above corollary read as

∑_{n=0}^{k} n\binom{k}{n} = k2^{k−1},  ∑_{n=0}^{k} n^{2}\binom{k}{n} = (k + k^{2})2^{k−2},

respectively, for ordinary binomial coefficients.

1Which, of course, due to linearity of the expectation operator and identical distribution of X_{1}, …, X_{k}, must equal k E[X_{1}], as verified by formula (c).

6 Applications

In this section, we discuss a variety of applications of Theorem 1 and its proofs. We thereby omit the choice of the ring R when it is clear from the context. We split our applications in three parts: Applications based on selected S and f (Section 6.1), applications based on selected S and where f is a probability measure (Section 6.2), which apparently yields the most interesting results, and applications for proving identities of the coefficients \binom{k}{n}_{(f(s))_{s∈S}} based on their combinatorial interpretation as representing restricted colored monotone lattice paths and restricted colored integer compositions (Section 6.3).

6.1 S-restricted f-weighted compositions for particular S and f

To start, we discuss quantities d_{S,f}(n, k) for selected S and f, thereby showing how Theorem 1 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 ∈ B and f(s) = 0 for s ∈ S\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}.

Example 7 (Compositions with no occurrence of s_{0}). Chinn and Heubach [12] 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 = ℙ and s_{0} = 1,

(d_{S,f}(n, k))_{n} = (\binom{k}{n}_{(0,1,1,1,...)})_{n} = (1, 3, 6, 10, 15, 21, 28, …)

for k = 3 and n = 6, 7, 8, 9, 10, 11, 12, 13, . . .. We note that the recursion which Chinn and Heubach [12, Theorem 5, p. 44] give for the number of compositions of n with k parts without s_{0} is nothing but the addition/induction property, Lemma 2 (ii), of extended binomial coefficients for their particular setting.

Example 8 (Compositions with parts in {0, 1, …, l}). Let S = {0, 1, …, l} for some l ≥ 0, and f(s) = 1 for all s ∈ S, R = (ℤ, +, ·, 0, 1). Then d_{S,f}(n, k) = c_{S}(n, k) = \binom{k}{n}_{(1,1,...,1)}. This coefficient is ordinarily denoted by \binom{k}{n}_{l+1} (cf. [2, 9, 17]). The upper bound l = 1 yields the ordinary binomial coefficients.

Example 9 (Sum of part-products). Let f(s) = s for all s ∈ S, R = (ℤ, +, ·, 0, 1). Then,

d_{S,f}(n, k) = ∑_{π∈C_{S}(n,k)} π_{1} ⋯ π_{k}

is the sum of the S-restricted part-products of integer compositions of n with k parts. For S = \{1, 2, …, l\}, d_{S,f}(n, k) is hence \binom{k}{n}_{(1,2,...,l)}.

Example 10 (n-color compositions). As mentioned, the case when f(s) = s also counts the n-color compositions. Agarwal [1] discusses generating functions for the number of n-color compositions of n with k parts and Guo [23] 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 ∈ S and (b) f(s) = s for all odd s ∈ S and f(s) = 0 otherwise. By Theorem 1, the generating functions for (a) and (b) are hence,

(∑_{s∈S} sx^{s})^{k}, and ( ∑_{s odd^{s∈S}} sx^{s})^{k}.

If we let S = ℙ, the set of positive integers, then the closed-form solutions ([1, Theorem 1, p. 1423] and [23, Theorem 4, p. 3], respectively)

\frac{x^{k}}{(1 − x)^{2k}} , and \frac{x^{k}(1 + x^{2})^{k}}{(1 − x^{2})^{2k}}

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 = ℙ [1, Theorem 1, p. 1423], can be shown inductively, using the addition/induction property of extended binomial coefficients,

\binom{k}{n}_{(f(s))_{s∈S}} = ∑_{s=1}^{n−1} s\binom{k − 1}{n − s}_{(f(s))_{s∈S}} = \binom{k}{n − 1}_{(f(s))_{s∈S}} + ∑_{s=1}^{n−1} \binom{k − 1}{n − s}_{(f(s))_{s∈S}},

where f(s) = s for s ∈ ℙ. By the induction hypothesis

∑_{s=1}^{n−1} \binom{k − 1}{n − s}_{(f(s))_{s∈S}} = ∑_{s=1}^{n−1} \binom{n − s + k − 2}{2k − 3} = \binom{n − 2 + k}{2k − 2}

and \binom{k}{n−1}_{(f(s))_{s∈S}} = \binom{n−2+k}{2k−1}, so that the formula is verified.

Example 11 (Part-products of uniform random compositions). Still in a similar context, let X_{S,k,n} be the random variable that, for a random (uniformly chosen) S-restricted integer composition π = (π_{1}, …, π_{k}) of n with k parts, takes on the part-product π_{1} ⋯ π_{k}. Then, X_{S,k,n} takes on p_{S}(n, k) different values, where p_{S}(n, k) = |P_{S}(n, k)|, and the probability

that it takes on value ∏_{s∈S} s^{α_{s}} for (α_{s})_{s∈S} ∈ P_{S}(n, k) is \frac{\binom{k}{(αs)_{s∈S}}}{c_{S}(n,k)}. Hence, the expected value of X_{S,k,n} is

E[X_{S,k,n}] = ∑_{(α_{s})_{s∈S}∈P_{S}(n,k)} \frac{\binom{k}{(α_{s})_{s∈S}}}{c_{S}(n, k)} ∏_{s∈S} s^{α_{s}} = \frac{d_{S,f}(n, k)}{c_{S}(n, k)},

where f is the identity map. More generally, the r-th moment, r ∈ ℕ, of X_{S,k,n} is given as

E[X_{S,k,n}^{r}] = \frac{d_{S,f}(n, k)}{c_{S}(n, k)} = \binom{k}{n}_{(g(s))_{s∈S}},

where f(s) = s^{r} for s ∈ 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 [33] and [35]. But note that, in fact, it also holds that

E[f(X_{S,k,n})] = \frac{d_{S,f}(n, k)}{c_{S}(n, k)} = \binom{k}{n}_{(g(s))_{s∈S}}, g(s) = \frac{f(s)}{c_{S}(n, k)^{1/k}} ,

whenever f is multiplicatively linear, i.e., when f(ab) = f(a)f(b), which includes all powers f(s) = s^{β}, with β ∈ ℝ, where ℝ denotes the set of real numbers, since in this case f(∏_{s∈S} s^{α_{s}}) = ∏_{s∈S} f(s)^{α_{s}}. We finally remark that since E[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 2,

E[f(X_{S,k,n})] = ∑_{μ=0}^{n} E[f(X_{S,j,μ})] E[f(X_{S,k−j,n−μ})]

for all 0 ≤ j ≤ k.

Example 12. We can of course also, e.g., define Y_{S,k,n} as the variable whose values are log(π_{1} ⋯ π_{k}) for random uniform S-restricted integer compositions, so that its moment generating function turns out to be

M(t) = exp(tY_{S,k,n}) = \binom{k}{n}_{(g(s))_{s∈S}},

with g(s) = \frac{s^{t}}{c_{S}(n,k)^{1/k}}.

Example 13 (Odd number of compositions with odd parts). Let f(s) = 1 if s ∈ S is odd and zero otherwise. Then \binom{k}{n}_{(0,1,0,1,0,1,...)} is the number of S-restricted integer compositions with no even parts. For example, \binom{2}{4}_{(0,1,0,1,0,1,...)} = 2 since 4 = 1 + 3 = 3 + 1. To make the example more interesting, let f : S → T with T = ℤ/(2ℤ) with s ↦ [s], where [s] is the congruence class of the integer s in the Boolean ring ℤ/(2ℤ). Then \binom{k}{n}_{([0],[1],[0],[1],[0],[1],...)} is [1] if n has an odd number of compositions with all parts odd (k parts fixed).

Example 14 (Parity of extended binomial coefficients). Relatedly, \binom{k}{n}_{(f(s))_{s∈S}} with f(s) = [1] for all s ∈ S (with notation as in Example 13) 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,...)}] = \binom{k}{n}_{([1],[1],...)}, where [x] denotes the parity of x ∈ ℕ, as above. We find the following characterization for S = {0, 1, …, l},

\binom{k}{n}_{([1],[1],...,[1])} = \begin{cases}[0], & if k even and n odd; \\ \binom{k/2}{n/2}_{([1],[1],...,[1])}, & if k even and n even; \\ ∑_{i=0}^{⌊ \frac{l−r(n)}{2} ⌋} \binom{⌊k/2⌋}{⌊n/2⌋−i}_{([1],[1],...,[1])}, & otherwise, \end{cases}  (10)

where we let r(n) = 1 if n is odd and r(n) = 0 otherwise. To prove (10), 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 26 below (bringing n to the left-hand side in the example). Moreover, if k and n are even, then by the Vandermonde property, Lemma 2, of extended binomial coefficients with j = k/2,

\binom{k}{n}_{([1],[1],...,[1])} = ∑_{x=0}^{n} \binom{k/2}{x}_{([1],[1],...,[1])}\binom{k/2}{n − x}_{([1],[1],...,[1])}.

All summands on the right-hand side, except for \binom{k/2}{n/2}_{([1],[1],...,[1])}^{2} = \binom{k/2}{n/2}_{([1],[1],...,[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 (10) generalizes the well-known ‘parity relationship’ for ordinary binomial coefficients (see Table 1).

Example 15 (Minimal parts). Let f : S → 2^{S} with s ↦ {0, 1, …, s} and let R = (2^{S}, Δ, ∩, ∅, S), where 2^{S} is the power set of S, and Δ denotes the symmetric difference on sets. Then, if x ∈ 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 = \{0, 1, 2, 3\}, \binom{3}{8}_{(\{0\},\{0,1\},\{0,1,2\},\{0,1,2,3\})} = \{0, 1, 2\} and 2 is the minimal part exactly three times here, 8 = 3 + 3 + 2 = 3 + 2 + 3 = 2 + 3 + 3.

Example 16 (‘Alternating trinomial coefficients’). Let S = A ∪ B where A and B are disjoint. Let f(s) = 1 if s ∈ A and f(s) = −1 if s ∈ 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 = {0, 1, 2} and B = {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.

Example 17 (‘Complex alternating quadrinomial coefficients’). Let f(s) = e^{\frac{π}{2} i·s}, where i is the imaginary unit. For S = {0, 1, 2, 3}, we have, e.g.,

(\binom{k}{n}_{(1,i,−1,−i)})_{n} = (1, 3i, −6, 10i, 12, 12i, −10, −6i, 3, i),

for n = 0, 1, …, 9 and k = 3, which, in general, yields the ‘complex alternating quadrinomial coefficients’.

Example 18 (Individual f_{i}’s). Note also the following generalization of the quantities d_{S,f}(n, k). Instead of using the same f for each part, we may consider different f_{i}’s for different parts π_{i}. For example, we might consider the ring element

d_{S,f_{1},...,f_{j},f}(n, k) = ∑_{π} f_{1}(π_{1}) ⋯ f_{j}(π_{j}) · f(π_{j+1}) ⋯ f(π_{k}),

i.e., where the first j ≤ 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 independent but not identically distributed random variables. We find by simple rewriting using Theorem 1 that

d_{S,f_{1},...,f_{j},f}(n, k) = ∑_{x_{1}+···+x_{j}+y=n} f_{1}(x_{1}) ⋯ f_{j}(x_{j}) · \binom{k − j}{y}_{(f(s))_{s∈S}}.

Using f_{1} = ⋯ = f_{j} = g, we find

d_{S,f_{1},...,f_{j},f}(n, k) = ∑_{x+y=n} \binom{j}{x}_{(g(s))_{s∈S}} \binom{k − j}{y}_{(f(s))_{s∈S}},

which can be considered a generalized Vandermonde relationship.

In this context, Heubach and Mansour [24] consider the number of S-restricted compositions of n (with k parts) with exactly m parts in a set B ⊆ S. Using the above, where g and f are the indicator functions of the sets B and S\B, respectively, we find the closed-form solution for this quantity,

\binom{k}{m} ∑_{x=0}^{n} \binom{m}{x}_{(1)_{s∈B}} \binom{k − m}{n − x}_{(1)_{s∈S\B}}.

For B = {s_{0}} with s_{0} ∈ 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} ≤ n,

∑_{m≥0} m\binom{k}{m}\binom{k − m}{n − ms_{0}}_{(1)_{s∈S\B}}

counts the number of times part s_{0} occurs in all S-restricted compositions of n with k parts (cf. [24, Example 2.11, p. 131] and [12]).

Similarly, for, e.g., S = {1, 2, s_{0}} and B = {s_{0}} [24, Example 2.14, p. 132], we find for the number N_{S,{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

N_{S,\{s_{0}\}}(n, m) = ∑_{k≥m} \binom{k}{m}\binom{k − m}{n − ms_{0}}_{(1,1)}.

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

N_{S,{s_{0}}}(n, m) = N_{S,{s_{0}}}(n − 1, m) + N_{S,{s_{0}}}(n − 2, m) + N_{S,{s_{0}}}(n − s_{0}, m − 1).

The combinatorial interpretation thereof is clear: By adding 1, 2, and s_{0} at the end of {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 {1, 2, s_{0}}-restricted compositions of n with exactly m occurrences of s_{0}. This formula obviously generalizes:

N_{S,B}(n, m) = ∑_{s∈S\B} N_{S,B}(n − s, m) + ∑_{s_{0}∈B} N_{S,B}(n − s_{0}, m − 1),

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 [24]). Using this recursion gives another convenient way of deriving the generating function for N_{S,B}(n, m) [24, Corollary 2.12, p. 131] as

\frac{(∑_{s_{0}∈B} x^{s_{0}})^{m}}{(1 − ∑_{s∈S\B} x^{s})^{m+1}} .

Example 19. 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} ⊆ S and m_{1} parts in B_{1} ⊆ S, B_{0} ∩ B_{1} = ∅, is given by

\binom{k}{m_{0}, m_{1}, k − m_{0} − m_{1}} ∑_{z+y+x=n} \binom{m_{0}}{z}_{(1)_{s∈B_{0}}} \binom{m_{1}}{y}_{(1)_{s∈B_{1}}} \binom{k − m_{0} − m_{1}}{x}_{(1)_{s∈S\(B_{0}∪B_{1})}}.

Example 20 (Palindromic compositions). Palindromic compositions, also called self-inverse compositions [28], are compositions where π_{i} = π_{k+1−i} for all i = 1, …, k. Heubach and Mansour [24] 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 d̃_{S,f}(n, k) = ∑π_{i}=π_{k+1−i}^{π∈C_{S} (n,k)} f(π_{1}) ⋯ f(π_{⌈k/2⌉}) and note that, when f is ℕ-valued, d̃_{S,f}(n, k) counts the num-

ber of colored palindromic compositions where parts π_{i} and π_{k+1−i} have the same color. Then, it obviously holds that,

d̃_{S,f}(n, k) = \begin{cases}\binom{k/2}{n/2}_{(f(s))_{s∈S}}, & if k is even; \\ ∑_{s∈S} f(s)(\frac{k−1}{2} ; \frac{n−s}{2})_{(f(s))_{s∈S}}, & otherwise, \end{cases}

where we let \binom{k}{n}_{(f(s))_{s∈S}} = 0 if n or k are not integral.

6.2 Sums of independent random variables

Now, we consider situations where the weighting function f is a discrete probability measure. In this context, we first note that relationship (6) often reduces proofs about sums of independent variables to one-liners when known results about integer compositions are taken into consideration.

Example 21 (Sum of geometrically distributed RVs). For example, if X_{j} ∼ Geometric(p), j = 1, …, k, i.e., each X_{j} has probability distribution function (pdf) g(y) = (1 − p)^{y}p, for y ∈ ℕ, then, denoting by S_{k} the sum X_{1} + ⋯ + X_{k},

P [S_{k} = n] = ∑_{π∈C_{ℕ}(n,k)}(1 − p)^{π_{1}}p ⋯ (1 − p)^{π_{k}}p = p^{k}(1 − p)^{n}c_{ℕ}(n, k) = p^{k}(1 − p)^{n}\binom{n + k − 1}{k − 1},

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 ℕ-restricted integer compositions of an integer n with k parts is the number \binom{n+k−1}{k−1}.

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.

Example 22 (Sum of logarithmically distributed RVs). If all X_{j}, j = 1, …, k, have logarithmic distribution with parameter p, i.e., g(y) = \frac{−1}{log (1−p)} \frac{p^{y}}{y}, for y ∈ ℙ, then

P [S_{k} = n] = ∑_{π∈C_{ℙ}(n,k)} ∏_{i=1}^{k} \frac{−1}{log(1 − p)} \frac{p^{π_{i}}}{π_{i}} = (\frac{−1}{log(1 − p)})^{k}p^{n} ∑_{π∈C_{ℙ}(n,k)} \frac{1}{π_{1} ⋯ π_{k}} .

Note that the quantity ∑_{π∈C_{ℙ}(n,k)} \frac{1}{π_{1}···π_{k}} is precisely d_{ℙ,f}(n, k) with f(s) = \frac{1}{s} for s ∈ ℙ. Thus,

P [S_{k} = n] = (\frac{−1}{log(1 − p)})^{k}p^{n}\binom{k}{n}_{(1, \frac{1}{2} , \frac{1}{3} ,..., \frac{1}{n})}.

Example 23 (Sum of multinomially distributed RVs). If all X_{j}, j = 1, …, k, have multinomial distribution on the set S with parameters p_{s} for s ∈ S, i.e., the number s ∈ S is taken on with probability p_{s}, then

P [S_{k} = n] = ∑_{π∈C_{S}(n,k)} p_{π_{1}} ⋯ p_{π_{k}}.

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 1 already. It allows another interpretation of the quantity \binom{k}{n}_{(a_{s})_{s∈S}}. For nonnegative real numbers (a_{s})_{s∈S} with ∑_{s∈S} a_{s} ≠ 0, the number \frac{1}{c} \binom{k}{n}_{(a_{s})_{s∈S}}, where c = ∑_{j} \binom{k}{j}_{(a_{s})_{s∈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 ∈ S is \frac{a_{s}}{∑_{s′∈S} a_{s′}} = \frac{a_{s}}{c^{1/k}}.

For S = \{1, …, m + 1\} and p_{s} = \frac{1}{m+1}, we obtain De Moivre’s original problem setting, and for S = {0, …, m − 1} and p_{s} = p^{s}q^{m−s−1} (for appropriate p and q), we obtain the distribution discussed in [3].

Continuing with this example, we find that, by the central limit theorem, the ‘probabilities’ \frac{1}{c} \binom{k}{n}_{(a_{s})_{s∈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}}{∑_{s′∈S} a_{s′}} and

whose exact distribution is P [S_{k} = n] = \frac{1}{c} \binom{k}{n}_{(a_{s})_{s∈S}}, is, for large k, approximately normally distributed with mean value μ = k ∑_{s∈S} sp_{s} and variance σ^{2} = k(∑_{s∈S} s^{2}p_{s} − (∑_{s∈S} sp_{s})^{2}).

Example 24 (Stirling’s approximation to central extended binomial coefficients). Thus, by equating the exact distribution with the approximate (and asymptotic) distribution \frac{1}{\sqrt{2πσ^{2}}} e^{− \frac{1}{2}(\frac{n−μ}{2σ})^{2}} at their mean value, this entails, for example, for S = \{0, 1, …, l\}, (a_{s})_{s∈S} = (1, 1, …, 1), and p_{s} = \frac{1}{l+1} (uniform distribution),

\binom{k}{n}_{l+1} ∼ \frac{(l + 1)^{k}}{\sqrt{2πk \frac{(l+1)^{2}−1}{12}}}  (11)

for n = ⌊\frac{kl}{2}⌋, and where we write a_{k} ∼ b_{k} as short-hand for lim_{k→∞} \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. A002426 in Sloane [36]). To explicitly list asymptotics, we, e.g., have

\binom{k}{\frac{k}{2}} ∼ \frac{2^{k+1}}{\sqrt{2πk}} , \binom{k}{k}_{3} ∼ \frac{3^{k}}{\sqrt{\frac{4}{3}πk}} , \binom{k}{\frac{3}{2}k}_{4} ∼ \frac{4^{k}}{\sqrt{\frac{5}{2}πk}} , \binom{k}{2k}_{5} ∼ \frac{5^{k}}{2\sqrt{πk}} ,

for l = 1, 2, 3, 4. Apparently, Walsh [37] 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 (11) for central extended binomial coefficients is novel.^{2}

Example 25. Analogously, for \binom{k}{n}_{(0,1,0,1,0,1,...)}, Example 13, we find for S = \{0, 1, 2, …, 2m\} for some m ∈ ℕ, p_{s} = \frac{1}{m} for s ∈ S, s odd, and p_{s} = 0 otherwise,

\binom{k}{n}_{(0,1,0,1,0,1,...)} ∼ 2 · \frac{m^{k}}{\sqrt{2πk \frac{m^{2}−1}{3}}} ,

for n = km if k is even or m is odd and n = km ± 1 otherwise.^{3} 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...

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.

2However, Fahssi [17] 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.

3The factor 2 in the formula is a correction because the exact distribution takes on strictly positive values only for odd respectively even numbers.

Example 26 (Absorption/extraction property). The following recursive evaluation of the distribution of the sum S_{k} = X_{1} + ⋯ + X_{k} goes back to Bühlmann and Gerber’s discussion of Panjer [30] and Panjer [31].

P [S_{k} = n] = \frac{k}{n} ∑_{s∈S} sg(s)P [S_{k−1} = n − s],  (12)

where g(y) is the pdf of the X_{i}’s. This recursion corresponds to the ‘absorption/extraction’ property of extended binomial coefficients [17],

\binom{k}{n}_{(f(s))_{s∈S}} = \frac{k}{n} ∑_{s∈S} sf(s)\binom{k − 1}{n − s}_{(f(s))_{s∈S}}.

For ordinary binomial coefficients, this is just the property

\binom{k}{n} = \frac{k}{n}\binom{k − 1}{n − 1}.

Fahssi [17] proves the absorption/extraction property by taking the derivative of both sides of (∑_{s∈S} f(s)x^{s})^{k} = ∑_{n≥0} \binom{k}{n}_{(f(s))_{s∈S}}x^{n} with respect x and equating coefficients of x^{n}. The probabilistic proof given in Panjer [30] and Panjer [31] is slightly more intriguing. We have for the conditional expectation of X_{k} given S_{k},

E[X_{k} | S_{k} = n] = \frac{n}{k},

by independence and identical distribution of the variables X_{1}, …, X_{k}. By the definition of conditional expectation, this immediately implies (12).

Example 27. Analogously, we find the following recursion, which goes back to De Pril [15]. Let 0 ∈ S. Then,

P [S_{k} = n] = \frac{1}{g(0)} ∑_{s∈S\\{0\}}(\frac{k + 1}{n}s − 1)g(s)P [S_{k} = n − s],  (13)

which translates into the corresponding property of extended binomial coefficients,

\binom{k}{n}_{(f(s))_{s∈S}} = \frac{1}{f(0)} ∑_{s∈S\\{0\}}(\frac{k + 1}{n}s − 1)f(s)\binom{k}{n − s}_{(f(s))_{s∈S}},

which is proven in [26]. For S = {0, 1} and f(s) = 1 for s ∈ S, this reads as the following property of ordinary binomial coefficients,

\binom{k}{n} = \frac{k + 1 − n}{n}\binom{k}{n − 1}.

A very similar proof of (13) in terms of conditional expectation as in Example 26 is easily derivable [15].

Finally, Sagan [32] 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 (h_{l,m}(n))_{n} is unimodal, that is, there exists an index i such that h_{l,m}(0) ≤ ⋯ ≤ h_{l,m}(i) ≥ h_{l,m}(i + 1) ≥ ⋯ ≥ 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} ≈ l^{m} integer compositions with m parts and upper bound l, and ∑_{k=0}^{m−1}(l + 1)^{k} = \frac{(l+1)^{m}−1}{l} ≈ 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 (\binom{m}{n}_{l+1})_{n} are ‘Gaussian’ in nature, representing sums of independent multinomials; see also our discussion in [16].

6.3 Lattice paths & combinatorial proofs of extended binomial coefficient identities

Here, we present two combinatorial proofs relating to objects involving lattice paths. Our proofs are an application of the third proof of Theorem 1. We also give four combinatorial proofs of identities of extended binomial coefficients which are based on their interpretation given in Theorem 1 as representing S-restricted f-weighted integer compositions.

Example 28 (Counting lattice paths). Consider monotone lattice paths from (0, 0) to (n, k) with steps in \{(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 {(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.

Example 29 (Combinatorial proofs of Fibonacci identities). Relatedly (but a bit more challenging), consider monotone paths from (0, 0) to (0, n) with steps in {(0, 1), (0, 2)}. Of course, by Equation (9) 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 ≤ s ≤ ⌊\frac{n}{2}⌋, (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 {(0, 1), (1, 1)} and by the third proof of Theorem 1, there are \binom{n−s}{s}_{2} such paths. Hence,

∑_{s=0}^{⌊ \frac{n}{2} ⌋} \binom{n − s}{s}_{2} = F_{n+1},

i.e., the sum of diagonal binomial coefficients yields a Fibonacci number. To continue on this, note that

∑_{s=0}^{⌊ \frac{n}{2} ⌋} \binom{n − s}{s} = ∑_{s=⌈ \frac{n}{2} ⌉}^{n} \binom{s}{n − s},

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 {(0, 1), (0, 2), …, (0, l)} for l ≥ 1. As above, there are F_{n+1,l} such paths, where F_{n,l} denotes the the n-th l-generalized Fibonacci number [20], i.e., F_{n,l} = F_{n−1,l} + ⋯ + F_{n−l,l}. Replace all s_{i} (0, i) steps, i = 2, …, l, by a step (i − 1, 1), leaving the s_{1} (0, 1) steps unchanged. This yields a path from (0, 0) to (α, β) = ((2 − 1)s_{2} + ⋯ + (l − 1)s_{l}, s_{1} + ⋯ + s_{l}) with steps in {(0, 1), (1, 1), …, (l − 1, 1)}. Now, note that s_{1} + 2s_{2} + ⋯ + ls_{l} = n and denote by k := s_{1}+⋯+s_{l} the total number of steps. Then (α, β) = (n−s_{1}−(s_{2}+⋯+s_{l}), k) = (n−k, k). Surely, there can be at most n steps and there must be at least ⌈\frac{n}{l}⌋ steps; thus,

∑_{k=⌈ \frac{n}{l} ⌉}^{n} \binom{k}{n − k}_{l} = F_{n+1,l}.

Of course, this identity can more easily be seen by noting that \binom{k}{n−k}_{l} = c_{\{1,...,l\}}(n, k) and, certainly, paths from (0, 0) to (0, n) with steps in {(0, 1), …, (0, l)} are equivalent to compositions of n with an arbitrary number of parts in {1, …, l}.^{4}

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 1). We exemplify with the Vandermonde convolution (Example 30), Fielder and Alford’s recursion (Example 31), and two further results (Examples 32 and 33). We assume that f(s) ∈ ℕ for all s ∈ S.

Example 30 (Combinatorial proof of Vandermonde identity). Let j ∈ ℕ, 0 ≤ j ≤ k, be fixed. Consider the set

D := ⋃_{m=0}^{n} D_{S,f}(m, j) × D_{S,f}(n − m, k − j),  (14)

where we denote by 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 ((π_{1}, …, π_{j}), (π̃_{1}, …, π̃_{k−j})) with the tuple (π_{1}, …, π_{j}, π̃_{1}, …, π̃_{k−j}).

Obviously, the union in (14) is over pairwise disjoint sets. Moreover, each π ∈ D is an f-weighted integer composition of n with k parts p ∈ S. Conversely, let π = (π_{1}, …, π_{j}, π_{j+1}, …, π_{k}) ∈ D_{S,f}(n, k). Then (π_{1}, …, π_{j}) ∈ D_{S,f}(m, j) for some m between 0 and n and (π_{j+1}, …, π_{k}) ∈ D_{S,f}(n − m, k − j). Hence, π ∈ D. Therefore

d_{S,f}(n, k) = |D_{S,f}(n, k)| = |D| = ∑_{m=0}^{n} d_{S,f}(m, j) · d_{S,f}(n − m, k − j).

Example 31 (Combinatorial proof of Fielder and Alford’s result). Note that in writing n = π_{1} + ⋯ + π_{k} with π_{i} ∈ S, we can use integer l ∈ S among the π_{i}’s either 0 times, 1 time, …, ⌊\frac{n}{l}⌋ 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} + ⋯ + q_{k−i} with q_{1}, …, q_{k−i} ∈ S\{l}. Hence, accounting for all orders of the i parts among k and for all possible colorings,

4The identity \binom{k}{n−k}_{l} = c_{\{1,...,l\}}(n, k) is seen as follows. By Example 8, c_{\{0,...,l\}}(n, k) = \binom{k}{n}_{l+1}. Subtracting 1 from each part in a composition π ∈ C_{{1,...,l}}(n, k) yields a composition of n − k with k parts, each between 0 and l − 1.

d_{S,f}(n, k) = ∑_{i=0}^{min\{k,⌊ \frac{n}{l} ⌋\}} f(l)^{i}\binom{k}{i}d_{S\\{l\},f}(n − li, k − i).

Using S = {0, 1, …, l} and f(s) = 1 for all s ∈ S, we obtain Fielder and Alford’s [18] 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),

\binom{k}{n}_{l+1} = ∑_{i=0}^{min\{k,⌊ \frac{n}{l} ⌋\}} \binom{k}{i}\binom{k − i}{n − il}_{l}.

Example 32. For S = {0, 1, …, l} and f(s) = 1 for all s ∈ 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 {0, 1, …, l}-restricted integer compositions of n with k parts that have a positive part π_{i}”. Obviously, if n > 0, C_{{0,1,...,l}}(n, k) = A_{1} ∪ ⋯ ∪ A_{k}, so that, by the inclusion/exclusion formula

c_{{0,1,...,l}}(n, k) = |A_{1} ∪ ⋯ ∪ A_{k}| = ∑_{B≠∅^{B⊆[k]}}(−1)^{|B|−1}|⋂_{j∈B} A_{j}|.

We find

|⋂_{j∈B} A_{j}| = ∑_{i=0}^{n} c_{{1,...,l}}(i, |B|) · c_{{0,...,l}}(n − i, k − |B|)

= ∑_{i=0}^{n} c_{{0,...,l−1}}(i − |B|, |B|) · c_{{0,...,l}}(n − i, k − |B|),

so that by applying Examples 31 and 30, we finally arrive at

\binom{k}{n}_{l+1} = ∑_{j∈[k],ν∈[0,k]}(−1)^{j−1}\binom{k}{j}\binom{k − j}{ν}\binom{k − ν}{n − j − νl}_{l},

where we use the notation [k] = {1, …, k} and [0, k] = {0, 1, …, k}.

Example 33. Relatedly, consider the formula for the number c_{S}(n) of compositions of n with arbitrarily many parts, each in the set S = {1, …, l}, given in [19], p. 43, derived from the generating function for c_{S}(n), c_{S}(x) = \frac{1}{1−∑_{s∈S} x^{s}} (cf. Corollary 5),

c_{S}(n) = ∑_{k≥0,j≥0}(−1)^{j}\binom{k}{j}\binom{n − lj − 1}{k − 1},

whence the corresponding formula for fixed number k of parts is,

c_{S}(n, k) = ∑_{j≥0}(−1)^{j}\binom{k}{j}\binom{n − lj − 1}{k − 1}.  (15)

The beauty of this formula, also given in [18], is that it directly links integer compositions with parts in S = {1, …, l}, or extended binomial coefficients, to ordinary binomial coefficients. A combinatorial proof is as follows. Let A_{i} be the set “ℙ-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

c_{S}(n, k) = |A_{1}^{c} ∩ ⋯ ∩ A_{k}^{c}|.

For any subset of indices B ⊆ [k], we find that |⋂_{j∈B} A_{j}| is the set of ℙ-restricted compositions of n with k parts where the parts indexed by B are strictly greater than l. Subtracting l from these parts yields

|⋂_{j∈B} A_{j}| = c_{ℙ}(n − |B|l, k) = \binom{n − l|B| − 1}{k − 1},

where the last equality is elementary (see, e.g., [19]). Applying the principle of inclusion/exclusion yields (15). The corresponding formula when S is {0, 1, …, l} is

\binom{k}{n}_{l+1} = ∑_{j≥0}(−1)^{j}\binom{k}{j}\binom{n + k − (l + 1)j − 1}{k − 1}.

7 Conclusion

In the current work, we have investigated the quantities

∑_{π} f(π_{1}) ⋯ f(π_{k}),

showing that they precisely yield the extended binomial coefficients \binom{k}{n}_{(f(s))_{s∈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 [17] and in the current exposition, of the coefficients \binom{k}{n}_{(f(s))_{s∈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., [21]) of binomial coefficients extend to the coefficients \binom{k}{n}_{(f(s))_{s∈S}}. Fahssi [17] generalizes the top ten identities from [22], and we have investigated further relationships (summarized in Table 1), but many more results (e.g., concerning further identities, extended binomial congruences, etc.) are awaiting.

Binomial  Extended binomial
∑_{n=0}^{k} n\binom{k}{n} = k2^{k−1}  ∑_{n≥0} n\binom{k}{n}_{(f(s))_{s∈S}} = kc^{k−1} · (∑_{s∈S} sf(s))
∑_{n=0}^{k} n^{2}\binom{k}{n} = (k + k^{2})2^{k−2}  ∑_{n≥0} n^{2}\binom{k}{n}_{(f(s))_{s∈S}} = kc^{k−2}(c ∑_{s∈S} s^{2}f(s) + (k − 1)(∑_{s∈S} sf(s))^{2})
\binom{k}{n} = \frac{k+1−n}{n} \binom{k}{n−1}  \binom{k}{n}_{(f(s))_{s∈S}} = \frac{1}{f(0)} ∑_{s∈S\\{0\}}(\frac{k+1}{n}s − 1)f(s)\binom{k}{n−s}_{(f(s))_{s∈S}}
\binom{k}{n} = \binom{k}{n}  \binom{k}{n}_{(f(s))_{s∈S}} = ∑_{i=0}^{min\{k,⌊ \frac{n}{l} ⌋\}} f(l)^{i}\binom{k}{i}\binom{k−i}{n−li}_{(f(s))_{s∈S\\{l\}}}
∑_{k=⌈n/2⌉}^{n} \binom{k}{n−k} = F_{n+1}  ∑_{k=⌈n/l⌉}^{n} \binom{k}{n−k}_{l} = F_{n+1,l}
\binom{k}{n} = ∑_{ν=0}^{n−1}(−1)^{n−ν−1}\binom{k}{n−ν}\binom{k+ν−n}{ν}  \binom{k}{n}_{l+1} = ∑_{j∈[k],ν∈[0,k]}(−1)^{j−1}\binom{k}{j}\binom{k−j}{ν}\binom{k−ν}{n−j−νl}_{l}
\binom{k}{n} = ∑_{j≥0}(−1)^{j}\binom{k}{j}\binom{n+k−2j−1}{k−1}  \binom{k}{n}_{l+1} = ∑_{j≥0}(−1)^{j}\binom{k}{j}\binom{n+k−(l+1)j−1}{k−1}
\binom{k}{k/2} ∼ \frac{2^{k+1}}{\sqrt{2πk}}  \binom{k}{kl/2}_{l+1} ∼ \frac{(l+1)^{k}}{\sqrt{2πk \frac{(l+1)^{2}−1}{12}}}

[\binom{k}{n}] = \begin{cases}[0], & if k even and n odd; \\ [\binom{⌊k/2⌋}{⌊n/2⌋}], & otherwise. \end{cases}  [\binom{k}{n}_{l+1}] = \begin{cases}[0], & if k even and n odd; \\ [\binom{k/2}{n/2}_{l+1}], & if k even and n even; \\ ∑_{i=0}^{⌊ \frac{l−r(n)}{2} ⌋}[\binom{⌊k/2⌋}{⌊n/2⌋−i}_{l+1}], & otherwise. \end{cases}

Table 1: List of properties of extended binomial coefficients derived in the current work and not included in [17]. The constant c is ∑_{s∈S} f(s). By [x] we denote the parity of x ∈ ℕ; moreover, r(n) is as defined in Example 14.

Furthermore, in the current work, we have considered the quantities

∑_{π} f_{1}(π_{1}) ⋯ f_{j}(π_{j}) · f(π_{j+1}) ⋯ f(π_{k}),

which correspond to independently but not identically distributed random variables. The most general objects to consider, within this framework, would be the quantities,

∑_{π} F (π_{1}, …, π_{k}),

which, by identity (6), correspond to the distribution of the sum of k (possibly dependent and not identically distributed) random variables. For example, Carlitz compositions, introduced in [10], require dependence between parts of an integer composition, namely, that two adjacent parts must be different (see also [5] and [7] for such, and more general, local dependencies), which could be described by quantities such as

∑_{π} g(π_{1}, π_{2}) · g(π_{2}, π_{3}) ⋯ g(π_{k−1}, π_{k}),

with g(m, l) = 1 if and only if m ≠ 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 ≥ 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.

8 Acknowledgements

The author would like to thank the anonymous referee for many helpful comments.

References

[1] A. K. Agarwal, n-color compositions, Indian J. Pure Appl. Math. 31 (2000), 1421–1427.

[2] G. E. Andrews, Euler’s ‘exemplum memorabile inductionis fallacis’ and q-trinomial coefficients, J. Amer. Math. Soc. 3 (1990), 653-669.

[3] K. Balasubramanian, R. Viperos, and N. Balakrishnan, Some discrete distributions related to extended Pascal triangles, Fibonacci Quart. 33 (1995), 415–425.

[4] C. Banderier and P. Hitczenko, Enumeration and asymptotics of restricted compositions having the same number of parts, Discrete Appl. Math. 160 (2012), 2542–2554.

[5] E. A. Bender and E. R. Canfield, Locally restricted compositions I. Restricted adjacent differences, Electron. J. Combin. 12 (2005), Paper R57. Available at

http://www.combinatorics.org/Volume_12/Abstracts/v12i1r57.html.

[6] E. A. Bender and E. R. Canfield, Locally restricted compositions II. General restrictions and infinite matrices, Electron. J. Combin. 16 (2009), Paper R108. Available at

http://www.combinatorics.org/Volume_16/Abstracts/v16i1r108.html.

[7] E. A. Bender and E. R. Canfield, Locally restricted compositions III. Adjacentpart periodic inequalities. Electron. J. Combin., 17 (2010), Paper R145. Available at

http://www.combinatorics.org/Volume_17/Abstracts/v17i1r145.html.

[8] E. A. Bender, E. R. Canfield, and Z. Gao, Locally restricted compositions IV. Nearly free large parts and gap-freeness. Electron. J. Combin., 19 (2012), Paper P14. Available

at http://www.combinatorics.org/Volume_19/Abstracts/v19i4p14.html.

[9] 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., Eighth Annual Conference of the Society of Special Functions and their Applications, Pala, India, Society for Special Functions and their Applications, 2007.

[10] L. Carlitz, Restricted compositions, Fibonacci Quart. 14 (1976), 254–264.

[11] P. Chinn and S. Heubach, (1, k)-compositions, Congr. Numer. 164 (2003), 183–194.

[12] P. Chinn and S. Heubach, Compositions of n with no occurrence of k, in Proceedings of the Thirty-Fourth Southeastern International Conference on Combinatorics, Graph Theory and Computing, vol. 164, 2003, pp. 33–51.

[13] L. Comtet, Advanced Combinatorics, D. Reidel Publishing Company, 1974.

[14] A. De Moivre, The Doctrine of Chances: or, A Method of Calculating the Probabilities of Events in Play, 3rd ed., Millar, 1756, reprint, Chelsea, 1967.

[15] N. De Pril, Recursions for convolutions of arithmetic distributions, Astin Bull. 15 (1985), 135–139.

[16] S. Eger, Asymptotic normality of integer compositions inside a rectangle, preprint,

  http://arxiv.org/abs/1203.0690.

[17] N.-E.  Fahssi,  The  polynomial  triangles  revisited,  preprint,

  http://arxiv.org/abs/1202.0228.

[18] 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., Applications of Fibonacci Numbers, Kluwer, 1991, pp. 77–90.

[19] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.

[20] I. Flores, k-generalized Fibonacci numbers, Fibonacci Quart. 5 (1967), 258–266.

[21] H. W. Gould, Combinatorial Identities: A Standardized Set of Tables Listing 500 Binomial Coefficient Summations, West Virginia University Press, 1972.

[22] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1994.

[23] Y.-H. Guo, Some n-color compositions, J. Integer Seq. 15 (2012).

[24] S. Heubach and T. Mansour, Compositions of n with parts in a set, Congr. Numer. 164 (2004), 127–143.

[25] G. Jaklič, V. Vitrih, and E. Žagar, Closed form formula for the number of restricted compositions, Bull. Aust. Math. Soc. 81 (2010), 289–297.

[26] D. E. Knuth, The Art of Computer Programming, Vol 2, Seminumerical Algorithms, Addison-Wesley, 1969.

[27] M. E. Malandro, Asymptotics for restricted integer compositions, preprint,

  http://arxiv.org/pdf/1108.0337v1.

[28] G. Narang and A. K. Agarwal, n-color self-inverse compositions, Proc. Indian Acad. Sci. Math. Sci. 116 (2006), 257–266.

[29] G. Narang and A. K. Agarwal, Lattice paths and n-colour compositions, Discrete Math. 308 (2008), 1732–1740.

[30] H. H. Panjer, The aggregate claims distribution and stop-loss reinsurance, Transactions of the Society of Actuaries 32 (1980), 537–538.

[31] H. H. Panjer, Recursive evaluation of a family of compound distributions, Astin Bull. 12 (1981), 22–26.

[32] B. E. Sagan, Compositions inside a rectangle and unimodality, J. Algebraic Combin. 29 (2009), 405–411.

[33] E. Schmutz and C. Shapcott, Part-products of S-restricted integer compositions, Appl. Anal. Discrete Math., to appear. Available at

  http://pefmath.etf.rs/accepted/rad1442.pdf.

[34] C. Shapcott, C-color compositions and palindromes, Fibonacci Quart. 50 (2012), 297– 303.

[35] C. Shapcott, Part-products of 1-free integer compositions, Electron. J. Combin. 18 (2011), #P235.

[36] N. J. A. Sloane, ed., The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

[37] D. P. Walsh, Equating Poisson and normal probability functions to derive Stirling’s formula, Amer. Statist. 49 (1995), 270–271.

2013 Mathematics Subject Classification: Primary 05A10; Secondary 05A17, 60G50. Keywords: integer composition, extended binomial coefficient, polynomial coefficient, sum of discrete random variables.

(Concerned with sequence \underline{A002426}.)

Received April 16 2012; revised versions received April 23 2012; September 7 2012; October 13 2012; January 3 2013. Published in Journal of Integer Sequences, January 4 2013.

Return to Journal of Integer Sequences home page.