# Enumerative Combinatorics problem from Stanley

Fix $k,n\in P$. Show that $\sum a_1\times...\times a_k={n+k-1\choose 2k-1}$, where the sum ranges over all compositions $(a_1,...,a_k)$ of n into $k$ parts. I have no idea how to do it.

You have a row of $n$ green olives on the table. You insert $k-1$ toothpicks into the row, dividing it into $k$ non-empty segments. Each of the $\binom{n+k-1}{k-1}$ ways of doing this corresponds to one of the $\binom{n+k-1}{k-1}$ compositions of $n$ into $k$ parts: if $a_i$ is the number of olives in the $i$-th segment, the composition is $a_1+\ldots+a_k=n$.

Now consider the olive-and-toothpick row corresponding to the composition $a_1+\ldots+a_k=n$; there are $a_i$ ways to choose an olive from the $i$-th segment and replace it with a black olive, so there are $a_1a_2\ldots a_k$ ways to one olive from each segment with a black olive. Thus, the lefthand side of your identity is the number of ways to insert the $k-1$ toothpicks and then replace one olive from each of the resulting $k$ segments with a black olive.

Alternatively, we could start with a string of $n+k-1$ positions on the table and choose $2k-1$ of them, say positions $p_1<p_2<\ldots<p_{2k-1}$. We’ll put a toothpick in each of the $k-1$ positions $p_2,p_4,\ldots,p_{2k-2}$ and a block olive in each of the positions $p_1,p_3,\ldots,p_{2k-1}$, and we’ll put a green olive in each of the remaining $(n+k-1)-(2k-1)=n-k$ positions. We then have one of the possible outcomes of the first procedure, and every outcome of the first procedure can be obtained uniquely in this way, so we’ve simply counted the same strings of olives and toothpicks in a different way. Clearly this procedure can be carried out in $\binom{n+k-1}{2k-1}$ ways, so the identity is established.

Added: A proof by induction on $k$ is also possible. Let $\varphi(n,k)$ be the sum on the lefthand side of the identity. Then $\varphi(k,k)=1$ for all $k$, and for any $n>k$ we also have the recurrence

$$\varphi(n,k+1)=\sum_{\ell=1}^{n-k}\ell\varphi(n-\ell,k)\;.$$

Suppose that

$$\varphi(n,k)=\binom{n+k-1}{2k-1}$$

for all $n\ge k$, and let $n\ge k+1$. Then

\begin{align*} \varphi(n,k+1)&=\sum_{\ell=1}^{n-k}\ell\varphi(n-\ell,k)\\ &=\sum_{\ell=1}^{n-k}\ell\binom{n-\ell+k-1}{2k-1}\\ &=\sum_{\ell=2k-1}^{n+k-2}(n+k-1-\ell)\binom{\ell}{2k-1}\\ &=(n+k)\sum_{\ell=2k-1}^{n+k-2}\binom{\ell}{2k-1}-\sum_{\ell=2k-1}^{n+k-2}(\ell+1)\binom{\ell}{2k-1}\\ &=(n+k)\binom{n+k-1}{2k}-2k\sum_{\ell=2k-1}^{n+k-2}\binom{\ell+1}{2k}\\ &=(n+k)\binom{n+k-1}{2k}-2k\binom{n+k}{2k+1}\\ &=(2k+1)\binom{n+k}{2k+1}-2k\binom{n+k}{2k+1}\\ &=\binom{n+k}{2k+1}\\ &=\binom{n+(k+1)-1}{2(k+1)-1}\;, \end{align*}

and the result follows by induction.

• I'm not sure if I fully understand the alternative way. – John Dynan Oct 2 '15 at 15:41
• @John: It’s just a matter of picking out the $2k-1$ positions for the toothpicks and black olives all at once instead of in two separate steps. The black olives must alternate with the toothpicks in order to make sure that there’s one black olive in each segment between toothpicks (and before the first and after the last toothpick). – Brian M. Scott Oct 2 '15 at 15:46
• Why not n choose n-k? I know this is wrong, but I don't understand why. – John Dynan Oct 2 '15 at 15:49
• What if there are two toothpicks standing together? No olives in between. In the first way that you mentioned, it can be interpreted as some ai is zero, and that is not allowed. – John Dynan Oct 2 '15 at 15:54
• @John: That corresponds to starting with a row of $n$ olives and choosing which $n-k$ of them are to be black. That tells you a little bit about where the toothpicks go – there must be one between every pair of adjacent black olives – but it doesn’t completely determine their positions. Thus, you’re lumping together several different arrangements and counting them as just one. – Brian M. Scott Oct 2 '15 at 15:55

It suffices to prove they have the same generating function:

\begin{align*} \sum\limits_{n} \sum a_1\cdots a_k x^n &= \sum\limits_{1\leq a_1,\ldots,a_k} a_1\cdots a_k x^{a_1 + \ldots + a_k} \\ &= \left( \frac{x}{(1 - x)^2} \right)^k \\ &= x^k \left( \frac{1}{(1 - x)^{2k}}\right) \\ &= x^k \sum\limits_n \binom{n - k + 2k - 1}{n - k}x^{n-k} \\ &= \sum\limits_{n} \binom{n + k - 1}{2k - 1}x^n. \end{align*}

• how do you get the second line from the first line? could you explain a little bit more ? – ramgorur Oct 19 '16 at 21:15