In my Discrete Math textbook there's the following problem: "How many possibilities there exist to distribute 25 objects of the same kind into 7 different bins, if in the first bin there can be no more than 10 objects?"
A solution using generating functions must be found. The solution uses the following generating function:
$$(1+x+x^2+x^3+x^4+...+x^{10})(1+x+x^2+x^3+...)^6$$
The textbook then goes on suggest this formal power series in order to find the coefficient of $x^{25}$: $$f(x)=\frac{1-x^{11}}{1-x}*\frac{1}{1-x^6}$$
I understand completely the first part:
$$\frac{1-x^{11}}{1-x}$$
I don't understand why this series
$$\frac{1}{1-x^6}$$ was chosen for the other 6 bins. The amount of objects can't be over 25 so we need to choose a power series which works for finite number of objects (the solution needs to be a natural number (including $0$)) which is again this:
$$\sum_{i=0}^n x^i = \frac{1-x^{n+1}}{1-x}$$
Can you please explain why?
The second factor should be $\left(\frac1{1-x}\right)^6=\frac1{(1-x)^6}$; the exponent is in the wrong place.
We want a generating function such that the coefficient of $x^n$ is the number of possibilities for distributing $n$ objects of the same kind into $7$ bins, with a limit of $10$ in the first bin. Thus, we need to allow for any number of objects, not just $25$. Each of the six bins whose contents are not limited can therefore contain any non-negative number of objects up to $n$ for any given $n$, and we have to allow for all of these possibilities. Of course when we compute the coefficient of $x^{25}$ in order to answer the specific question for $25$ objects, the terms in $x^k$ with $k>25$ won’t contribute anything.