Talk:Stirling numbers of the second kind

From Wikipedia, the free encyclopedia

Contents

[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.

[edit] Explicit formula

I have noticed that the index j in the sum of the explicit formula starts at 0 in all textbooks I have had a look on this topic. I understand that it does not matter, as the jn part will make the whole thing zero anyway when j=0. Was just wondering if there is standard notation, since wikipedia is the first place where I have seen it starting at 1. —Preceding unsigned comment added by 130.95.29.113 (talk • contribs) 08:54, 25 May 2007 (UTC)

Its starts at j=0 to cover the case when n=0, because then we get 00 = 1. --Ray andrew 21:48, 26 September 2007 (UTC)

[edit] n < k ?

I think the article could use a mention of whether or not n < k is allowed in

\left\{\begin{matrix} n \\ k \end{matrix}\right\}

Btyner (talk) 01:02, 21 January 2008 (UTC)