# Number of ways to represent $100$ as a sum of $1, 5, 10, 25$

In how many ways can you represent $100$ as a sum using only these numbers: $1, 5, 10, 25$ if the order does not matter? What if the order did matter?

My solution:
Let the power of $x$ denote our current sum. We need to take any number of ones, fives, tens and twenty-fives as we need, just to get the exponent of $x$ to be $100.$ The generating function will be: $$f(x) = (x^0 + x^1 + x^2 + \dots)(x^0 + x^5 + x^{10} + \dots)(x^0+x^{10}+x^{20} +\dots)(x^0 + x^{25}+x^{50}+ \dots) = \frac{1}{(1-x)(1-x^5)(1-x^{10})(1-x^{25})}$$ We need to take the coefficient at $x^{100}$, which is $242$.
Now, if the order did matter, then we would have to consider sequences instead of multisets, and so the generating function would be $$g(x) =\sum_n(x+x^5+x^{10}+x^{25})^n$$ And now the coefficient would be $8 577 828 731 901$.

Well, there is a slight difference between these numbers and so - my question is - is my method of solving this correct? If so, I guess that this enormous numbers derives from very large factorials.

• $g$ is missing a summation indexed by $n$, I suppose? Other than that, this seems like a perfect example of the power of generating functions. – Fimpellizieri May 28 '18 at 20:08
• Did a quick computation and confirmed that the order-matters count is $8577828731901$. – Brian Tung May 28 '18 at 20:34

## 1 Answer

Your approach is a good one. Yes, the much larger number of ordered sums comes from the permutations. As a simple example, consider $100=50\cdot 1 + 10 \cdot 5$. In the first part this represents one way to make $100$. In the second, it represents ${60\choose 10}=75\ 394\ 027\ 566$ ways because you can pick any $10$ of the $60$ positions for the $5$s.