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!

  • $\begingroup$ "I don't some work" is a misprint, right? Did you mean "I've done some work"? $\endgroup$ – Ewan Delanoy Mar 12 '11 at 12:09
  • 4
    $\begingroup$ Could you give the definition of the multi-indexed binomial coef? $\endgroup$ – shenghao Mar 12 '11 at 12:57
  • 1
    $\begingroup$ Have you tried replacing the coefficients with a bunch of gamma functions and the sum with an integral? $\endgroup$ – Steve Huntsman Mar 12 '11 at 16:16
  • $\begingroup$ Is there reason to suspect \alpha=q does not work? If so, what is that reason? Gerhard "Ask Me About System Design" Paseman, 2011.03.12 $\endgroup$ – Gerhard Paseman Mar 13 '11 at 1:33
  • $\begingroup$ Oh, I get it now. For each gamma, you are interested in the sum, and you want to know which gamma produces the largest sum, I'm guessing for all gamma with weight n? Gerhard "Time to Clean My Glasses" Paseman, 2011.03.12 $\endgroup$ – Gerhard Paseman Mar 13 '11 at 1:35

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy