Results 1 to 2 of 2

Math Help - Combinatorics question - generating functions

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    29

    Combinatorics question - generating functions

    Hi, I have a question that requires the use of generating functions in combinatorics;

    Let t(n) be the number of ways to arrange n books on two bookshelves so that each shelf receives at least one book. Find a closed formula for tn.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by htata123 View Post
    Hi, I have a question that requires the use of generating functions in combinatorics;

    Let t(n) be the number of ways to arrange n books on two bookshelves so that each shelf receives at least one book. Find a closed formula for tn.

    Thanks
    I'm assuming the order of the books on each shelf is important.

    If we have n books on a single shelf, there are n! ways to arrange the books. If we require n > 0, the Exponential Generating Function (EGF) of n! is
    f(x) = 1 \cdot x + 2! \cdot x^2/2! + 3! \cdot x^3/3! + \dots
     = x + x^2 + x^3 + \dots = x \; (1 + x + x^2 + \dots)
     = x \; (1-x)^{-1}

    For books on two shelves with at least one book on each shelf, the EGF is then
    f(x) \cdot f(x) = x^2 \; (1-x)^{-2} = x^2 \; \sum_{i=0}^\infty \binom{i+1}{i} x^i

    The coefficient of x^n / n! in the above series is
    t(n) = n! \binom{n-1}{n-2} = \frac{n (n-1) (n-1)! }{2}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Question about generating functions
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: June 22nd 2011, 09:26 AM
  2. Replies: 0
    Last Post: April 15th 2011, 05:43 AM
  3. combinatorics - generating functions 2
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 6th 2009, 05:06 PM
  4. Generating Functions question
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: October 13th 2009, 02:43 PM
  5. Probability Generating Functions Question
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: February 15th 2009, 07:39 PM

Search Tags


/mathhelpforum @mathhelpforum