of [n] into k nonempty subsets. First consider the total number of partitions, i.e. Bn where i.e. the Bell numbers. The Flajolet–Sedgewick fundamental theorem applies (labelled case). The set of partitions into non-empty subsets is given by ("set of non-empty sets of singletons") This decomposition is entirely analogous to the construction of the set of permutations from cycles, which is given by and yields the Stirling numbers of the first kind. Hence the name "Stirling numbers of the second kind." The decomposition is equivalent to the EGF Differentiate to obtain which implies that by convolution of exponential generating functions and because differentiating an EGF drops the first coefficient and shifts Bn+1 to z n/n!. The EGF of the Stirling numbers of the second kind is obtained by marking every subset that goes into the partition with the term , giving Translating to generating functions, we obtain This EGF yields the formula for the Stirling numbers of the second kind: or which simplifies to References Ronald Graham, Donald Knuth, Oren Patashnik (1989): Concrete Mathematics, Addison–Wesley, D. S. Mitrinovic, Sur une classe de nombre relies aux nombres de Stirling, C. R. Acad. Sci. Paris 252 (1961), 2354–2356. A. C. R. Belton, The monotone Poisson process, in: Quantum Probability (M. Bozejko, W. Mlotkowski and J. Wysoczanski, eds.), Banach Center Publications 73, Polish Academy of Sciences, Warsaw, 2006 Milton Abramowitz and Irene A. Stegun, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, USGPO, 1964, Washington DC, Enumerative combinatorics