bounding coefficients in the extended Pascal's triangle.

Question

Hi,

Here is what I want to know:

Let $M(n,d)$ be the largest coefficient in the expansion of $(1+x+x^2+\cdots+x^n)^d$ and $C(n,d)$ be $$ C(n,d):=\max\{\binom{d}{k_0,k_1,\ldots,k_n}\}\text{, $k_0+\cdots+k_n=d$}, $$

That is, the maximum multinomial among the multinomial coefficients $\binom{d}{k_0,k_1,\ldots,k_n}$ with $k_0+\cdots+k_n=d$.

I'm trying to bound $M(n,d)$ in terms of $C(n,d)$. I think something along the lines of $$ M(n,d)\leq\binom{n+1}{\lfloor(n+1)/2\rfloor}C(n,d) $$ should work. I don't want the constant [which is the $\binom{n+1}{\lfloor(n+1)/2\rfloor}$ above] to depend on $d$. Any thoughts?

Thanks,

SB

Answer 1

I don't believe any such inequality is possible.

The $x^k$ coefficient of $(1+\dots+x^n)^d$ is $(n+1)^d$ times $P(X_1+\dots+X_d=k)$, where $X_i$ are iid variables uniform on $\{0,1,2,\dots,n\}$.

If we fix $n$ and let $d$ tend to infinity, then the maximal concentration of $X_1+\dots+X_d$ decays at least as slowly as $C_n d^{-1/2}$ for some constant $C_n$ depending on $n$ (e.g. because by Chebyshev's inequality the sum lies within $-C \sqrt{d}$ and $C\sqrt{d}$ of the mean with probability at least $1/2$ for large $C$, so by pigeonhole some value in that range is likely).

Similarly, the multinomial coefficient $\binom{d}{k_0,\dots,k_n}$ can be thought of as $(n+1)^d$ times $P\left(Y_1+\dots+Y_d=(k_0,k_1,\dots,k_n)\right)$, where the $Y_i$ are iid variables uniform on vectors of the form $(0,\dots,0,1,0,\dots,0)$.

If we fix $n$ and let $d$ tend to infinity, then the maximal concentration of this sum should decay at least as quickly as $c_n d^{-n/2}$. I assume this is well known somewhere, but here's a rough idea for such a bound. It's very unlikely (probability exponentially small in $d$) for any coordinate to be far away from $\frac{d}{n+1}$. So now suppose that all the $k_i$ are near $\frac{d}{n+1}$. Then the probability the first coordinate equals $k_0$, the probability the second coordinate equals $k_1$ given the first coordinate equals $k_0$, and so on up to the probability the second to last coordinate is equal to $k_{n-1}$ given the previous coordinates are all at most $C_n d^{-1/2}$, where $C_n$ is again a constant depending on $n$.

Combining these bounds, the ratio $\frac{M(n,d)}{C(n,d)}$ tends to infinity for fixed $n$ as $d$ tends to infinity.

Answer 2

If $d\to\infty$ sufficiently much faster than $n\to\infty$, you can get an estimate of $M(n,d)$ using the central limit theorem. The uniform distribution on $\{0,1,\ldots,n\}$ has variance $n(n+2)/12$, so its $d$-fold convolution has variance $dn(n+2)/12$. For $d\to\infty$ quickly enough relative to $n$, this gives $$ M(n,d) \sim (n+1)^d \frac{\sqrt{6}}{n\sqrt{\pi d}}.$$ I predict that it is out by at most a constant for any $n,d\ge 1$. Use Stirling's formula to estimate the central multinomial coefficient, then you will see the true nature of their relationship.

Added: Douglas gave his answer while I was typing and correctly used a factor of 2 that I got wrong so I'm putting it in. Using the exact value of the variance, the estimate seems quite accurate even for tiny $n,d$.

Answer 3

I hope the computations don't obscure the intuition here. $C(n,d)/M(n,d)$ is a conditional probability. Imagine rolling $6$ dice and getting the most common total, $21$. The conditional probability that each number came up exactly once is small, but it wouldn't be terribly shocking for this to be the case. Suppose you roll $6000$ dice and get a total of $21000$. Now, what's the conditional probability that exactly $1000$ of the dice showed a $1$, ... and exactly $1000$ showed $6$? It would be much more of a surprise, and the conditional probability isn't bounded away from $0$ as the number of dice increases. That said, here are some computations:

For each fixed $n$, you can use the Central Limit Theorem and log-convexity to obtain the asymptotics of $M(n,d)$ (Brendan McKay pointed out that unimodality is not enough to get an upper bound on $M(n,d)$). The coefficients of $(\frac{1+x+...+x^n}{n+1})^d$ are approximately normal. The standard deviation is $\sigma = \sqrt{d (n^2+2n)/12}$, and $\frac{M(n,d)}{(n+1)^d} \approx \frac {1}{\sqrt{2 \pi}}\sigma^{-1}$ since the peak of the density of the standard normal distribution is $\frac{1}{\sqrt{2\pi}}$. So, for fixed $n$,

$$M(n,d) \approx (n+1)^d \sqrt{\frac{6}{\pi d(n^2+2n)}}.$$

Another application of the Central Limit Theorem would also approximate $C(n,d)$ but Stirling's formula is simpler. All powers of $e$ and most powers of $d$ cancel.

$${d \choose \frac {d}{n+1},\frac{d}{n+1},...\frac{d}{n+1}} = \frac{d!}{{\frac {d}{n+1}}!^{n+1}}$$

$$\approx \sqrt{2\pi d} \bigg/ \bigg[\bigg(\frac{1}{n+1}\bigg)^d \sqrt{2 \pi \frac{d}{n+1}}^{n+1}\bigg]$$

$$\approx (n+1)^{d+(n+1)/2} (2\pi d)^{-n/2} $$.

When $d$ is large but not divisible by $n+1$ the most even integral division is not much different.

The quotient $M(n,d)/C(n,d)$ is proportional to some function of $n$ times $d^{(n-1)/2},$ so there is no upper bound for the quotient only depending on $n$, and you can't bound the conditional probability $C(n,d)/M(n,d)$ away from $0$ regardless of $d$.