Skip to main content

Let $S_{n, k}$ denote the number of partitions of a set of size $n$ into $k$ partitions (the Stirling numbers of the second kind), so that $B_n = \displaystyle \sum_{k=0}^n S_{n, k}$ and hence, exchanging the order of summation, we have

$$\sum_{n=0}^{\infty} B_n t^n = \sum_{n=0}^{\infty} \sum_{k=0}^n S_{n, k} t^n = \sum_{k=0}^{\infty} t^k \sum_{n=k}^{\infty} S_{n, k} t^{n-k}.$$

A standard identity whose proof I used to know but have now forgotten asserts that

$$\sum_{n=k}^{\infty} S_{n, k} t^{n-k} = \frac{1}{(1 - t)(1 - 2t)...(1 - kt)}$$$$\sum_{n=k}^{\infty} S_{n, k} t^{n-k} = \frac{1}{(1 - t)(1 - 2t)\cdots(1 - kt)}$$

and this gives your formula. This is identity 1.94c in the second edition of Stanley's Enumerative Combinatorics, Volume I.

Let $S_{n, k}$ denote the number of partitions of a set of size $n$ into $k$ partitions (the Stirling numbers of the second kind), so that $B_n = \displaystyle \sum_{k=0}^n S_{n, k}$ and hence, exchanging the order of summation, we have

$$\sum_{n=0}^{\infty} B_n t^n = \sum_{n=0}^{\infty} \sum_{k=0}^n S_{n, k} t^n = \sum_{k=0}^{\infty} t^k \sum_{n=k}^{\infty} S_{n, k} t^{n-k}.$$

A standard identity whose proof I used to know but have now forgotten asserts that

$$\sum_{n=k}^{\infty} S_{n, k} t^{n-k} = \frac{1}{(1 - t)(1 - 2t)...(1 - kt)}$$

and this gives your formula. This is identity 1.94c in the second edition of Stanley's Enumerative Combinatorics, Volume I.

Let $S_{n, k}$ denote the number of partitions of a set of size $n$ into $k$ partitions (the Stirling numbers of the second kind), so that $B_n = \displaystyle \sum_{k=0}^n S_{n, k}$ and hence, exchanging the order of summation, we have

$$\sum_{n=0}^{\infty} B_n t^n = \sum_{n=0}^{\infty} \sum_{k=0}^n S_{n, k} t^n = \sum_{k=0}^{\infty} t^k \sum_{n=k}^{\infty} S_{n, k} t^{n-k}.$$

A standard identity whose proof I used to know but have now forgotten asserts that

$$\sum_{n=k}^{\infty} S_{n, k} t^{n-k} = \frac{1}{(1 - t)(1 - 2t)\cdots(1 - kt)}$$

and this gives your formula. This is identity 1.94c in the second edition of Stanley's Enumerative Combinatorics, Volume I.

Source Link
Qiaochu Yuan
  • 118.2k
  • 40
  • 447
  • 741

Let $S_{n, k}$ denote the number of partitions of a set of size $n$ into $k$ partitions (the Stirling numbers of the second kind), so that $B_n = \displaystyle \sum_{k=0}^n S_{n, k}$ and hence, exchanging the order of summation, we have

$$\sum_{n=0}^{\infty} B_n t^n = \sum_{n=0}^{\infty} \sum_{k=0}^n S_{n, k} t^n = \sum_{k=0}^{\infty} t^k \sum_{n=k}^{\infty} S_{n, k} t^{n-k}.$$

A standard identity whose proof I used to know but have now forgotten asserts that

$$\sum_{n=k}^{\infty} S_{n, k} t^{n-k} = \frac{1}{(1 - t)(1 - 2t)...(1 - kt)}$$

and this gives your formula. This is identity 1.94c in the second edition of Stanley's Enumerative Combinatorics, Volume I.