# Find number of ways to split $1$ dollar into $5$, $10$, $20$, $50$ cents

Find number of ways to split $$1$$ dollar into $$5$$, $$10$$, $$20$$, $$50$$ cents

I am going to use generating functions: $$n = [x^{100}] (1+x^5+x^{10}+\cdots)(1+x^{10}+x^{20}+\cdots)(1+x^{20}+x^{40}+\cdots)(1+x^{50}+x^{100}+\cdots) = \\ [x^{100}]\frac{1}{1-x^5}\frac{1}{1-x^{10}}\frac{1}{1-x^{20}}\frac{1}{1-x^{50}}$$ Ok, I know that computers are able to solve that but how can I easily get coefficient at $$x^{100}$$?

• Slightly simplify it as $[y^{20}]\frac{1}{1-y}\frac{1}{1-y^2}\frac{1}{1-y^4}\frac{1}{1-y^{10}}$ – Thomas Andrews Apr 4 at 20:37
• Ok, but I still don't see any smart way to find it – VirtualUser Apr 4 at 20:38
• @VirtualUser It's not easy to find. Best way is to let a computer do it. Finding the coefficient by hand is equivalent to finding all the ways to write $100$ as sums of $5, 10,20,50$ by hand. – kccu Apr 4 at 20:39
• If your question is how to implement it in such a way with code so that you can arrive at an answer (since infinite sums are messy) you can truncate each sum to have a finite number of terms and look at $[x^{100}](1+x^5+x^{10}+\dots+x^{95}+x^{100})(1+x^{10}+\dots+x^{100})\dots(1+x^{50}+x^{100})$ and when calculating the product you can further throw away any terms with exponent greater than $100$. This can be accomplished using a $21$ entry array of integers for example. – JMoravitz Apr 4 at 21:05

## 1 Answer

Let \begin{align}f(y)&=\frac{1}{1-y}\frac{1}{1-y^2}\frac{1}{1-y^4}\\&=\frac{(1+y+y^2+y^3)(1+y^2)}{(1-y^4)^3}\\&=\frac{1+y+2y^2+2y^3+y^4+y^5}{(1-y^4)^3}\end{align}

Letting $$p(y)=1+y+2y^2+2y^3+y^4+y^5$$, then $$[y^{20}]f(y)\frac{1}{1-y^{10}} = [y^0]f(y)+[y^{10}]f(y)+[y^{20}]f(y)$$

Now use that $$\frac{1}{(1-y^4)^3}=\sum_{j=0}^{\infty} \binom{j+2}{2}y^{4j}$$

So \begin{align}[y^0]f(y)&=1\\ [y^{10}]f(y)&=\binom{0+2}{2}[y^{10}]p(y) + \binom{1+2}{2}[y^{6}]p(y)+\binom{2+2}{2}[y^2]p(y)\\&=0+0+6\cdot2\\&=12\\ [y^{20}]f(y)&=\binom{4+2}{2}[y^4]p(y)+\binom{5+2}{2}[y^0]p(y)\\ &=15\cdot 1 + 21\cdot 1\\ &=36\end{align}

So your result is $$1+12+36=49.$$

You have in general that \begin{align}[y^{4j}]f(y)&=\binom{j+1}{2}+\binom{j+2}{2}=(j+1)^2\\ [y^{4j+1}]f(y)&=\binom{j+1}{2}+\binom{j+2}{2}=(j+1)^2\\ [y^{4j+2}]f(y)&=2\binom{j+2}{2}=(j+2)(j+1)\\ [y^{4j+3}]f(y)&=2\binom{j+2}{2}=(j+2)(j+1) \end{align}

• So the general rule is to transform it to $\frac{f(y)}{(1-\lambda y)^{\alpha}}$ and use coefficient – VirtualUser Apr 5 at 17:52