How do i maximize $\max_{\gamma}\sum_{|\alpha|=q}\binom{\alpha}{\gamma}$? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T01:05:47Z http://mathoverflow.net/feeds/question/58259 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/58259/how-do-i-maximize-max-gamma-sum-alphaq-binom-alpha-gamma How do i maximize $\max_{\gamma}\sum_{|\alpha|=q}\binom{\alpha}{\gamma}$? Colin Tan 2011-03-12T11:48:16Z 2011-03-13T07:00:24Z <p>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&lt;0$ or $r>n$.</p> <p>This maximum is well-defined and fully determined in terms of $n$ and $q$. Could anyone help? </p> <p>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}$.</p> <p>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}$.</p> <p>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$.</p> <p>More rewrites and updates to come. Thanks to Gerhard in advance!</p> http://mathoverflow.net/questions/58259/how-do-i-maximize-max-gamma-sum-alphaq-binom-alpha-gamma/58319#58319 Answer by Gjergji Zaimi for How do i maximize $\max_{\gamma}\sum_{|\alpha|=q}\binom{\alpha}{\gamma}$? Gjergji Zaimi 2011-03-13T07:00:24Z 2011-03-13T07:00:24Z <p>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|}}$$</p>