combinatorics: sum of product of integer compositions

I am trying to solve a problem from Stanley's book, it says:

Fix $k,n \in \mathbb{P}$. Show that: \begin{align} \sum a_1 a_2 \cdots a_k = \binom{n+k-1}{2k-1} \end{align} where the sum ranges over all compositions $(a_1 , a_2 , \ldots , a_k)$ of $n$ into $k$ parts.

I am trying to reason like this:

we need to find the coefficient $c_n = \sum a_1 a_2 \cdots a_k$ from this generating function --

\begin{align} \sum_n c_n x^n &= \sum_n \sum a_1 a_2 \cdots a_k x^n \\ &= \sum_n \sum a_1 a_2 \cdots a_k x^{a_1 + a_2 + \cdots + a_k}\\ &= \sum_n \sum a_1x^{a_1} a_2x^{a_2} \cdots a_kx^{a_k} \end{align}

after that, I have no clue, how do I solve this ?

moreover, what is the range in the inner sum ?

If we consider Mark Riedel's answer, and assume $n=4$, $k=2$; then the sum will be \begin{align} \sum (z + 2z^2)^2 = z^2 + 4z^3 + 4z^4 \end{align}

On the other hand the compositions will be $(1,3), (2,2), (3,1)$, therefore the above sum will be counted as:

\begin{align} (1.3)z^{1+3} + (2.2)z^{2+2} + (3.1)z^{3+1} &= 1z^1.3z^3 + 2z^2.2z^2 + 3z^3.1z^1\\ &= 3z^4 + 4z^4 + 3z^4 = 10z^4 \end{align}

what's going on? what am I missing?

Solution 1:

Compositions of $n$ into $k$ parts can be represented as a string of $n$ stars and $k-1$ bars. The $k-1$ bars break the stars into $k$ groups, and the number of stars in the $i^{th}$ group represents $a_i$.

For each of these compositions, we are adding $a_1a_2\dots a_k$. This represents the number of ways to choose one star from each of the $k$ blocks, and color it red. For example, with $n=6, k=3$, and the composition $\star\star|\star\star\star|\star$, the number of ways to color one star in each group red like $\star\color{red}\star|\star\color{red}\star\star|\color{red}\star$ would be $2\cdot 3\cdot 1$.

However, there is a more direct way to count these arrangements of black stars, red stars, and bars. If you ignore the black stars, then what remains is an alternating pattern of red stars and bars; in the example, this is $\color{red}\star|\color{red}\star|\color{red}\star$. There are $k+(k-1)=2k-1$ symbols which are red stars or bars, and $n+k-1$ symbols total. Therefore, there are $\binom{n+k-1}{2k-1}$ arrangements, since an arrangement is specified by choosing which of the $2k-1$ symbols are red stars or bars, and then assigning these in an alternating fashion.

Solution 2:

We have using generating functions the closed form

$$[z^n](z+2z^2+3z^3+\cdots)^k = [z^n] \frac{z^k}{(1-z)^{2k}} \\ = [z^{n-k}] \frac{1}{(1-z)^{2k}}.$$

Using the Newton binomial this becomes $${n-k+2k-1\choose 2k-1} = {n+k-1\choose 2k-1}.$$

Solution 3:

This is a supplement to @MarkoRiedel's answer which should clarify OPs question. At first we look at the compositions of $n=4$ which consists of two terms ($k=2$) and look at the corresponding terms of the generating function.

\begin{array}{crl} 1+3\qquad&\qquad x^1\cdot3x^3=&3x^4\\ 2+2\qquad&\qquad2 x^2\cdot 2 x^2=&4x^4\\ 1+3\qquad&\qquad3 x^3\cdot x^1=&3x^4\\ \end{array}

When looking at the three compositions above, we see the first summand is either $1$ or $2$ while the second summand is either $3$ or $2$. In general the first summand is a positive integer encoded as generating function \begin{align*} (x^1+2x^2+3x^3+\cdots)=\sum_{n=1}^\infty n x^n=x\frac{d}{dx}\left(\frac{1}{1-x}\right)=\frac{x}{(1-x)^2} \end{align*} The same holds for all the other summands of a composition. Since we want to multiply the summands and $k=2$ we have to consider \begin{align*} (x^1+2x^2+3x^3+\cdots)^2=\frac{x^2}{(1-x)^4}\tag{1} \end{align*}

We use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$.

The number of compositions of $n=4$ is according to (1) \begin{align*} [x^4](x^1+2x^2+3x^3+\cdots)^2&=[x^4](x^1+2x^2+3x^3)^2\tag{2}\\ &=([x^3]+2[x^2]+3[x^1])(x^1+2x^2+3x^3)\tag{3}\\ &=3+2\cdot 2+3\\ &=\color{blue}{10} \end{align*}

Comment:

In (2) we see it is sufficient to consider terms with exponents up to $3$, since higher exponents do not contribute to $x^4$.
In (3) we use the linearity of the coefficient of operator and apply the rule $$[x^p]x^qA(x)=[x^{p-q}]A(x)$$