bounding extended binomial coefficients from above

186 Views Asked by At

Given natural $i,m\ge 1$, how large can the largest coefficient of the polynomial $$(x^0+x^1+\dots+x^{m-1})^i$$ (viewed as polynomial in $x$) be?

A trivial upper bound is $m^i$, perhaps even $m^{i-1}$. Is there any tighter yet simple upper bound? We need a closed, explicit (nonrecursive, without big/iterated sums or big/iterated products), and possibly elementary expression involving $m$ and $i$.

3

There are 3 best solutions below

5
On

Note that $$ F_b (x,r,m) = \sum\limits_{0\,\, \leqslant \,\,s\,\,\left( { \leqslant \,\,r\,m} \right)} {N_b (s,r,m)\;x^{\,s} } = \left( {1 + x + \cdots + x^{\,r} } \right)^m = \left( {\frac{{1 - x^{\,r + 1} }}{{1 - x}}} \right)^m $$ is the ogf of $$N_{\,b} (s,r,m) = \text{No}\text{. of solutions to}\;\left\{ \begin{gathered} 0 \leqslant \text{integer }x_{\,j} \leqslant r \hfill \\ x_{\,1} + x_{\,2} + \cdots + x_{\,m} = s \hfill \\ \end{gathered} \right.$$ and that $$ N_b (s,r,m)\quad \left| {\;0 \leqslant \text{integers }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s}{r+1}\, \leqslant \,m} \right)} {\left( { - 1} \right)^k \binom{m}{k} \binom { s + m - 1 - k\left( {r + 1} \right) } { s - k\left( {r + 1} \right)}\ } $$ as explained in this related post

Now it is easy to see that $N_b (s,r,m)$ , among various properties, obeys to the symmetry $$ N_{\,b} (s,r,m) = N_{\,b} (mr - s,r,m) $$ that is that it has a maximum at $$ s = \left\lfloor {{{mr} \over 2}} \right\rfloor $$ which equals $$ \eqalign{ & \max N_b (s,r,m) = N_b \left( {\left\lfloor {{{mr} \over 2}} \right\rfloor ,r,m} \right) = \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,\,m} \right)} {\left( { - 1} \right)^k \left( \matrix{ m \hfill \cr k \hfill \cr} \right)\left( \matrix{ \left\lfloor {{{mr} \over 2}} \right\rfloor + m - 1 - k\left( {r + 1} \right) \cr \left\lfloor {{{mr} \over 2}} \right\rfloor - k\left( {r + 1} \right) \cr} \right)} \cr} $$

For large $m$ we can approximate the distribution with that of $m$ continuous uniform variables onto $[-1/2,r+1/2]$ , which is the Irwin-Hall distribution.
This in turn quickly converges, for the Central Limit theorem, to a Gaussian having as mean and variance $m$ times the mean and variance of a single uniform variable, for which we have the following prospect $$ \matrix{ {} & \mu & {\sigma ^{\,2} } & {{{\mu _{\,3} } \over {\sigma ^{\,3} }}} & {{{\mu _{\,4} } \over {\sigma ^{\,4} }}} & {CF(t)} \cr {discr.} & {{r \over 2}} & {{{\left( {r + 1} \right)^{\,2} - 1} \over {12}} = {{r\left( {r + 2} \right)} \over {12}}} & 0 & {{{9\left( {\left( {r + 1} \right)^{\,2} - 7/3} \right)} \over {5\left( {\left( {r + 1} \right)^{\,2} - 1} \right)}}} & {{{1 - e^{\,i\,\left( {r + 1} \right)t} } \over {\left( {r + 1} \right)\left( {1 - e^{\,i\,t} } \right)}}} \cr {contin.} & {{r \over 2}} & {{{\left( {r + 1} \right)^{\,2} } \over {12}}} & 0 & {{9 \over 5}} & {{{e^{\,i\left( {r + 1/2} \right)\,t} - e^{\, - i\,\left( {1/2} \right)t} } \over {i\left( {r + 1} \right)t}}} \cr } $$

