Combinatorics question - generating functions

**htata123** · November 4th 2009, 11:26 AM

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** · November 4th 2009, 04:22 PM

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

Thread: Combinatorics question - generating functions

LinkBack

Thread Tools

Display

Combinatorics question - generating functions

Similar Math Help Forum Discussions

Question about generating functions

Probability question involving generating functions and expectation

combinatorics - generating functions 2

Generating Functions question

Probability Generating Functions Question

Search Tags