Results 1 to 3 of 3

Math Help - Bell numbers

  1. #1
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1

    Bell numbers

    The nth Bell number B_n is the number of partitions of a set having n elements. The sequence begins 1,1,2,5,15,52....

    Show that the exponential generating function of the Bell numbers is

    G(z)=\sum_{n=0}^\infty B_n\frac{z^n}{n!} = e^{e^z-1}
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Lemma: Let a_n(k) be the number of ordered partitions of a set of n elements in k sets. - or the number of ways in which you can distribute n balls into k boxes -
    Then \sum_{n=0}^{\infty}{\tfrac{a_n(k)}{n!}\cdot x^n}=(e^x -1)^{k}

    Proof

    Let's compute the coefficient of x^n of the RHS.

    Since e^x  - 1 = x + {\textstyle{{x^2 } \over {2!}}} + ... it follows that our coefficient is: <br />
\sum\limits_{a_1  + ... + a_k  = n} {{\textstyle{1 \over {\left( {a_1 !} \right) \cdot ... \cdot \left( {a_k !} \right)}}}} <br />

    Now: <br />
\sum\limits_{a_1  + ... + a_k  = n} {{\textstyle{{n!} \over {\left( {a_1 !} \right) \cdot ... \cdot \left( {a_k !} \right)}}}}  = \sum\limits_{a_1  + ... + a_k  = n} {{\textstyle{{\left( {a_1  + ... + a_k } \right)!} \over {\left( {a_1 !} \right) \cdot ... \cdot \left( {a_k !} \right)}}}} <br />
and each term is the number of ordered permutations in which you can have a_1 elements in box number 1, ... -permutations with repetition -

    So the coefficient is actually {\textstyle{{a_n \left( k \right)} \over {n!}}} \square


    Next note that <br />
\left\{ {\begin{array}{*{20}c}<br />
   n  \\<br />
   k  \\<br />
\end{array}} \right\} = {\textstyle{1 \over {k!}}} \cdot a_n \left( k \right)<br />
-the LHS is the stirling number of the second kind, or, the number of partitions of a set of n elements into k sets (here we do not care about the order) -

    Hence: <br />
\sum\limits_{n = 0}^\infty  {\left\{ {\begin{array}{*{20}c}<br />
   n  \\<br />
   k  \\<br />
\end{array}} \right\} \cdot {\textstyle{{x^n } \over {n!}}}}  = {\textstyle{{\left( {e^x  - 1} \right)^k } \over {k!}}}<br />
and summing over k : <br />
e^{e^x  - 1}  = \sum\limits_{k \ge 0} {{\textstyle{{\left( {e^x  - 1} \right)^k } \over {k!}}}}  = \sum\limits_{k \ge 0} {\sum\limits_{n \ge 0} {\left\{ {\begin{array}{*{20}c}<br />
   n  \\<br />
   k  \\<br />
\end{array}} \right\} \cdot {\textstyle{{x^n } \over {n!}}}} }  = \sum\limits_{n \ge 0} {\left( {\sum\limits_{k \ge 0} {\left\{ {\begin{array}{*{20}c}<br />
   n  \\<br />
   k  \\<br />
\end{array}} \right\}} } \right) \cdot {\textstyle{{x^n } \over {n!}}}} <br />
\

    Since: <br />
B_n  = \sum\limits_{k \ge 0} {\left\{ {\begin{array}{*{20}c}<br />
   n  \\<br />
   k  \\<br />
\end{array}} \right\}}  <br />
we are done \square
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Very nice!
    Here is my proof.

    First notice that the Bell numbers are of "binomial type"; i.e. they satisfy the recurrence B_{n+1}=\sum_{j=0}^n{n \choose j}B_j. You can see that by induction, considering where to put the (n+1)^{\mbox{st}} object; it can belong to a part by itself (in B_n different ways), or it can belong to a two-object part with {n \choose 1} choices for the other object and B_{n-1} ways to partition the remaining objects, etc.

    Now let G(z) be the generating function. Differentiating is equivalent to shifting the sequence one place to the left. Moreover, multiplying by e^z is equivalent to taking the binomial convolution : if f(z)=\sum_{j=0}^\infty a_j\frac{z^j}{j!} then the coefficient of \frac{z^n}{n!} in e^zf(z) is \sum_{j=0}^n{n \choose j}a_j.

    So we know that the generating function satisfies the differential equation G'(z)=e^zG(z). So G(z)=e^{e^z+C}. Since we have G(0)=1, we must have C=-1, \: \: G(z)=e^{e^z-1}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. software for bell curve graphs
    Posted in the Math Software Forum
    Replies: 1
    Last Post: January 26th 2010, 05:23 AM
  2. Bell Curves
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: January 9th 2010, 11:05 PM
  3. bell numbers
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 28th 2009, 09:50 AM
  4. Computing Bell Number for set of n elements.
    Posted in the Advanced Statistics Forum
    Replies: 7
    Last Post: March 14th 2009, 10:16 AM
  5. bell curve
    Posted in the Statistics Forum
    Replies: 4
    Last Post: July 25th 2007, 08:15 AM

Search Tags


/mathhelpforum @mathhelpforum