3
$\begingroup$

I did (parcially) the following exercise:

There are $10$ identical gift boxes. Each one must be colored with a unique color and there are the colors red, blue, green and yellow. It's possible to color a maximum of $2$ boxes with red, and a maximum of $3$ colors with blue. Write the ordinary generating function associated with the problem and find the number of ways to color 10 boxes.

I've managed to find the generating function:

$$(1+x+x^2)(1+x+x^2+x^3)(1+x+x^2+\dots)^2=\left[ \frac{1-x^3}{1-x}\right]\left[ \frac{1-x^4}{1-x}\right]\left[ \frac{1}{1-x}\right]^2\\ \frac{(1-x^3)(1-x^4)}{(1-x)^4}$$

But for calculating the number of colored boxes, I'd have:

$$\frac{(1-x^3)(1-x^4)}{(1-x)^4}=[1-x^3][1-x^4] \left[ \frac{1}{(1-x)} \right]^4$$

The expansion of $\left[\frac{1}{(1-x)}\right]^4$ is:

$$\left[\frac{1}{(1-x)}\right]^4=\sum_{j=0}^\infty {4+j-1 \choose j} y^k$$

But this doesn't seem too revealing. I don't know how to proceeed the counting in this exercise.

$\endgroup$
1
  • $\begingroup$ Your expansion is correct. Now you only need to expand $(1-x^3)(1-x^4)$ and then plug the relevant value of $j$ is the sum to find the coefficient of $x^{10}$. $\endgroup$
    – Galc127
    Feb 16 '15 at 10:50
4
$\begingroup$

Already you have notice that$$(1+x+x^2)(1+x+x^2+x^3)(1+x+x^2+\dots)^2=\left[ \frac{1-x^3}{1-x}\right]\left[ \frac{1-x^4}{1-x}\right]\left[ \frac{1}{1-x}\right]^2.$$ Also $$(1+x+x^2+\dots)^2=(1+2x+3x^2+\cdots+kx^{k-1}+\cdots)$$ $$(1+x+x^2)(1+x+x^2+x^3)=(1+2x+3x^2+3x^3+2x^4+x^5)$$ Therefore coefficient of $x^{10}$ in the product $$(1+2x+3x^2+3x^3+2x^4+x^5)(1+2x+3x^2+\cdots+kx^{k-1}+\cdots)$$ is $$11+(2\times10)+(3\times9)+(3\times8)+(2\times7)+6=102.$$

$\endgroup$
2
$\begingroup$

You're almost there. Expand $(1-x^3)(1-x^4)$ as $1-x^3-x^4+x^7$; when you take the $x^{10}$ coefficient of the product of this with $1/(1-x)^4$, you'll get the four terms with $j=10,10-3,10-4,10-7$ (with appropriate signs): $$ \binom{13}{10}-\binom{10}{7}-\binom{9}{6}+\binom{6}{3} = 102.$$

$\endgroup$
1
$\begingroup$

This is mechanized in Maple:

coeftayl(((-x^3+1)/(1-x)*((-x^4+1)/(1-x)))/(1-x)^2, x = 0, 10);

$$ 102. $$ See coeftayl for info.

$\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.