How do i maximize $\max_{\gamma}\sum_{|\alpha|=q}\binom{\alpha}{\gamma}$?

2011-03-12T11:48:16Z

I'm trying to find the following maximum: $\max_{\gamma}\sum_{|\alpha|=q}\binom{\alpha}{\gamma}$. Here $\alpha=(\alpha_1,\ldots, \alpha_n),\gamma=(\gamma_1,\ldots, \gamma_n)$ are multi-indices. The binomial coefficient is defined as $\binom{\alpha}{\gamma}=\frac{\alpha !}{\gamma! (\alpha-\gamma)!}=\prod_{i=1}^n \frac{\alpha_i !}{\gamma_i! (\alpha_i-\gamma_i)!}=\prod_{i=1}^n\binom{\alpha_i}{\gamma_i}$. We take the usual convention that $\binom{n}{r}=0$ if $r$ goes out of range, i.e. $r<0$ or $r>n$.

This maximum is well-defined and fully determined in terms of $n$ and $q$. Could anyone help?

Here is the solution for $n=1$. The sum $\sum_{|\alpha|=q}\binom{\alpha}{\gamma}$ is the single term $\binom{q}{\gamma}$, so the monotonicity of the binomial distribution gives the maximum at $\binom{q}{\lfloor q/2\rfloor}$.

For $n=2$, the problem amounts to maximizing $\max_{r,s}\sum_{i=0}^q \binom{i}{r}\binom{q-i}{s}=\max_{r,s}\sum_{i=r}^{q-s} \binom{i}{r}\binom{q-i}{s}$.

For general $n$, here is my very rough estimate. The basic inequality $\binom{\alpha}{\gamma}\le \binom{|\alpha|}{|\gamma|}$ implies $\max_\gamma \sum_{|\alpha|=q}\binom{\alpha}{\gamma}\le \max_{\gamma}\sum_{|\alpha|=q}\binom{q}{|\gamma|}\le \binom{n+q-1}{n}\binom{q}{\lfloor q/2\rfloor}$. The coefficient $\binom{n+q-1}{n}$ that pops out is the number of multi-indices $\alpha$ of length $q$.

More rewrites and updates to come. Thanks to Gerhard in advance!

Answer by Gjergji Zaimi for How do i maximize $\max_{\gamma}\sum_{|\alpha|=q}\binom{\alpha}{\gamma}$?

2011-03-13T07:00:24Z

I claim that $$\sum_{|\alpha|=q} \binom{\alpha}{\gamma}=\binom{n+q-1}{|\gamma|+n-1}$$ and so the answer is simply all $\gamma$ with $|\gamma|=\lfloor\frac{n+q-1}{2}\rfloor -n+1$. A quick proof comes from the following generating function $$\frac{x^l}{(1-x)^{l+1}}=\sum_{p=0}^{\infty} \binom{p}{l}x^p$$ and looking at the coefficient of $x^{n+q-1}$ in the identity $$x^{n-1}\prod_{i=1}^n \frac{x^{\gamma_i}}{(1-x)^{1+\gamma_i}}=\frac{x^{|\gamma|+n-1}}{(1-x)^{n+|\gamma|}}$$

How do i maximize $\max_{\gamma}\sum_{|\alpha|=q}\binom{\alpha}{\gamma}$? - MathOverflow

How do i maximize $\max_{\gamma}\sum_{|\alpha|=q}\binom{\alpha}{\gamma}$?

Answer by Gjergji Zaimi for How do i maximize $\max_{\gamma}\sum_{|\alpha|=q}\binom{\alpha}{\gamma}$?