A Note on Extended Binomial Coefficients

Thorsten Neuschel Department of Mathematics KU Leuven Celestijnenlaan 200B Box 2400 BE-3001 Leuven Belgium

               Thorsten.Neuschel@wis.kuleuven.be

Abstract We study the distribution of the extended binomial coefficients by deriving a complete asymptotic expansion with uniform error terms. We obtain the expansion from a local central limit theorem and we state all coefficients explicitly as sums of Hermite polynomials and Bernoulli numbers.

1 Introduction

The extended binomial coefficients, occasionally called polynomial coefficients [5, p. 77], are defined as the coefficients in the expansion

∑_{k=0}^{∞} \binom{n}{k}^{(q)}x^{k} = (1 + x + x^{2} + ⋯ + x^{q})^{n} , n, q ∈ ℕ = \{1, 2, …\}.  (1)

In written form, they presumably appeared for the first time in the work by De Moivre [6, p. 41] and later they also were addressed by Euler [9]. Since then, the extended binomial coefficients played a role mainly in the theory of compositions of integers, as the number c(k, n, q) of compositions of k with n parts not exceeding q is given by [10, p. 45]

c(k, n, q) = \binom{n}{k − n}^{(q−1)}.

Thus, the extended binomial coefficients and their modifications have been studied in various papers and from different perspectives [1, 2, 3, 4, 7, 8, 12, 13, 15], and among the properties their distribution is of particular interest. Recently, Eger [8] showed (using slightly different notation) that

\binom{n}{nq/2}^{(q)} ∼ \frac{(q + 1)^{n}}{\sqrt{2πn\frac{q(q+2)}{12}}} ,

as n → ∞, meaning that the quotient of both sides tends to unity. Moreover, based upon numerical simulations [8] the question arises how well those coefficients can be approximated by “normal approximations” in general. It is the aim of this note to give a precise and comprehensive answer to this question by establishing a complete asymptotic expansion for the extended binomial coefficients with error terms holding uniformly with respect to all integer k. More precisely, we show the following.

Theorem 1. For all integers N ≥ 2 we have

\sqrt{\frac{q(q + 2)n}{12}} \frac{1}{(1 + q)^{n}} \binom{n}{k}^{(q)} = \frac{1}{\sqrt{2π}} e^{−x^{2}/2} + ∑_{ν=1}^{⌊(N−2)/2⌋} \frac{q_{2ν}(x)}{n^{ν}} + o (\frac{1}{n^{(N−2)/2}} ) ,

as n → ∞, uniformly with respect to all k ∈ ℤ, with

x = \begin{matrix}√ & \overline{12} \\ √ & \overline{q(q + 2)n} \end{matrix} (k − \frac{q}{2}n) ,

where the functions q_{2ν}(x) are given explicitly as sums of Hermite polynomials and Bernoulli numbers (see Theorem 5 below for the exact formulas).

Although we only deal with the very basic situation of the extended binomial coefficients in (1) here, the presented approach is a general one, which admits the derivation of (complete) asymptotic expansions in many applications. However, usually it is not possible to obtain the involved quantities in a very explicit form, which is an instance making the case of extended binomial coefficients especially interesting.

A general overview of the analytic theory of compositions can be found in Flajolet and Sedgewick’s standard book [10], where essentially two asymptotic results on restricted compositions are given [10, pp. 43–44]. The first one states that the numbers C_{k}^{{1,...,q}} of compositions of k with parts restricted to {1, …, q} asymptotically behave like

C_{k}^{{1,...,q}} ∼ c_{q}ρ_{q}^{−k},

as k → ∞, for fixed q ≥ 2. Here, c_{q} > 0 is some constant and ρ_{q} is the singularity of the associated generating function located in the interval (\frac{1}{2}, 1). The second result deals with the number C_{k}^{(n)} of compositions of k having n parts. As these numbers are given explicitly by

C_{k}^{(n)} = \binom{k − 1}{n − 1},

we immediately obtain the asymptotic formula

C_{k}^{(n)} ∼ \frac{k^{n−1}}{(n − 1)!},

as k → ∞, for fixed n. Interpreting the extended binomial coefficients as numbers of restricted compositions, in the present paper we are concerned with the numbers c(k, n, q) counting compositions of k with n parts restricted to {1, …, q}, which can be considered as a mixed type of restricted compositions in the above sense. For fixed integer q, the result in Theorem 5 gives a complete and explicit description of the behavior of c(k, n, q) for large values of n, valid uniformly in k, meaning that with n growing to infinity it is not necessary to specify the way k tends to infinity. This feature usually is not available by methods in the context of singularity analysis.

2 Proof of the main result

