Num. of ways of stacking shelves using generating functions

Question

We have $n$ books that need to be put on $k$ shelves so that each shelf contains at least $w$ books.

Now, I know how to do it using stars and bars, but how to do it using exponential generating functions?

Answer 1

There are $n!$ ways to arrange $n$ books on a shelf, so the EGF of the number arrangements of a single shelf containing $w$ or more books is $$w! \frac{1}{w!} z^w + (w+1)! \frac{1}{(w+1)!} x^ {w+1} + (w+2)! \frac{1}{(w+2)!} x^ {w+2} + \dots = \frac{z^w}{1-z}$$

The bookcase is simply a sequence of $k$ shelves, so the EGF for the number of ways books can be arranged on the bookcase is $$\left( \frac{z^w}{1-z} \right)^k = z^{wk} (1-z)^{-k} = z^{wk} \sum_{j=0}^{\infty} \binom{k+j-1}{j} z^j$$

Extract the coefficient of $\frac{1}{n!} z^n$ and you're done: $$n! \binom{k+n-wk-1}{n-wk}$$ for $n \ge wk$.