Asymptotic Estimate for the Multinomial Coefficients

Jiyou Li School of Mathematical Sciences Shanghai Jiao Tong University Shanghai, 200240 China

                 lijiyou@sjtu.edu.cn

Abstract The multinomial coefficient \binom{n,q}{k} is defined to be the coefficient of x^{k} in (1 + x + x^{2} + ⋯ + x^{q−1})^{n}. It is conjectured that for given n > 2, T (n, q) := \binom{n,q}{cn} − \binom{n,q−1}{cn} is unimodal and the maximum occurs at q = ⌊log_{1+ \frac{1}{c}} n⌋ or q = ⌊log_{1+ \frac{1}{c}} n⌋ + 1. As an attempt to prove this conjecture, we give an asymptotic estimate for \binom{n,q}{cn} as n tends to infinity, where c is a positive integer.

1 Introduction

The multinomial coefficient \binom{n,q}{k} is defined by

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

Clearly \binom{n,q}{k} is a natural generalization of the well-known binomial and trinomial coefficients and thus belongs to a large class of fundamental combinatorial numbers. It was studied extensively by many mathematicians since Euler. For details related to this number the readers are referred to [1, 2, 4, 5, 9, 14]. Some applications in coding theory and communication theory can be found in [8, 10].

Multinomial coefficients count the numbers of certain compositions. For a positive integer k, a composition (also called an ordered partition) is a finite sequence of positive integers x_{1}, x_{2}, …, x_{r} such that x_{1} + x_{2} + ⋯ + x_{r} = k. The x_{i}’s are called parts of the composition. A composition with n parts is called a n-part composition.

Let b(k, n, q) be the number of n-part compositions of k such that each part is bounded by q. Obviously b(k, n, q) equals \binom{n,q}{k−n}, which is the coefficient of x^{k} in the expansion of (x + x^{2} + ⋯ + x^{q})^{n} = x^{n}(1 + x + ⋯ + x^{q−1})^{n}. It also equals the number of different ways putting k identical balls into n distinct boxes with each one nonempty and containing at most q − 1 balls, or equivalently, the number of k-multisets in {1, 2, …, n} such that each number appears and is repeated at most q − 1 times. In this note we will mainly focus on the study of \binom{n,q}{k}.

From the multinomial theorem one has

\binom{n, q}{k} = ∑_{\begin{matrix}i_{1}+i_{2}+···+i_{q}=n, \\ i_{2}+2i_{3}+···+(q−1)i_{q}=k \end{matrix}} \binom{n}{i_{1}, i_{2}, …, i_{q}}.

However, it was proved in [15] that when q > 2, \binom{n,q}{k} has no closed form, that is, it cannot be written as a sum of finite hypergeometric terms. A natural question is thus to ask if there are any nice asymptotic estimates for \binom{n,q}{k} for suitable parameters n, q, k.

We are also interested in the unimodality of the multinomial coefficients.

Definition 1. A sequence a_{0}, a_{1}, …, a_{n} of real numbers is unimodal if for some 0 ≤ k ≤ n one has

a_{0} ≤ a_{1} ≤ ⋯ ≤ a_{k−1} ≤ a_{k} ≥ a_{k+1} ≥ ⋯ ≥ a_{n}.

For instance, the sequence \binom{n}{i}, 0 ≤ i ≤ n is unimodal. Unimodality plays an important role in combinatorics, number theory and representation theory. Many interesting and important examples are surveyed by Stanley [16, 17].

It is well known that for given n, q, \binom{n,q}{k} is unimodal (see, for example, [1]).

Proposition 2. For given positive integers n, q, \binom{n,q}{k} is unimodal on k and reaches its maximum at k = ⌊\frac{qn}{2}⌋.

Recall that b(k, n, q) is the number of n-part compositions of k such that each part is bounded by q. Let a(k, n, q) be the number of compositions of k with n parts such that the largest part is q. Then a(k, n, q) = b(k, n, q) − b(k, n, q − 1) and in particular a(2n, n, q) = \binom{n,q}{n} − \binom{n,q−1}{n}.

