Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
Thanks anon, this is very slick indeed. :) –  Clara Jan 31 '12 at 4:06
add comment

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$

share|improve this answer
    
Thanks for the example and explanation! –  Clara Jan 31 '12 at 4:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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