# Combinatorial identity on partitions

In Stanley's Enumerative Combinatorics, there is the following identity

$$\sum_{n \geq k}S(n,k) x^n = \frac{x^k}{(1-x)(1-2x) \dots (1-kx)}$$

where $S(n,k)$ denotes the number of partitions of an $n$-set into $k$ blocks. (A partition of an $n$-set $N$ into $k$ blocks is a collection of $k$ non-empty and disjoint of subsets of $N$ whose union is $N$).

What I have tried, following Stanley's perceived advice is expanding the denominator terms

$$\frac{1}{1-ax} = \sum_{n \geq 0} a^nx^n$$

so that

$$\sum_{n \geq k}S(n,k) x^n = x^k \left(\sum_{n \geq 0} x^n\right)\left(\sum_{n \geq 0} 2^nx^n\right)\dots\left(\sum_{n \geq 0} k^nx^n\right)$$

and then comparing coefficients. What I obtained is that for $n = k + q$, $q \geq 0$, then

$$\Large \sum_{\substack{(q_1,q_2, \dots, q_k) \\q_1,q_2,\dots,q_k \geq 0 \\ \sum_{i=1}^n = q}} 1^k1^{q_1}2^{q_2}\dots k^{q_k} = S(n,k)$$

but I fail to grasp how this sum represents $S(n,k)$. I understand the summation goes over $k$-compositions of $n$ but I can't seem to relate it to $S(n,k)$, neither combinatorially nor by the closed form expression

$$S(n,k) = \frac{1}{k!}\sum_{i=0}^k(-1)^{k-i}\binom{k}{i}i^n$$

Maybe I'm entirely on the wrong track. Any ideas?

• There are two proofs by different users at this MSE link. – Marko Riedel Sep 16 '14 at 21:38

## 1 Answer

Here is the idea. Suppose without loss of generality that $N = \{1,\ldots,n\}$, and let $p_1,\ldots,p_n \in \{1,\ldots,k\}$ be a partition of $N$ into non-empty parts. We assume that different parts appear in increasing order, that is, the first part appearing is number $1$, the second part appearing is number $2$, and so on (so, for example, a list starting $1,3,\ldots$ is illegal). For $t \in \{1,\ldots,k\}$, let $j_t$ be the first index $j$ such that $p_j = t$. For example, for $n = 5$ and the partition $1,1,2,1,2$, we have $j_1 = 1$ and $j_2 = 3$. Also, let $j_{k+1} = n+1$.

By definition, $p_{j_1} = 1$, $p_{j_2} = 2$, and so on. Moreover, $p_{j_t+1},\ldots,p_{j_{t+1}-1} \in \{1,\ldots,t\}$, with no further constraints. So given a choice of $j_1,\ldots,j_k$, we have $1^{j_2-j_1-1} 2^{j_3-j_2-1} \cdots k^{j_{k+1}-j_k-1}$ possible partitions. Hopefully you can take it from here.

• I don't really understand your reasoning. It appears for instance that, the way you've written, $2$ always belongs to part 1. – Fimpellizieri Sep 16 '14 at 2:55
• @Fimpellizieri Rewrote the answer, hope this version is clearer. In particular, $j_2$ always belongs to $2$, but $j_2$ doesn't have to be $2$. – Yuval Filmus Sep 16 '14 at 3:24
• Ok, after careful thinking I finally understand it. Thank you. – Fimpellizieri Sep 16 '14 at 6:56