Let b(k, q) = ∑_{n=1}^{k} b(k, n, q) (respectively, a(k, q) = ∑_{n=1}^{k} a(k, n, q)) be the number of compositions of a positive integer k with parts bounded by q (respectively, the largest part is q). It is well known that [12]

∑_{k=0}^{∞} b(k, q)x^{k} = \frac{1 − x}{1 − 2x + x^{q+1}} .

Based on this formula and analytical tools, Odlyzko and Richmond [14] proved the next statement.

Lemma 3 (Odlyzko and Richmond). Let a(k, q) be defined as above. Then a(k, q) is unimodal for any k and the maximum value occurs for q = ⌊log_{2} k⌋ infinitely often and q = ⌊log_{2} k⌋ + 1 infinitely often and always at one of these two values and no other.

Based on numerical results, an improved conjectured is proposed.

Conjecture 4. Let a(k, q) be defined as above. Let c be a positive integer. Then for any n, a((c + 1)n, n, q) = \binom{n,q}{cn} − \binom{n,q−1}{cn} is unimodular on q and the maximum value occurs for q = ⌊log_{1+ \frac{1}{c}} n⌋ + 1 or q = ⌊log_{1+ \frac{1}{c}} n⌋ + 1.

In particular, a(2n, n, q) = \binom{n,q}{n} − \binom{n,q−1}{n} is unimodular on q and the maximum value occurs for q = ⌊log_{2} n⌋ or q = ⌊log_{2} n⌋ + 1.

Our attempt to establish this conjecture starts with an investigation to the asymptotic behaviors of \binom{n,q}{k} when k is linear of n. We will first review some classical results.

For the simplest case q = 2, it is well known that the binomial coefficient \binom{n,2}{cn} = \binom{n}{cn} has asymptotic estimate

\binom{n, 2}{cn} ∼ \frac{1}{\sqrt{2π(c − c^{2})n}}(c^{−c}(c − 1)^{−c+1})^{n},

where 0 < c < 1 is a constant.

For the case q = 3, it is known for k = n, the central trinomial coefficient has asymptotic estimate

\binom{n, 3}{n} ∼ \frac{3^{n+1/2}}{2\sqrt{πn}} .

For large q and general k, based on the integral representation

\binom{n, q}{k} = \frac{2}{π} ∫0^{\frac{π}{2}} (\frac{sin qθ}{sin θ})^{n} cos(((q − 1)n − 2k)θ)dθ,

André [3] proved that

sup_{k} \binom{n, q}{k} ∼ \frac{\sqrt{6}q^{n}}{\sqrt{(q^{2} − 1)πn}}, n → ∞.

This estimate has several other proofs; see, for example, a recent one by Eger [6, 7], by representing it as the distribution of sums of independent discrete random variables. An asymptotic distribution in this case was given by Neuschel [13].

Star [18] generalized the result of André. Write k = \frac{1}{2}(n − s)(q + 1), where s = Kn^{θ}, 0 ≤ θ ≤ 1/2 and K > 0 is a constant. Star proved that

\binom{n, q}{k − n} = \frac{\sqrt{6}q^{n}}{\sqrt{(q^{2} − 1)πn}} · (1 + \frac{∑_{j=0}^{1} h_{1,j}(q)s^{2j}}{n^{1}} + ⋯ + \frac{∑_{j=0}^{m−1} h_{m−1,j}(q)s^{2j}}{n^{m−1}} + O(\frac{1 + s^{2m}}{n^{m}})) ,

where h_{i,j}(q) are some rational functions in the function field ℝ(q).

The main result of this note is an asymptotic estimate for \binom{n,q}{k} for large q > 3 and for general k = cn, where c is fixed positive integer. The proof uses simple analysis based on Hayman’s method.

Lemma 5. Suppose q > 3 and k = cn, where c < q is an absolute positive integer. Then we have

