Talk:Stirling numbers of the second kind

From Wikipedia, the free encyclopedia

[edit] Unclear

I'm removing a large block of text from this article, because it is unclear. The problems are:

  • Use of blackpage symbols without any attempt to explain their meaning
  • Use of the term "EGF" without explaining what it means. Is this, perhaps, the exponential generating function? or something else?
  • Use of the symbol [xn] without explanation. Clearly, its not equal to xn, but I can't figure out what its supposed to be.
  • Most of the text appears to be a long proof, and, as such, is not appropriate for article space. See Category:Article proofs for examples on how to deal with proofs.

linas 02:16, 29 December 2006 (UTC)

[edit] Generating functions

These numbers count the number of partitions of [n] into k nonempty subsets. First consider the total number of partitions, i.e. Bn where

B_n = \sum_{k=1}^n \left\{\begin{matrix} n \\ k \end{matrix}\right\} \mbox{ and } B_0 = 1,

i.e. the Bell numbers. The fundamental theorem of combinatorial enumeration applies (labelled case). The set \mathcal{B}\, of partitions into non-empty subsets is given by ("set of non-empty sets of singletons")

\mathcal{B} = \mathfrak{P}(\mathfrak{P}_{\ge 1}(\mathcal{Z})).

This decomposition is entirely analogous to the construction of the set \mathcal{P}\, of permutations from cycles, which is given by

\mathcal{P} = \mathfrak{P}(\mathfrak{C}(\mathcal{Z})).

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

B(z) = \exp \left(\exp z - 1\right).

Differentiate to obtain

\frac{d}{dz} B(z) = \exp \left(\exp z - 1\right) \exp z = B(z) \exp z,

which implies that

B_{n+1} = \sum_{k=0}^n {n \choose k} B_k,

by convolution of exponential generating functions and because differentiating an EGF drops the first coefficient and shifts Bn + 1 to zn / 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 \mathcal{U}\,, giving

\mathcal{B} = \mathfrak{P}(\mathcal{U} \; \mathfrak{P}_{\ge 1}(\mathcal{Z})).

Translating to generating functions, we obtain

B(z, u) = \exp \left(u \left(\exp z - 1\right)\right).

This EGF yields the formula for the Stirling numbers of the second kind:

\left\{\begin{matrix} n \\ k \end{matrix}\right\} = n! [u^k] [z^n] B(z, u) = n! [z^n] \frac{(\exp z - 1)^k}{k!}

or

n! [z^n] \frac{1}{k!} \sum_{j=0}^k {k \choose j} \exp(jz) (-1)^{k-j}

which simplifies to

\frac{n!}{k!} \sum_{j=0}^k {k \choose j} (-1)^{k-j} \frac{j^n}{n!} = \frac{1}{k!} \sum_{j=0}^k {k \choose j} (-1)^{k-j} j^n.

We can use B(z,u) to evaluate the sum

\sum_{k=0}^n \left\{\begin{matrix} n \\ k \end{matrix}\right\} (x)_k.

This is equal to

\sum_{k=0}^n n! [u^k] [z^n] B(z, u) (x)_k = n! [z^n] \sum_{k=0}^n [u^k] B(z, u) (x)_k

or

n! [z^n] \sum_{k=0}^n \frac{(\exp z - 1)^k}{k!} (x)_k = n! [z^n] \sum_{k=0}^\infty \frac{(\exp z - 1)^k}{k!} (x)_k

where the last equality occurs because [z^n] (\exp z - 1)^k = 0\, when n<k\,.

Now consider the Taylor series of yx at y = 1:

y^x = \sum_{k=0}^\infty \left( \left(\frac{d}{dy}\right)^k y^x \Bigg|_{y=1} \right) \frac{(y-1)^k}{k!} = \sum_{k=0}^\infty (x)_k \frac{(y-1)^k}{k!}.

Hence

\sum_{k=0}^n \left\{\begin{matrix} n \\ k \end{matrix}\right\} (x)_k = n! [z^n] \exp(xz) = n! \frac{x^n}{n!} = x^n.
Retrieved from "http://en.wikipedia.org../../../s/t/i/Talk%7EStirling_numbers_of_the_second_kind_24a0.html"