4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ $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. $\endgroup$ – Fimpellizieri May 28 '18 at 20:08
  • $\begingroup$ Did a quick computation and confirmed that the order-matters count is $8577828731901$. $\endgroup$ – Brian Tung May 28 '18 at 20:34
2
$\begingroup$

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.

$\endgroup$

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.