|
|
|
|
![[parent]](http://images.planetmath.org:8080/images/uparrow.png)
derivation of the generating series for the Stirling numbers of the second kind
|
(Derivation)
|
|
|
The derivation of the generating series is much simpler if one makes use of the composition lemma for exponential generating series. We are looking for the generating series for sets of nonempty sets, so in the notation of Jackson and Goulden, we have the set decomposition:
where $\mathcal{U}$ is the set of all canonical unordered sets, $\mathcal{A}$ is the set which we are interested in counting, and $\circledast$ is star-composition of sets of labelled combinatorial objects.
The set $\mathcal{U}$ has one object in it of each weight, and so has exponential generating series:
The set $\mathcal{U} \backslash \{\emptyset\}$ then has generating series:
So, by the star composition lemma and the above decomposition, \begin{eqnarray*} [(\mathcal{A}, \omega)]_e (x) &=& [(\mathcal{U} \circledast (\mathcal{U} \backslash \{\emptyset\}), \omega)]_e (x)\\ &=&\left([(\mathcal{U}, \omega)]_e \circ [(\mathcal{U} \backslash \{\emptyset\}, \omega)]_e\right) (x)\\ &=&e^{e^x - 1} \end{eqnarray*} By tensoring the weight function $\omega$ with a weight function $\lambda$ counting the number of parts each set partition contains, we get
using a derivation similar to the one above.
|
"derivation of the generating series for the Stirling numbers of the second kind" is owned by cgibbard.
|
|
(view preamble | get metadata)
Cross-references: similar, contains, set partition, number, function, star, has exponential, weight, objects, canonical, decomposition, exponential, composition, series, generating, derivation
This is version 3 of derivation of the generating series for the Stirling numbers of the second kind, born on 2005-05-01, modified 2005-05-03.
Object id is 6992, canonical name is DerivationOfTheGeneratingSeriesForTheStirlingNumbersOfTheSecondKind.
Accessed 1778 times total.
Classification:
| AMS MSC: | 05A15 (Combinatorics :: Enumerative combinatorics :: Exact enumeration problems, generating functions) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
![$\displaystyle [(\mathcal{U}, \omega)]_e (x) = \sum_{n\geq 0} {x^n\over n!} = e^x $](http://images.planetmath.org:8080/cache/objects/6992/js/img2.png "$\displaystyle [(\mathcal{U}, \omega)]_e (x) = \sum_{n\geq 0} {x^n\over n!} = e^x $")
![$\displaystyle [(\mathcal{U} \backslash \{\emptyset\}, \omega)]_e (x) = e^x - 1 $](http://images.planetmath.org:8080/cache/objects/6992/js/img3.png "$\displaystyle [(\mathcal{U} \backslash \{\emptyset\}, \omega)]_e (x) = e^x - 1 $"){kind=small}
![$\displaystyle [(\mathcal{A}, \omega \otimes \lambda)]_{e,o} (x,t) = e^{t (e^x - 1)} $](http://images.planetmath.org:8080/cache/objects/6992/js/img4.png "$\displaystyle [(\mathcal{A}, \omega \otimes \lambda)]_{e,o} (x,t) = e^{t (e^x - 1)} $"){kind=small}