Create the generating function for this distribution problem. In how many ways can we distribute 22 identical objects to 9 distinct recipients, if 3 of the recipients can receive at most 3 objects. 
How to create the generating function for this problem and find the coefficient of X^22?
 A: You want the coefficient of $x^{22}$in $(1+x+x^2+\dots)^6(1+x+x^2+x^3)^3$.
Of course this is the same as the coefficient of $x^{22}$ in $(1+x+\dots+x^{22})^6(1+x+x^2+x^3)^3$.
You can calculate this in time $8\times 22\log(22)$ if you truncate the polynomials after each step and use fft.
A: It is convenient to use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ in a series.

We obtain
  \begin{align*}
\color{blue}{[x^{22}]}&\color{blue}{(1+x+x^2+x^3)^3(1+x+x^2+\cdots)^6}\\
&=[x^{22}]\left(\frac{1-x^4}{1-x}\right)^3\left(\frac{1}{1-x}\right)^6\tag{1}\\
&=[x^{22}]\frac{(1-x^4)^3}{(1-x)^9}\\
&=[x^{22}](1-x^4)^3\sum_{j=0}^\infty \binom{-9}{j}(-x)^j\tag{2}\\
&=\left([x^{22}]-3[x^{18}]+3[x^{14}]-[x^{10}]\right)\sum_{j=0}^\infty \binom{j+8}{8}x^j\tag{3}\\
&=\binom{30}{8}-3\binom{26}{8}+3\binom{22}{8}-\binom{18}{8}\tag{4}\\
&\,\,\color{blue}{=2\,081\,652}
\end{align*}

Comment:


*

*In (1) we use the geometric series expansion.

*In (2) we use the binomial series expansion.

*In (3) we use the linearity of the coefficient of operator, apply the formula $[x^{p-q}]A(x)=[x^p]x^qA(x)$ and the binomial identity $\binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q$.

*In (4) we select the coefficients accordingly.
