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.


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


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


$$\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.

  • $\begingroup$ Thanks anon, this is very slick indeed. :) $\endgroup$ – Clara Jan 31 '12 at 4:06

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$

  • $\begingroup$ Thanks for the example and explanation! $\endgroup$ – Clara Jan 31 '12 at 4:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.