So the Gaussian will be $$ \eqalign{ & p_{\,b} (s;r,m) = {{N_{\,b} (s,r,m)} \over {\left( {r + 1} \right)^{\,m} }} \approx {1 \over {\sqrt {2\pi m\sigma ^{\,2} } }}e^{\, - \,{{\left( {s - m\mu } \right)^{\,2} } \over {2m\sigma ^{\,2} }}} = \cr & = \left\{ \matrix{ {{\sqrt {6/\pi } } \over {\sqrt {m\left( {r\left( {r + 2} \right)} \right)} }}e^{\, - \,6{{\left( {s - mr/2} \right)^{\,2} } \over {m\left( {r\left( {r + 2} \right)} \right)}}} \hfill \cr {{\sqrt {6/\pi } } \over {\sqrt {m\left( {\left( {r + 1} \right)^{\,2} } \right)} }}e^{\, - \,6{{\left( {s - mr/2} \right)^{\,2} } \over {m\left( {\left( {r + 1} \right)^{\,2} } \right)}}} \hfill \cr} \right. \cr} $$ where

  • the first version uses the variance of a discrete variable, and corresponds to that indicated in Brian 's answer;
  • the second version instead uses the variance of a continuous variable.

It turns out that

  • the first version ensures that the peak of the Gaussian will be higher than the peak of $p_b$, already for $2 < m$;
  • while the second version provides a bit better global approximation, but the peak might undershoot that of $p_b$.

I do not have at the moment an analytical proof of that.

---- addendum in reply to your comment ----

One of the combinatoric interpretations of $N_b$ is that it represents the number of ways of laying down $s$ undistinguishable balls into $m$ distinguishable bins, each having a max capacity of $r$ balls.
Then the symmetry has the combinatoric explanation that it is the same matter as laying down $mr-s$ voids.

The unimodality instead follows from $$ \eqalign{ & F_b (x,r,m + n) = \left( {{{1 - x^{\,r + 1} } \over {1 - x}}} \right)^m \left( {{{1 - x^{\,r + 1} } \over {1 - x}}} \right)^n \quad \Rightarrow \cr & \Rightarrow \quad N_b (s,r,m + n) = \sum\limits_j {N_b (j,r,m)\;N_b (s - j,r,n)} \cr} $$ $N_b (s,r,1)$ is a flat histogram, $N_b (s,r,2)$ is triangular centered at $s= mr/2 =r $, thus unimodal. Therefore $N_b (s,r,3)$ is the convolution of a flat and a centred unimodal histogram, ...

4
On

The maximum coefficient in $(1+x+\cdots+x^{m−1})^i$ is asymptotically $$m^i \sqrt{\frac{6}{(m-1)(m+1)\pi i}}$$ according to Vaclav Kotesovec in several entries of the Online Encyclopedia of Integer Sequences, such as A025012 for the $m=7$ case.

As Dude mentioned in the comments, the question is about multinomial coefficients. You know binomial coefficients from $(1+x)^i$ that make up Pascal's triangle. The largest terms happen in the middle, the "central binomial coefficients" related to the famous Catalan numbers.

For $(1+x+x^2)^i$, the resulting coefficients are called trinomial coefficients (studied by Euler). The largest ones are still in the middle of each row in the resulting (wider) triangle A027907. For any $m$, the maximal multinomial coefficients are still the central ones; those explicit sequences are in the OEIS through $m=9$. The various sequences (listed under "crossrefs" from A025012 above) give references to various articles if you want to know more about the derivation of the asymptotic upper bound.

NB: Trinomial & multinomial are commonly used for two different notions. The ${ n \choose a, b, c}$ with $a+b+c=n$ usage is not what you want for your problem.

3
On

It seems to me there are two steps needed to solve your problem:

  1. Prove that the largest coefficient of $(1+\dots+x^m)^i$ is in the middle, at $\lfloor im/2 \rfloor$.

  2. Find a simple upper bound for the middle coefficient.

The other answers address $(2)$ (without proof), but no one has addressed $(1)$. I will prove $(1)$. This proof is due to Richard Stanley [1, Proposition 1].


More generally, you can prove that if $A(x)$ and $B(x)$ are polynomials whose coefficient sequences are symmetric, unimodal, and nonnegative, then all of these properties are enjoyed by the coefficient sequence of the product, $A(x)B(x)$. This lets you prove $(1+\dots+x^m)^i$ is unimodal by induction on $i$. Edit: Recall the definition of a sequence $(a_i)_{i=0}^n$ being unimodal is the existence of an index $m$ for which $$ a_0\le a_1\le \dots \le a_{m-1}\le a_m \ge a_{m+1}\ge \dots \ge a_n $$ To do this, write $A(x)=\sum_{i=0}^m a_ix^i$ and $B(x)=\sum_{i=0}^n b_jx^j$, and let $r=\lfloor m/2\rfloor$ and $s=\lfloor n/2\rfloor$. Then, (edit) adopting the convention $a_{-1}=b_{-1}=0$, $$ A(x)=\sum_{i=0}^r(a_i-a_{i-1})(x^i+x^{i+1}+\dots+x^{m-i})\\ B(x)=\sum_{j=0}^s(b_j-b_{j-1})(x^j+x^{j+1}+\dots+x^{n-j}) $$ so $$ A(x)B(x)=\sum_{i=0}^r\sum_{j=0}^s(a_i-a_{i-1})(b_j-b_{j-1})(x^i+x^{i+1}+\dots+x^{m-i})(x^j+x^{j+1}+\dots+x^{n-j}) $$ Since the polynomials $(x^i+x^{i+1}+\dots+x^{m-i})(x^j+x^{j+1}+\dots+x^{n-j})$ are symmetric with center $(m+n)/2$ and unimodal, and the coefficients $(a_i-a_{i-1})(b_j-b_{j-1})$ are nonnegative, it follows that $A(x)B(x)$ is unimodal as well.


[1]: Stanley, Log-Concave and Unimodal Sequences in Algebra, Combinatorics and Geometry, Annals of the New York Academy of Sciences, 576: 500-535; DOI: 10.1111/j.1749-6632.1989.tb16434.x. https://math.mit.edu/~rstan/pubs/pubfiles/72.pdf