GeneratingFunction China Challenging
2004


Problem - 4333

A deck of poker has three different colors each of which contains $10$ cards numbered from $1$ to $10$, respectively. In addition, there are two jokers both of which are numbered as $0$. A card with number $k$ is valued as $2^k$ points. How many different ways are there to draw several cards from this deck so that their total value equals $2004$?


Let $a_n$ be the number of combinations of cards such that their total value is $n$. Then we have $$\begin{align*} \sum_{k=0}^{\infty}a_kx^k =\ &\left(1+x^{2^0}\right)^2\left(1+x^{2^1}\right)^3\left(1+x^{2^2}\right)^3\cdots\left(1+x^{2^{10}}\right)^3 \\ =\ &\frac{1}{1+x}\left(\left(1+x^{2^0}\right)\left(1+x^{2^1}\right)\left(1+x^{2^2}\right)\cdots\left(1+x^{2^{10}}\right)\right)^3 \\ =\ &\frac{1}{1+x}\frac{1}{(1-x)^3}\left(1-x^{2^{11}}\right)^3 \end{align*}$$

Because $2004 < 2^{11}$, therefore $a_{2004}$ must equal the coefficient of the $x^{2004}$ in the expanded form of $$\begin{align*} &\frac{1}{(1+x)(1-x)^3}\\ =\ &\frac{1}{1-x^2}\cdot\frac{1}{(1-x)^2}\\=\ &(1+x^2+x^4+\cdots)\left(1+\binom{1+1}{1}x + \binom{1+2}{1}x^2+\binom{1+3}{1}x^3+\cdots\right) \end{align*}$$

Therefore $$\begin{align*} a_{2004} =\ &\binom{1+2004}{1} + \binom{1+2002}{1} + \cdots + \binom{1+2}{1}+\binom{1+0}{1} \\ =\ & 2005+2003+\cdots + 3+1 \\=\ & 1003^2\\=\ &\boxed{1006009} \end{align*}$$

report an error