Number of ways to express sum.

Question

Consider three sets of cards colored Blue, Red and Yellow. Each set has cards numbered $1-10$. The $4$ remaining cards are all indistinguishable cards numbered $0$.

Card numbered $i$ has the value of $2^i$. How many ways are there to choose a group of cards that sums up to $2016$.

I'm having a problem with creating a generating function for this problem, any help would be appreciated.

So far I have $f(x) = (x^1 + x^2 + x^3 + x^4)\cdot(1 + x^{2^{1}} + x^{2^{2}} + x^{2^{3}} ... + x^{2^{10}})^3$ but I'm not really sure that's even correct.

Answer 1

We can represent the number of selecting zero up to four indistinguishible cards which have value $2^0=1$ as \begin{align*} 1+x+x^2+x^3+x^4=\frac{1-x^5}{1-x} \end{align*}

We can represent the number of selecting zero up to three distinguishible cards numbered with value $2^i$ as \begin{align*} \left(1+x^{2^i}\right)^3\qquad 1\leq i\leq 10 \end{align*}

The corresponding generating function is \begin{align*} &\frac{1-x^5}{1-x}\left(1+x^{2^{1}}\right)^3\left(1+x^{2^{2}}\right)^3\left(1+x^{2^{3}}\right)^3\cdots\left(1+x^{2^{10}}\right)^3\\ &\qquad=\frac{1-x^5}{1-x}\left(\sum_{j=0}^{2^{10}-1}x^{2j}\right)^3\\ &\qquad=\frac{1-x^5}{1-x}\left(\frac{1-x^{2^{11}}}{1-x^2}\right)^3\tag{1} \end{align*} in accordance with the generating function given by the answer from @RossMillikan.

Next we have to extract the coefficient of $x^{2016}$ from (1). It is convenient to use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ of a series.

We obtain from (1) \begin{align*} \color{blue}{[x^{2016}]}&\color{blue}{\frac{1-x^5}{1-x}\left(\frac{1-x^{2^{11}}}{1-x^2}\right)^3}\\ &=[x^{2016}]\frac{1-x^5}{1-x}\left(\frac{1}{1-x^2}\right)^3\tag{2}\\ &=\left([x^{2016}]-[x^{2011}]\right)\sum_{j=0}^\infty x^k\sum_{j=0}^\infty\binom{-3}{j}(-x^2)^j\tag{3}\\ &=\left(\sum_{k=0}^{2016}[x^k]-\sum_{k=0}^{2011}[x^k]\right)\sum_{j=0}^\infty\binom{j+2}{2}x^{2j}\tag{4}\\ &=\left(\sum_{k=0}^{1008}[x^{2k}]-\sum_{k=0}^{1005}[x^{2k}]\right)\sum_{j=0}^\infty\binom{j+2}{2}x^{2j}\tag{5}\\ &=\binom{1008}{2}+\binom{1009}{2}+\binom{1010}{2}\tag{6}\\ &\,\,\color{blue}{=1\,525\,609} \end{align*}

Comment:

• In (2) we omit terms in the numerator with powers of $x^{2^{11}}$ since they do not contribute to the coefficient of $x^{2016}$.

• In (3) we apply $[x^{p-q}]A(x)=[x^p]x^qA(x)$ and do a geometric and binomial series expansion.

• In (4) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q$.

• In (5) we skip coefficients of odd powers since they do not contribute.

• In (6) we select the coefficients accordingly.

Answer 2

Here are a couple of hints:

With the blue cards, you can make any even number from $0$ to $2^{11}-2$, and you can make it it exactly one way. (Think binary numbers.)

With the the zero cards, you can make $0$ in $1$ way, $1$ in $4$ ways, $2$ in $6$ ways, etc. if we take account of which zero card we use. From the statement that the zero cards are indistinguishable, however, I suppose we can make $0,1,2,3,$ or $4$ in one way.

Can you finish it from here?

Answer 3

The blue cards can give you any even value from $0$ through $2046$ in exactly one way, so their generating function is $1+x^2+x^4+\ldots+x^{2046}=\frac {1-x^{2048}}{1-x^2}$. You could also get here by saying the $1$ card has value $2$ so generating function $1+x^2$, the $2$ card has function $1+x^4$ and so on. Multiply all those together for a given color and you get the above. Each color can give you the same, so you cube it. The blanks can give you any value from $0$ to $4$, so their generating function is $1+x+x^2+x^3+x^4=\frac {1-x^5}{1-x}$ and the overall generating function is $$\left(\frac {1-x^5}{1-x}\right)\left(\frac {1-x^{2048}}{1-x^2}\right)^3$$