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!

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

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    So
    [tex]e^{u(e^{x}-1)}=B(x)^u[/tex]
    If you write that out using the definition of B(x), collecting up the coefficients of xn will, with luck, produce:
    [tex]\frac{1}{n!}\sum_{k=1}^{n}S(n,k)u^{k}[/tex]
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Combinatorics: Generating functions
Loading...