How can we find the number of ways to get sum $11$ using numbers $\{1,3,5\}$? Repetition of numbers is allowed. For example, one way is to take number $1$ and sum it $11$ times. Another is $5+5+1$. Ordering of numbers does not matter.
Asked
Active
Viewed 1,096 times
1
-
Does order matter, or is $1+3+5$ the same as $5+3+1$? – Misha Lavrov Mar 24 '17 at 01:33
-
Order does not matter. 1 + 3 +5 and 5 +3 +1 are treated as same. Will update my question – bornfree Mar 24 '17 at 01:34
-
Why the downvote ? – bornfree Mar 24 '17 at 01:35
-
2The answer is given by $\left[z^{11}\right]\left({1 \over 1 - z},{1 \over 1 - z^{3}},{1 \over 1 - z^{5}}\right)$ but the final evaluation is a cumbersome one. – Felix Marin Mar 24 '17 at 02:35
1 Answers
1
One method is to use generating functions:
\begin{align} & (1+x+x^2+x^3+\cdots)(1+x^3+x^6+x^9+\cdots)(1+x^5+x^{10}+x^{15}+\cdots) \\ & = \frac{1}{1-x} \cdot \frac{1}{1-x^3} \cdot \frac{1}{1-x^5} \\ & = 1 + x + x^2 + 2x^3 + 2x^4 + 3x^5 + 4x^6 + 4x^7 + 5x^8 + 6x^9 + 7x^{10} \\ & \quad + 8x^{11} + 9x^{12} + 10x^{13} + 11x^{14} + 13x^{15} + 14x^{16} + \cdots \end{align}
We want the coefficient of the $x^{11}$ term, which is $\fbox{8}$. Moreover, since the denominator of the generating function is $(1-x)(1-x^3)(1-x^5) = 1-x-x^3+x^4-x^5+x^6+x^8-x^9$, a recursive formula for the coefficients is $a_n = a_{n-1} + a_{n-3} - a_{n-4} + a_{n-5} - a_{n-6} - a_{n-8} + a_{n-9}$.
Alex B.
- 545
-
Thanks for the answer. I have a question. What are generating functions and how are they calculating the answer to my question( it appears like magic to me- coefficient of x^11 is the answer). Can you provide any good resource to learn about the same ? – bornfree Mar 30 '17 at 14:40
-
@bornfree Searching MathSE I found this answer to a similar question about dice -- I think it does a great job (by using color) of illustrating what the purpose of introducing polynomials is good for. Here is a site that is more directly related to your question. For a slightly more rigorous treatment with many good examples, see this document. – Alex B. Mar 30 '17 at 20:55
-