Impossible counting problem with Generating function

Question

How do I find the generating function where the coefficient $a_k$ represent the how many ways to distribute $k$ pieces of candy to n children where no children get more than m pieces? I cannot find any example of how to solve such problem. Thanks.

Answer 1

This is the number of tuples $(c_1, \dots c_n)$ of nonnegative integers such that $\sum c_i = k$ and $c_i \le m$. Each $c_i$ contributes a factor $(1 + x + \dots + x^m)$ to the generating function (do you see why?) and the final generating function is

$$\sum a_k x^k = (1 + x + \dots x^m)^n.$$

It might be good to think about the case $m = 1$ first: when each child can get either $0$ or $1$ pieces of candy, you are precisely asking about the number of subsets of the set of children (namely, the subset of children who get candy) of size $k$, so it's no surprise that you get the generating function $(1 + x)^n$ for the binomial coefficients.