bounding coefficients in the extended Pascal's triangle.

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

-
$(1+x+x^2+\dots +x^n)^d$ is the rank generating function for a poset that is a d-fold product of chains, with each chain having $n+1$ elements in it. This is known to have a symmetric chain decomposition, implying this rank generating function is unimodal. That tells you that the largest coefficient $M(n,d)$ is the middle coefficient. I don't see immediately how to get from this a bound of the type that you want though. –  Patricia Hersh Aug 5 '12 at 1:09
This is a nice way of seeing the unimodality of the coefficients in the expansion. I've seen proofs that are more "elementary", as well as proofs of many relations resembling those of Pascal's triangle (thus the "extended" part). I've tried to use the unimodality as well as other identities of these coefficients, but I haven't been successful yet. Something like this should be true, though. After all, M(n,d) is the sum of multinomial coefficients. Thanks for your comment. –  user25532 Aug 5 '12 at 1:25
The convolution of log-concave distributions is log-concave, so this is log-concave, which is stronger then unimodal. –  Brendan McKay Aug 5 '12 at 7:59

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.

-
I see... too bad. On a related note, the following should be true: $$\frac{M(n,d+1)}{(n+1)^{d-1}}$$ tends to zero for fixed $n$ as $d$ tends to infinity, right? I'm not used to thinking about coefficients in the expansion in terms of probabilities –  user25532 Aug 5 '12 at 6:42
Yes, that goes to $0$ as $c/\sqrt{d}$. –  Douglas Zare Aug 5 '12 at 8:17

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$.

-

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$.

-
Is unimodality really needed here? –  user25532 Aug 6 '12 at 0:57
Perhaps you could use something weaker. –  Douglas Zare Aug 6 '12 at 1:46
What I mean is that I don't see where you used unimodality in your argument. –  user25532 Aug 6 '12 at 1:54
One use is that we want to evaluate the central term, not some isolated spike somewhere else. Second, we need some sort of continuity condition to turn the Central Limit Theorem's estimate on the sum of terms on an interval into an estimate on an individual term. Log-concavity means the terms around the largest can't be too small. –  Douglas Zare Aug 6 '12 at 3:43
In fact unimodality alone is insufficient right near the mean. Imagine increasing the single value in the middle and compensating by slightly decreasing nearby values. It can still satisfy the (cumulative) CLT yet the maximum is higher. However, log-concavity is sufficient. An early treatment is E. Rodney Canfield, Application of the Berry-Esséen inequality to combinatorial estimates, Journal of Combinatorial Theory, Series A, Volume 28, Issue 1, January 1980, Pages 17–25. –  Brendan McKay Aug 6 '12 at 6:04