Combinatorics question - generating functions

htata123 · #1 $Old$ November 4th, 2009, 01:26 PM

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

awkward · #2 $Old$ November 4th, 2009, 06:22 PM

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}$ .