Combinatorics - Generating function problem So we have this problem . We want to distribute 20 identical marbles to 3 distinct children so that:


*

*The first child takes at least 4 marbles.

*Every child gets at least 3 marbles.
The given answers where :


*

*$(x^4 + ... + x^{20})(1 + x + ... + x^{20})(1 + x + ... + x^{20})$

*$((1+x+...+x^{20})^{3})$
And in both case the answer is given by the coefficient of $x^{20}$
My question is this:

If the first child takes at least 4 , then the second and the third could never have more 16 so should we change the generating function to:  $(x^4 + ... + x^{20})(1 + x + ... + x^{16})(1 + x + ... + x^{16})$ ?
Accordingly, if every child gets at least 3, then it should not have more than 14 because we always need 3+ 3 = 6 for the other two . So i would write $((1+x+...+x^{14})^{3})$ and the correct answer will be given by the coefficient of 20.
Because we care about the coefficient of 20 , we need to make  sure that there are no extra things in our function in order for our solution to be correct , if for example we wanted to disturb 10 marbles then because we only need to identify the coefficient of $x^{10}$ then it makes no difference if expand these polynomials. Am I right? Am I missing something?

For the first problem, the simplest answer is that both generating functions are correct for the desired coefficient. i.e.,
\begin{align*}
&[x^{20}] (x^4+\dotsb+x^{20})(1+\dotsb+x^{20})(1+\dotsb+x^{20})\\
&= [x^{20}] (x^4+\dotsb+x^{20})(1+\dotsb+x^{16})(1+\dotsb+x^{16})
\end{align*}
where $[x^n]$ denotes the coefficient extraction operator.
The reason for this is, for instance, the coefficient of $x^{17}$ is never used from the second product term due to the contribution of terms with power at least $4$ from the first. The difference between our generating functions is that certain cases, such as cases in which the first person selects $4$ marbles and the second selects $17$ are encoded in the first generating function but not in the second. Encoded or not, $20$ marbles cannot be reached from $21$ through selection of marbles in the third term, so $[x^{20}]$ does not count such cases.
In terms of the problem at hand, we note that we can encode more states that won't ultimately affect the extracted coefficient. For much the same reasoning as higher order coefficients like $[x^{17}]$ not being considered when extracting, we could equally well conclude
\begin{align*}[x^{20}] &(x^4+\dotsb+x^{20})(1+\dotsb+x^{16})(1+\dotsb+x^{16})\\
&= [x^{20}] (x^4+\dotsb+x^{a})(1+\dotsb+x^{b})(1+\dotsb+x^{c})
\end{align*}
for $a\geq 20$, $b\geq 16$, and $c\geq 16$.
In fact this holds formally if $a=b=c=\infty$:
\begin{align*}
&[x^{20}] (x^4+\dotsb+x^{20})(1+\dotsb+x^{16})(1+\dotsb+x^{16})\\
&= [x^{20}] (x^4+x^5+\dotsb)(1+x+\dotsb)(1+x+\dotsb)
\end{align*}
This is useful for when we want to actually do the coefficient extraction,
\begin{align*}
&(x^4+x^5+\dotsb)(1+x+\dotsb)(1+x+\dotsb)\\
&= x^4(1+x+\dotsb)^3
= \frac{x^4}{(1-x)^3}
\end{align*}
is more manageable than
\begin{align*}&(x^4+\dotsb+x^{20})(1+\dotsb+x^{16})(1+\dotsb+x^{16})\\
&= x^4(1+\dotsb+x^{16})^3
= \frac{x^4(1-x^{17})^3}{(1-x)^3}.
\end{align*}
On to the actual computation, given that $\frac{1}{(1-x)^n} = \sum_{k=0}^\infty \binom{n+k-1}{n-1} x^k$,
\begin{align*}
[x^{20}] \frac{x^4}{(1-x)^3}
&= [x^{20}] \sum_{k=0}^\infty \binom{k+2}{2} x^{k+4}\\
&= [x^{20}] \sum_{k=4}^\infty \binom{k-2}{2} x^{k}
= \binom{18}{2}.
\end{align*}
For the second problem, I believe they meant $(x^3+\dotsb+x^{20})^3$ as $(1+x+\dotsb+x^{20})^3$ encodes $1\cdot 1\cdot x^{20}$ which is not one of the valid cases.
At least $3$ marbles were taken by each, so you can just look at $(x^3+\dotsb+x^{14})^3$. Another way is to first reserve $3$ marbles per person, and then selecting up to $20-9=11$ marbles for each, which corresponds to the generating function $(x^3)^3(1+\dotsb+x^{11})^3$ (which you'll note is algebraically equivalent). All these generating functions have the same $x^{20}$ coefficient:
\begin{align*}
&\;[x^{20}] (x^3+\dotsb+x^{20})^3\\
= &\;[x^{20}] (x^3+x^4+\dotsb+x^{14})^3\\
= &\;[x^{20}] (x^3+x^4+\dotsb)^3
= [x^{20}] \frac{x^9}{(1-x)^3}\\
= &\;[x^{20}] \sum_{k=0}^\infty \binom{k+2}{2} x^{k+9}
= [x^{20}] \sum_{k=9}^\infty \binom{k-7}{2} x^{k}\\
= &\binom{13}{2}.
\end{align*}
