# Combinatorics: Generating functions

1. Nov 28, 2012

### BrownianMan

I have that $B(x)=e^{e^{x}-1}$ is the generating function for the number of set partitions. Also the Stirling numbers of the second kind are de fined by S(0,0)=1, S(n,0)=S(0,n)=0 for n=>1 and S(n,k)=S(n-1, k-1) + kS(n-1, k). Show that

$$e^{u(e^{x}-1)}=1+\sum_{n\geq 1}\sum_{k=1}^{n}S(n,k)u^{k}\frac{x^{n}}{n!}$$

Use this result to show that

$$S(n,k)=\frac{1}{k!}\sum_{r=0}^{k}(-1)^{k-r}\left \binom{k}{r}r^{n}$$

----------------------------------------------

I've tried doing this but I cannot seem to get very far. Could someone show me how to prove this? Thanks.

2. Nov 28, 2012

### haruspex

So
$$e^{u(e^{x}-1)}=B(x)^u$$
If you write that out using the definition of B(x), collecting up the coefficients of xn will, with luck, produce:
$$\frac{1}{n!}\sum_{k=1}^{n}S(n,k)u^{k}$$

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook