1
$\begingroup$

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}$?

$\endgroup$
  • $\begingroup$ 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}}$ $\endgroup$ – Thomas Andrews Apr 4 at 20:37
  • $\begingroup$ Ok, but I still don't see any smart way to find it $\endgroup$ – VirtualUser Apr 4 at 20:38
  • 1
    $\begingroup$ @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. $\endgroup$ – kccu Apr 4 at 20:39
  • $\begingroup$ 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. $\endgroup$ – JMoravitz Apr 4 at 21:05
2
$\begingroup$

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}$$

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

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.