1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Combinatorics: Generating functions

  1. Nov 28, 2012 #1
    I have that [itex]B(x)=e^{e^{x}-1}[/itex] 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

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

    Use this result to show that

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


    I've tried doing this but I cannot seem to get very far. Could someone show me how to prove this? Thanks.
  2. jcsd
  3. Nov 28, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    If you write that out using the definition of B(x), collecting up the coefficients of xn will, with luck, produce:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook