Results 1 to 3 of 3

Thread: 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 $\displaystyle B_n$ is the number of partitions of a set having $\displaystyle n$ elements. The sequence begins $\displaystyle 1,1,2,5,15,52...$.

    Show that the exponential generating function of the Bell numbers is

    $\displaystyle 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 $\displaystyle 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 $\displaystyle \sum_{n=0}^{\infty}{\tfrac{a_n(k)}{n!}\cdot x^n}=(e^x -1)^{k}$

    Proof

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

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

    Now: $\displaystyle
    \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)}}}}
    $ and each term is the number of ordered permutations in which you can have $\displaystyle a_1$ elements in box number 1, ... -permutations with repetition -

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


    Next note that $\displaystyle
    \left\{ {\begin{array}{*{20}c}
    n \\
    k \\
    \end{array}} \right\} = {\textstyle{1 \over {k!}}} \cdot a_n \left( k \right)
    $ -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: $\displaystyle
    \sum\limits_{n = 0}^\infty {\left\{ {\begin{array}{*{20}c}
    n \\
    k \\
    \end{array}} \right\} \cdot {\textstyle{{x^n } \over {n!}}}} = {\textstyle{{\left( {e^x - 1} \right)^k } \over {k!}}}
    $ and summing over k : $\displaystyle
    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}
    n \\
    k \\
    \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}
    n \\
    k \\
    \end{array}} \right\}} } \right) \cdot {\textstyle{{x^n } \over {n!}}}}
    \$

    Since: $\displaystyle
    B_n = \sum\limits_{k \ge 0} {\left\{ {\begin{array}{*{20}c}
    n \\
    k \\
    \end{array}} \right\}}
    $ we are done $\displaystyle \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 $\displaystyle B_{n+1}=\sum_{j=0}^n{n \choose j}B_j$. You can see that by induction, considering where to put the $\displaystyle (n+1)^{\mbox{st}}$ object; it can belong to a part by itself (in $\displaystyle B_n$ different ways), or it can belong to a two-object part with $\displaystyle {n \choose 1}$ choices for the other object and $\displaystyle B_{n-1}$ ways to partition the remaining objects, etc.

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

    So we know that the generating function satisfies the differential equation $\displaystyle G'(z)=e^zG(z)$. So $\displaystyle G(z)=e^{e^z+C}$. Since we have $\displaystyle G(0)=1$, we must have $\displaystyle 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: Jan 26th 2010, 05:23 AM
  2. Bell Curves
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: Jan 9th 2010, 11:05 PM
  3. bell numbers
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Sep 28th 2009, 09:50 AM
  4. Computing Bell Number for set of n elements.
    Posted in the Advanced Statistics Forum
    Replies: 7
    Last Post: Mar 14th 2009, 10:16 AM
  5. bell curve
    Posted in the Statistics Forum
    Replies: 4
    Last Post: Jul 25th 2007, 08:15 AM

Search Tags


/mathhelpforum @mathhelpforum