\binom{n, q}{cn} ∼ \frac{ϕ(r)}{\sqrt{2πn}} (\frac{1 − r^{q}}{r − r^{2}} )^{n} ,

as n → ∞, where

ϕ(r) = (\frac{r}{(1 − r)^{2}} − \frac{q^{2}r^{q}}{(1 − r^{q})^{2}} )^{−1/2} , r = \frac{1}{d} + \frac{q}{c^{2}d^{q+2}} + θ\frac{q^{3}}{d^{2q}} ,

|θ| ≤ 1 and d = 1 + \frac{1}{c}. In particular, when c = 1 we have

r = \frac{1}{2} + \frac{q}{2^{q+2}} + θ\frac{q^{3}}{2^{2q}} .

The proof of Theorem 5 is given in Section 2. For simplicity of the computations, we only gives details of the proof for the special case k = n, i.e., c = 1. The proof of case c > 1 is essentially the same as the case c = 1.

2 Proof of Theorem 5

Definition 6. Suppose that f(z) = ∑_{n=0}^{∞} a_{n}z^{n} is a complex analytic function for |z| < R, where 0 < R ≤ ∞. Define

M(r) = max_{|z|=r} |f(z)|.  (1)

If for large enough r, we have M(r) = f(r), then f(z) is called an admissible function. The references [11, 19] present a discussion on admissible functions.

Hayman [11] showed that such good functions have nice asymptotic estimates for their coefficients.

Lemma 7 (Hayman). Let f(z) = ∑_{n=0}^{∞} a_{n}z^{n} be an admissible function, which is analytic in the disk |z| < R. Denote

a(r) = r\frac{f′(r)}{f(r)}, b(r) = ra′(r),

and suppose 0 < r_{n} < R is a positive real zero satisfying

a(r_{n}) = n, ∀n ∈ N.

Then

a_{n} ∼ \frac{f(r_{n})}{r_{n}^{n}\sqrt{2πb(r_{n})}}, n → ∞.

Lemma 8. [2] The function f(z) = (1 + z + z^{2} + ⋯ + z^{q−1})^{n} is an admissible function analytical in the disk |z| < 1.

Lemma 9. For q ≥ 3 the equation

(q − 2)x^{q+1} − (q − 1)x^{q} + 2x − 1 = 0, q ∈ N

has only two positive real roots including 1 being one of them. The second root r satisfies

|r − \frac{1}{2} − \frac{q}{2^{q+2}} | ≤ \frac{q^{3}}{2^{2q}} .

Proof. Since the cases q = 3, 4 can be verified directly, we may assume q > 4. Suppose f(x) = (q − 2)x^{q+1} − (q − 1)x^{q} + 2x − 1. Then f′′(x) = qx^{q−2}(xq^{2} − 2x − xq − q^{2} + 2q − 1) = 0 gives two inflection points \frac{(q−1)^{2}}{(q+1)(q−2)}, 0. This proves that there are only two positive real roots including 1.

Now suppose that r = \frac{1}{2} + \frac{c}{2^{q+2}} is a positive real zero of f(x), where c is regarded as a variable depending on q and will be specified. Then

f(r) = (q − 2)(\frac{1}{2} + \frac{c}{2^{q+2}} )^{q+1} − (q − 1)(\frac{1}{2} + \frac{c}{2^{q+2}} )^{q} + 2(\frac{1}{2} + \frac{c}{2^{q+2}} ) − 1

= (\frac{−q}{2^{q+1}} + \frac{(q − 2)c}{2^{2q+2}})(1 + \frac{c}{2^{q+1}} )^{q} + \frac{c}{2^{q+1}}

= 0.

Assume without of generality that 0 ≤ c ≤ q^{3/2}. By Taylor’s theorem one has

|(1 + \frac{c}{2^{q+1}} )^{q} − 1 − \frac{cq}{2^{q+1}} | ≤ \frac{c^{2}q^{2}}{2^{2q}} ≤ \frac{q^{5}}{2^{2q}} .

And hence

|f(r) + \frac{q − c}{2^{q+1}} + \frac{c(q^{2} − q + 2)}{2^{2q+2}} | ≤ \frac{q^{6}}{2^{3q+1}} .

Since f(r) = 0, we then have

q − c + \frac{c(q^{2} − q + 2)}{2^{q+1}} + \frac{θq^{6}}{2^{2q}} = 0,

where 0 ≤ |θ| ≤ 1.

Let c = q + c′. Putting it into the above equality, one has

c′(1 − \frac{q^{2} − q + 2}{2^{q+1}}) = \frac{q^{3} − q^{2} + 2q}{2^{q+1}} + \frac{θq^{6}}{2^{2q}} .

This implies

|c − q − \frac{q^{3} − q^{2} + 2q}{2^{q+1} − q^{2} + q − 2}| ≤ \frac{2q^{6}}{2^{2q}} .

Replace in r = \frac{1}{2} + \frac{c}{2^{q+2}} to obtain, for q > 16,

\frac{q^{3} − q^{2}}{2^{2q+2}} ≤ r − \frac{1}{2} − \frac{q}{2^{q+2}} ≤ \frac{q^{3}}{2^{2q+2}} .

The remaining cases of q can be easily verified. Lemma 10. Assume q > 3. Then we have the asymptotic estimate

\binom{n, q}{n} ∼ \frac{ϕ(r)}{\sqrt{2πn}} (\frac{1 − r^{q}}{r − r^{2}} )^{n} , n → ∞

where ϕ(r) = (\frac{r}{(1−r)^{2}} − \frac{q^{2}r^{q}}{(1−r^{q})^{2}} )^{−1/2}, and |r − \frac{1}{2} − \frac{q}{2^{q+2}} | ≤ \frac{q^{3}}{2^{2q}} . Proof. Let f(z) = (1 + z + z^{2} + ⋯ + z^{q−1})^{n} = (\frac{1−z^{q}}{1−z})^{n}. By Lemma 8, f(z) is an admissible analytical function on ℂ − {∞}. Applying Hayman’s theorem (Lemma 7), we have

a(x) = x\frac{f′(x)}{f(x)} = \frac{−nx(qx^{q−1} − qx^{q} − 1 + x^{q})}{(1 − x^{q})(1 − x)},
b(x) = xa′(x) = \frac{nx(1 − x^{q−1}q^{2} − 2x^{q} + x^{2q} + 2q^{2}x^{q} − x^{q+1}q^{2})}{(−1 + x^{q})^{2}(x − 1)^{2}}

= nx (\frac{1}{(1 − x)^{2}} − \frac{q^{2}x^{q−1}}{(x^{q} − 1)^{2}} ) .

The equation a(x_{n}) = n yields

\frac{−nx_{n}(qx_{n}^{q−1} − qx_{n}^{q} − 1 + x_{n}^{q})}{(1 − x_{n}^{q})(1 − x_{n})} = n,

and thus

(q − 2)x_{n}^{q+1} − (q − 1)x_{n}^{q} + 2x_{n} − 1 = 0.

The result now follows from Lemma 9. Corollary 11. When q > 3, for large n we have the estimate

\binom{n, q}{n} ∼ \frac{(1 + \frac{q^{2}−6q}{2^{q}} + θ_{1} \frac{q^{2}}{2^{2q}})2^{n}}{\sqrt{πn}} (1 − \frac{1}{2^{q−2}} + θ_{2} \frac{q^{2}}{2^{2q}})^{n}, n → ∞,

where |θ_{i}| ≤ 1 for i = 1, 2. Proof. Since

|r − \frac{1}{2} − \frac{q}{2^{q+2}} | ≤ \frac{q^{3}}{2^{2q}} ,

it follows that

|\frac{r}{(1 − r)^{2}} − \frac{1}{2} − \frac{3q}{2^{q−1}} | ≤ \frac{q}{2^{2q}} ,

and

|\frac{q^{2}r^{q}}{(1 − r^{q})^{2}} − \frac{q^{2}}{2^{q}} | ≤ \frac{q^{4}}{2^{2q}} .

Thus

|ϕ(r) − \sqrt{2}(1 + \frac{q^{2} − 6q}{2^{q}})| ≤ \frac{q^{2}}{2^{2q}} .

Similarly

|\frac{1 − r^{q}}{r − r^{2}} − 2 + \frac{1}{2^{q−1}} | ≤ \frac{q^{2}}{2^{2q}} ,

and the result follows from Theorem 10.

3 Acknowledgments

Part of this work was done during the author’s master’s studies at Beijing Normal University. This work is supported in part by the National Science Foundation of China (11771280) and in part by the National Science Foundation of Shanghai Municipal (17ZR1415400).

The author wishes to thank the referees for their constructive comments.

References

[1] G. E. Andrews, A theorem on reciprocal polynomials with applications to permutations and compositions, Amer. Math. Monthly 82 (1975), 830–833.

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

[3] L. Comtet, Advanced Combinatorics, D. Reidel, 1974.

[4] Valerio De Angelis, Asymptotic expansions and positivity of coefficients for large powers of analytic functions, Int. J. Math. Math. Sci. (16) (2003), 1003–1025.

[5] Robert Donaghey and Louis W. Shapiro, Motzkin numbers, J. Combinatorial Theory Ser. A 23 (1977), 291–301.

[6] S. Eger, Restricted weighted integer compositions and extended binomial coefficients, J. Integer Sequences 16 (2013), Article 13.1.3.

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

[8] E. N. Gilbert, Synchronization of binary messages, IRE Trans. IT-6 (1960), 470–477.

[9] Ian P. Goulden and David M. Jackson, Combinatorial Enumeration, Dover, 2004.

[10] L. J. Guibas and A. M. Odlyzko, Long repetitive patterns in random sequences, Z. Wahrsch. Verw. Gebiete 53 (1980), 241–262.

[11] W. K. Hayman, A generalisation of Stirling’s formula, J. Reine Angew. Math. 196 (1956), 67–95.

[12] P. A. MacMahon, Memoir on the theory of compositions of numbers, Philos. Trans. Roy. Soc. London Ser. A 184 (1890), 835–901.

[13] T. Neuschel, A note on extended binomial coefficients, J. Integer Sequences 17 (2014), Article 14.10.4.

[14] A. M. Odlyzko and L. B. Richmond, On the compositions of an integer. In Combinatorial Mathematics VII, Vol. 829 of Lecture Notes in Math., pp. 199–210. Springer-Verlag, 1980.

[15] M. Petkovsek, H. S. Wilf, and D. Zeilberger, A = B, A. K. Peters, 1996.

[16] Richard P. Stanley, Unimodal sequences arising from Lie algebras. In Combinatorics, Representation Theory and Statistical Methods in Groups, Vol. 57 of Lecture Notes in Pure and Appl. Math., pp. 127–136. Dekker, 1980.

[17] Richard P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry. In Graph Theory and its Applications: East and West (Jinan, 1986), Vol. 576 of Ann. New York Acad. Sci., pp. 500–535. New York Acad. Sci., 1989.

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

[19] Herbert S. Wilf, generatingfunctionology, A. K. Peters, 3rd edition, 2006.

2010 Mathematics Subject Classification: Primary 05A16; Secondary 05A15, 05A17. Keywords: multinomial coefficient, Hayman’s method.

(Concerned with sequences \underline{A002426}, \underline{A005725}, \underline{A187925}, and \underline{A305161}.)

Received January 29 2018; revised versions received February 4 2018; August 23 2018; June 8 2018; June 12 2018; September 5 2018; September 8 2018; May 30 2019; August 25 2019. Published in Journal of Integer Sequences, December 28 2019.

Return to Journal of Integer Sequences home page.