Why does $S(n,k)=\sum 1^{a_1-1}2^{a_2-1}\cdots k^{a_k-1}$?

Question

I've been trying to get back into some combinatorics, and in my reading, I find that $$ S(n,k)=\sum 1^{a_1-1}2^{a_2-1}\cdots k^{a_k-1} $$ where the sum is taken over all compositions $a_1+\cdots+a_k=n$. Here $S(n,k)$ denotes Stirling numbers of the second kind. I'm trying to understand why there is a combinatorial reason for this equality. So for each partition $\pi$ of $\{1,\dots,n\}$ into $k$ blocks, there should be an associated composition $a_1+\cdots+a_k=n$ such that exactly $1^{a_1-1}2^{a_2-1}\cdots k^{a_k-1}$ partitions are associated with this composition.

I read that by defining $a_1+\cdots+a_i$ to be the least $r$ such that removing $1,2,\dots,r$ from $\pi$ gives a resulting partition has $k-i$ blocks, shows this association.

My question is, why does this method work? The explanation is sparse, so I was hoping to see more detail. Thank you.

Answer 1

A slick generatingfunctionological approach uses a recursion formula. Let

$$f_k(x)=\sum_{n=k}^\infty \left\{n\atop k\right\}x^n.$$

$$=\left\{k\atop k\right\}x^k+\sum_{n=k}^\infty\left\{n+1\atop k\right\} x^{n+1}$$

$$=x^k+x\sum_{n=k}^\infty\left(k\left\{n\atop k\right\}+\left\{n\atop k-1\right\}\right)x^n$$

$$=x^k+x\left(kf_k(x)+f_{k-1}(x)-\left\{k-1\atop k-1\right\}x^{k-1}\right)$$

$$=kxf_k(x)+xf_{k-1}(x).$$

With $f_1(x)=x/(1-x)$ and $f_k(x)=x/(1-kx)\cdot f_{k-1}(x)$ we obtain by induction

$$f_k(x)=\frac{x}{1-kx}\;\cdots\;\frac{x}{1-2x}\frac{x}{1-x}=\prod_{l=1}^k\frac{x}{1-lx}$$

$$\large =\prod_{l=1}^k\left(\sum_{m_l=1}^\infty l^{m_l-1}x^{m_l}\right)=\sum_{n=k}^\infty \left(\sum_{m_1+\cdots+m_k=n}1^{m_1-1}2^{m_2-1}\cdots k^{m_k-1}\right)x^n.$$

Equate coefficients between the two power series and then our work here is done.

Answer 2

If $\pi$ is a $k$-partition of $[n]$, let $m_0(\pi),\dots,m_{k-1}(\pi)$ be the maximum elements of the $k$ parts of $\pi$ in descending order, so that necessarily $m_0(\pi)=n$. Removing the integers $\{1,\dots,m_{k-i}(\pi)\}$ removes $i$ parts of the partition, leaving $k-i$ parts.

Set $m_k(\pi)=0$, and for $i=1,\dots,k$ let $a_i(\pi)=m_{i-1}(\pi)-m_i(\pi)\ge 1$; clearly $$a_1(\pi)+\cdots+a_k(\pi)=n$$ is a $k$-composition of $n$.

Claim: Let $b_1+\cdots+b_k$ be any $k$-composition of $n$; then there are $1^{b_1-1}\cdot2^{b_2-1}\cdot\ldots\cdot k^{b_k-1}$ $k$-partitions $\pi$ of $[n]$ such that $a_i(\pi)=b_i$ for $i=1,\dots,k$.

As an example, take $n=5,k=3$, and the composition $1+2+2=5$. Which $3$-partitions $\pi$ of $[5]$ have $a_1(\pi)=1,a_2(\pi)=2$, and $a_3(\pi)=2$? For such a $\pi$ we must have $m_0(\pi)=5$, $m_1(\pi)=5-1=4$, and $m_2(\pi)=4-2=2$. With a little work we find that the partitions in question are $$\begin{align*} &\big\{\{1,3,4\},\{2\},\{5\}\big\},\\ &\big\{\{1,3,5\},\{2\},\{4\}\big\},\\ &\big\{\{1,2\},\{3,4\},\{5\}\big\},\\ &\big\{\{1,2\},\{3,5\},\{4\}\big\},\\ &\big\{\{1,4\},\{3,5\},\{2\}\big\},\text{ and}\\ &\big\{\{1,5\},\{3,4\},\{2\}\big\}, \end{align*}$$ so there are indeed $1^{1-1}\cdot2^{2-1}\cdot3^{2-1}$ of them.

Proof of Claim: Suppose, now, that $b_1+\cdots+b_k$ is a $k$-composition of $n$. In order for a $k$-partition $\pi$ of $[n]$ to satisfy the condition that $a_i(\pi)=b_i$ for $i=1,\dots,k$, it must satisfy the condition that $m_i(\pi)=m_{i+1}(\pi)+b_{i+1}$ for $i=0,\dots,k-1$ (where we set $m_k(\pi)=0$).

In particular, $m_{k-1}=b_k$, so there are $b_k-1$ positive integers less than $m_{k-1}$; clearly each of them can go into any of the $k$ parts of $\pi$. There are $b_{k-1}-1$ positive integers less than $m_{k-2}$ and greater $m_{k-1}$; they cannot go in the part whose maximum element is $m_{k-1}$, but they can go into any of the other $k-1$ parts of of $\pi$. And in general there are $b_i-1$ positive integers that are less than $m_{i-1}$ and greater than $m_i$, each of which can go into any of the $i$ parts of $\pi$ whose maximum elements are in the set $\{m_0(\pi),\dots,m_{i-1}(\pi)\}$ bit not into any of the parts with smaller maximum elements. Thus, these $n-k$ non-maximal elements can be distributed amongst the $k$ parts in

$$\prod_{i=1}^k i^{b_i-1}=1^{b_1-1}\cdot2^{b_2-1}\cdot\ldots\cdot k^{b_k-1}$$

different ways. $\dashv$