Combinatorics question - generating functions

Quote:

Originally Posted by htata123

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
$\displaystyle f(x) = 1 \cdot x + 2! \cdot x^2/2! + 3! \cdot x^3/3! + \dots$
$\displaystyle = x + x^2 + x^3 + \dots = x \; (1 + x + x^2 + \dots)$
$\displaystyle = x \; (1-x)^{-1}$

For books on two shelves with at least one book on each shelf, the EGF is then
$\displaystyle 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 $\displaystyle x^n / n!$ in the above series is
$\displaystyle t(n) = n! \binom{n-1}{n-2} = \frac{n (n-1) (n-1)! }{2}$.