1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.