# Combinatorial Proof of Binomial-type Identity

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?

• I assume $[k]=\{1,2,\ldots,k\}$? – Mr Pie Jun 4 '18 at 4:58

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.
• 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
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}