Combinatorial Proof of Binomial-type Identity

Question

I'm looking to find a combinatorial proof for the following:

Fix a positive integer $n$ and a non-negative integer $k$. Show that $$\sum a_1\dots a_k={n+k-1\choose 2k-1}$$ where the sum ranges over all $k$-tuples $\left(a_1,\ldots,a_k\right)$ of integers satisfying $a_1+\dots +a_k=n$ with $a_i\ge 0$ $\forall i\in [k]$.

Here, $\left[k\right]$ denotes the set $\left\{1,2,\ldots,k\right\}$.

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?

Answer 1

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.)

Answer 2

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