Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
"I don't some work" is a misprint, right? Did you mean "I've done some work"? –  Ewan Delanoy Mar 12 '11 at 12:09
4  
Could you give the definition of the multi-indexed binomial coef? –  shenghao Mar 12 '11 at 12:57
1  
Have you tried replacing the coefficients with a bunch of gamma functions and the sum with an integral? –  Steve Huntsman Mar 12 '11 at 16:16
    
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 –  Gerhard Paseman Mar 13 '11 at 1:33
    
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 –  Gerhard Paseman Mar 13 '11 at 1:35
show 3 more comments

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer
    
thanks Gjergji! –  Colin Tan Mar 13 '11 at 9:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.