Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm looking to find a combinatorial proof for the following: Fixing $k,n$ non-negative, I want that $$\sum a_1\dots a_k={n+k-1\choose 2k-1}$$ where the sum ranges over all $a_1+\dots +a_k=n$ with $a_i\ge 0$ $\forall i\in [k]$.

I guess I've sort of been looking at the right side with a modified "stars and bars" type mindset. I'll write down $n+k-1$ stars and then circle $2k-1$ of them. I'll sweep from left to right, putting stars in a bucket, and when I get to the second circle I put a line through it to start a new bucket. I continue putting things in that bucket passing the next circled star, and then drawing a line through the one after that. This should give me $k$ buckets with $a_i$ things in each one (and with the $\sum a_i=n$ since we crossed out every second circled star).

Is this the right bijection in some sense? I understand what I did but I'm not sure if I understand why what I did is right (if it is). Namely, what's the inverse procedure and what is the left side actually counting?

share|improve this question
add comment

2 Answers 2

up vote 4 down vote accepted

You’re on the right track. The $k-1$ circled stars in the even-numbered positions are the boundaries between your $k$ buckets, and the other $k$ circled stars pick one specific element from each bucket. Thus, $\binom{n+k-1}{2k-1}$ counts the number of ways to divide $n$ things into $k$ buckets and choose one thing from each bucket.

Now consider a particular vector of contents, $\langle a_1,\dots,a_k\rangle$, meaning $a_i$ things in the $i$-th bucket. How many times will this vector be counted in that binomial coefficient? Once for each way of choosing one object from each bucket, and there are $a_1a_2\dots a_k$ ways to do that. Thus, the content vector $\langle a_1,\dots,a_k\rangle$ gets counted $a_1a_2\dots a_k$ times in the binomial coefficient. And on the lefthand side you’re simply summing those products over all possible content vectors.

(Interesting identity; I’d not seen it before.)

share|improve this answer
2  
From a generating function view, the left side is just the $n$th coefficient of $$\left(\frac{z}{(1-z)^2}\right)^k$$ –  Thomas Andrews Apr 3 '13 at 20:33
    
Thank ya sir, very helpful. The identity came from a problem in Stanley's Enumerative Combinatorics. –  AsinglePANCAKE Apr 5 '13 at 4:34
    
@AsinglePANCAKE: You’re welcome. (I should have guessed: one of these days I’m going to have to take a thorough look at that book!) –  Brian M. Scott Apr 5 '13 at 4:37
add comment

Note that $$ 1x^1+2x^2+3x^3+4x^4+\dots=\frac{x}{(1-x)^2}\tag{1} $$ If we raise $(1)$ to the $k^{\text{th}}$ power, the coefficient of $x^n$ would be the sum of all products of $k$ positive integers that sum to $n$. That is, we want to find the coefficient of $x^{n-k}$ in $(1-x)^{-2k}$: $$ \begin{align} (-1)^{n-k}\binom{-2k}{n-k} &=\binom{n+k-1}{n-k}\\[6pt] &=\binom{n+k-1}{2k-1}\tag{2} \end{align} $$

share|improve this answer
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.