Our approach is based on an application of a local central limit theorem. To this end, we choose a sequence of independent random variables with common uniform distribution on the integers {0, …, q}. This way, the extended binomial coefficients can be represented (up to a normalization) as certain probabilities for the sums of the random variables. Before stating the details, we will fix some notation following Petrov [14]. For a (real) random variable X we denote its characteristic function by

φ_{X}(t) = Ee^{itX}, t ∈ ℝ,

where, as usual, E means the mathematical expectation with respect to the underlying probability distribution. If X has finite moments up to k-th order, then φ_{X} is k times continuously differentiable on ℝ and we have

\frac{d^{k}}{dt^{k}} φ_{X}(t)|_{t=0} = \frac{1}{i^{k}} EX^{k}.

Moreover, in this case we define the cumulants of order k by

γ_{k} = \frac{1}{i^{k}} \frac{d^{k}}{dt^{k}} log φ_{X}(t)|_{t=0},

where the logarithm takes its principal branch. Now, let (X_{n}) be a sequence of independent integer-valued random variables having a common distribution and suppose that for all positive integer values of k we have

E|X_{1}|^{k} < ∞

and

EX_{1} = μ, V arX_{1} = σ^{2} > 0.

Thus, for the sum given by

S_{n} = ∑_{ν=1}^{n} X_{ν}

we obtain

ES_{n} = nμ, V arS_{n} = nσ^{2},

and for integer k we define the probabilities

p_{n}(k) = P (S_{n} = k) .

Furthermore, we introduce the Hermite polynomials (in the probabilist’s version)

H_{m}(x) = (−1)^{m}e^{x^{2}/2} \frac{d^{m}}{dx^{m}} e^{−x^{2}/2},

and for positive integers ν we define the functions

q_{ν}(x) = \frac{1}{\sqrt{2π}} e^{−x^{2}/2} ∑_{{k_{1},...,kν ≥0 \atop k_{1}+2k_{2}+···+νkν =ν}} H_{ν+2s}(x) ∏_{m=1}^{ν} \frac{1}{k_{m}!} (\frac{γ_{m+2}}{(m + 2)!σ^{m+2}} )^{k_{m}} ,  (2)

where s = k_{1} + ⋯ + k_{ν} and γ_{m+2} denotes the cumulant of order m + 2 of X_{1}.

Finally, we demand (for convenience) that the maximal span of the distribution of X_{1} is equal to one. This means that there are no numbers a and h > 1 such that the values taken on by X_{1} with probability one can be expressed in the form a + hk (k ∈ ℤ). Under all these assumptions we have the following complete asymptotic expansion in the sense of a local central limit theorem [14, p. 205].

Theorem 2. For all integers N ≥ 2 we have

σ\sqrt{n}p_{n}(k) = \frac{1}{\sqrt{2π}} e^{−x^{2}/2} + ∑_{ν=1}^{N−2} \frac{q_{ν}(x)}{n^{ν/2}} + o (\frac{1}{n^{(N−2)/2}} ) ,  (3)

as n → ∞, uniformly with respect to all k ∈ ℤ, where we have

x = \frac{k − nμ}{σ\sqrt{n}}.

In the following we choose X_{1} to take the integer values {0, …, q} with

P (X_{1} = k) = \frac{1}{q + 1}, k ∈ \{0, …, q\}.

Hence, we obtain

p_{n}(k) = P (S_{n} = k) = \frac{1}{(1 + q)^{n}} \binom{n}{k}^{(q)}, k ∈ ℤ.  (4)

It is our aim to apply Theorem 2 in full generality and we want to compute all cumulants as explicitly as possible.

Lemma 3. For the k-th order cumulant γ_{k} of X_{1} we have

γ_{k} = \begin{cases}\frac{q}{2}, & if k = 1; \\ 0, & if k odd and k > 1; \\ \frac{B_{2l}}{2l} ((q + 1)^{2l} − 1) , & if k = 2l, l ≥ 1, \end{cases}  (5)

where B_{ν}, ν ≥ 0, denotes the Bernoulli numbers [11, p. 22]. Proof. First, we observe that the characteristic function of X_{1} is given by

φ_{X_{1}}(t) = \frac{1 + e^{it} + ⋯ + e^{qit}}{1 + q} .

According to the definition of the cumulants we obtain for a positive integer k

γ_{k} = \frac{1}{i^{k}} \frac{d^{k}}{dt^{k}} log φ_{X_{1}}(t)|_{t=0}

= \frac{1}{i^{k}} \frac{d^{k}}{dt^{k}} \{log (1 + e^{it} + ⋯ + e^{qit}) − log(1 + q)\} |_{t=0}

= \frac{1}{i^{k}} \frac{d^{k}}{dt^{k}} log (\frac{e^{(q+1)it} − 1}{e^{it} − 1}) |_{t=0}

= \frac{1}{i^{k}} \frac{d^{k}}{dt^{k}} \{\frac{q}{2}it + log (\frac{sin \frac{q+1}{2}t}{sin \frac{t}{2}})\} |_{t=0}

= \frac{q}{2}δ_{k,1} + \frac{1}{i^{k}} \frac{d^{k}}{dt^{k}} \{log (\frac{sin \frac{q+1}{2}t}{\frac{q+1}{2}t}) − log (\frac{sin \frac{t}{2}}{\frac{t}{2}} )\} |_{t=0},

where δ_{k,1} denotes the Kronecker delta. Using

\frac{d}{dz} log (\frac{sin z}{z} ) = cotan z − \frac{1}{z}

yields

γ_{k} = \frac{q}{2}δ_{k,1} + \frac{1}{i^{k}} \frac{d^{k−1}}{dt^{k−1}} \{\frac{q + 1}{2} (cotan \frac{q + 1}{2}t − \frac{2}{(q + 1)t}) − \frac{1}{2} (cotan \frac{t}{2} − \frac{2}{t})\} |_{t=0}.

Now, making use of the following expansion [11, p. 35]

cotan z − \frac{1}{z} = ∑_{m=1}^{∞}(−1)^{m} \frac{4^{m}}{(2m)!}B_{2m}z^{2m−1} , 0 < |z| < π,

after some algebra we obtain

γ_{k} = \frac{q}{2}δ_{k,1} + \frac{1}{i^{k}} \frac{d^{k−1}}{dt^{k−1}} ∑_{m=1}^{∞}(−1)^{m} \frac{B_{2m}}{(2m)!} ((q + 1)^{2m} − 1) t^{2m−1}|_{t=0}.

Carrying out the differentiation under the summation sign immediately gives us (5).

Remark 4. As an immediate consequence of Lemma 3 we obtain

EX_{1} = μ = γ_{1} = \frac{q}{2}

and, as we know B_{2} = \frac{1}{6},

V arX_{1} = σ^{2} = γ_{2} = \frac{B_{2}}{2} ((q + 1)^{2} − 1) = \frac{q(q + 2)}{12}.

We now are ready to state the main theorem in form of a complete asymptotic expansion with explicit coefficients for the extended binomial coefficients \binom{n}{k}^{(q)}.

Theorem 5. For all integers N ≥ 2 we have

\sqrt{\frac{q(q + 2)n}{12}} \frac{1}{(1 + q)^{n}} \binom{n}{k}^{(q)} = \frac{1}{\sqrt{2π}} e^{−x^{2}/2} + ∑_{ν=1}^{⌊(N−2)/2⌋} \frac{q_{2ν}(x)}{n^{ν}} + o (\frac{1}{n^{(N−2)/2}} ) ,

as n → ∞, uniformly with respect to all k ∈ ℤ, with

x = \begin{matrix}√ & \overline{12} \\ √ & \overline{q(q + 2)n} \end{matrix} (k − \frac{q}{2}n) ,

and

q_{2ν}(x) = \frac{1}{\sqrt{2π}} (\frac{12}{q(q + 2)})^{ν} e^{−x^{2}/2}  (6)

× ∑_{{k_{2},k_{4},...,k_{2ν} ≥0 \atop k_{2}+2k_{4}+···+νk_{2ν} =ν}} H_{2(ν+s)}(x) (\frac{6}{q(q + 2)})^{s} ∏_{m=1}^{ν} \frac{1}{k_{2m}!} (\frac{B_{2(m+1)} ((q + 1)^{2m+2} − 1)}{(2m + 2)!(m + 1)})^{k_{2m}} ,

where s = k_{2} + k_{4} + ⋯ + k_{2ν}.

Proof. The proof is based on an application of Theorem 2 to the probabilities defined in (4). First we observe that in our situation the functions given in (2) vanish identically for odd indices, which turns out to be a consequence of (5). Indeed, if ν = 2l +1 for an integer l ≥ 0, then in every solution k_{1}, …, k_{2l+1} ≥ 0 of the equation

k_{1} + 2k_{2} + ⋯ + (2l + 1)k_{2l+1} = 2l + 1

there is at least one odd index i with k_{i} > 0. Consequently, using (5) we have

∏_{m=1}^{2l+1} \frac{1}{k_{m}!} (\frac{γ_{m+2}}{(m + 2)!σ^{m+2}} )^{k_{m}} = 0,

from which follows that q_{2l+1}(x) vanishes identically. Thus, only the functions q_{2ν}(x) appear in (3) and here we have

q_{2ν}(x) = \frac{1}{\sqrt{2π}} e^{−x^{2}/2} ∑_{{k_{1},...,k_{2ν} ≥0 \atop k_{1}+2k_{2}+···+2νk_{2ν} =2ν}} H_{2(ν+s)}(x) ∏_{m=1}^{2ν} \frac{1}{k_{m}!} (\frac{γ_{m+2}}{(m + 2)!σ^{m+2}} )^{k_{m}} ,

where s = k_{1} + ⋯ + k_{2ν}. An analogous argument as in the odd case above shows that a solution k_{1}, …, k_{2ν} of the equation

k_{1} + 2k_{2} + ⋯ + 2νk_{2ν} = 2ν

with a positive entry at an odd index does not give any contribution to the whole sum, so that we can write

q_{2ν}(x) = \frac{1}{\sqrt{2π}} e^{−x^{2}/2} ∑_{{k_{2},k_{4},...,k_{2ν} ≥0 \atop k_{2}+2k_{4}+···+νk_{2ν} =ν}} H_{2(ν+s)}(x) ∏_{m=1}^{ν} \frac{1}{k_{2m}!} (\frac{γ_{2m+2}}{(2m + 2)!σ^{2m+2}} )^{k_{2m}} ,

where s = k_{2} + k_{4} + ⋯ + k_{2ν}. Now, taking the explicit form of the cumulants in (5) into account, after some elementary computation we obtain (6).

For the purpose of illustration we state Theorem 5 for N = 5 explicitly.

Example 6. Using the known facts

H_{4}(x) = x^{4} − 6x^{2} + 3, B_{4} = −\frac{1}{30},

we obtain

\sqrt{\frac{q(q + 2)n}{12}} \frac{1}{(1 + q)^{n}} \binom{n}{k}^{(q)} = \frac{1}{\sqrt{2π}} e^{−x^{2}/2} \{1 − \frac{((q + 1)^{4} − 1) (x^{4} − 6x^{2} + 3)}{20nq^{2}(q + 2)^{2}}\} + o (\frac{1}{n^{3/2}} ) ,

as n → ∞, uniformly with respect to all k ∈ ℤ, where we have

x = \begin{matrix}√ & \overline{12} \\ √ & \overline{q(q + 2)n} \end{matrix} (k − \frac{q}{2}n) .

3 Acknowledgments

The author would like to express his gratitude to two anonymous referees for their constructive comments improving the readability of the manuscript. This work is supported by KU Leuven research grant OT/12/073 and the Belgian Interuniversity Attraction Pole P07/18.

References

[1] G. Andrews, Euler’s “Exemplum Memorabile Inductionis Fallacis” and q-trinomial coefficients, J. Amer. Math. Soc. 3 (1990), 653–669.

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

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

[4] C. Caiado and P. Rathie, Polynomial coefficients and distributions of the sum of discrete uniform variables, in A. Mathai, M. Pathan, K. Jose, 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. Available electronically at

http://community.dur.ac.uk/c.c.d.s.caiado/multinomial.pdf.

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

[6] A. De Moivre, The Doctrine of Chances: or, A Method of Calculating the Probabilities of Events in Play, 3rd ed. London: Millar, 1756; rpt. New York: Chelsea, 1967.

[7] S. Eger, Restricted weighted integer compositions and extended binomial coefficients, J. Integer Seq. 16 (2013), Article 13.1.13.

[8] S. Eger, Stirling’s approximation for central extended binomial coefficients, Amer. Math. Monthly 121 (2014), 344–349.

[9] L. Euler, De evolutione potestatis polynomialis cuiuscunque (1+x+x^{2}+x^{3}+x^{4}+etc.)^{n}, Nova Acta Academiae Scientarum Imperialis Petropolitinae 12 (1801), 47–57.

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

[11] I. Gradshteyn and I. Ryzhik, Table of Integrals, Series and Products, twelfth printing, Academic Press, 1979.

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

[13] A. Knopfmacher and B. Richmond, Compositions with distinct parts, Aequationes Math. 49 (1995), 86–97.

[14] V. Petrov, Sums of Independent Random Variables, Springer-Verlag, Berlin, 1975.

[15] Z. Star, An asymptotic formula in the theory of compositions, Aequationes Math. 13 (1975), 279–284.

2010 Mathematics Subject Classification: Primary 11P82; Secondary 05A16, 41A60. Keywords: extended binomial coefficient, composition, restricted integer composition, complete asymptotic expansion, local central limit theorem, normal approximation, Hermite polynomial, Bernoulli number.

(Concerned with sequences \underline{A002426}, \underline{A005190}, \underline{A008287}, \underline{A027907}, and \underline{A035343}.)

Received July 29 2014; revised versions received October 1 2014; November 3 2014; November 4 2014. Published in Journal of Integer Sequences, November 4 2014.

Return to Journal of Integer Sequences home page.