Create the generating function for this distribution problem.

Question

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?

Answer 1

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.

Answer 2

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.