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?

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

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.

  • $\begingroup$ I don't really understand your reasoning. It appears for instance that, the way you've written, $2$ always belongs to part 1. $\endgroup$ – Fimpellizieri Sep 16 '14 at 2:55
  • $\begingroup$ @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$. $\endgroup$ – Yuval Filmus Sep 16 '14 at 3:24
  • $\begingroup$ Ok, after careful thinking I finally understand it. Thank you. $\endgroup$ – Fimpellizieri Sep 16 '14 at 6:56

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.