how many combination of coins add up to \$20? we have five coins:


*

*Coin 1: \$1.

*Coin 2: \$2.

*Coin 3: \$5.

*Coin 4: \$10.

*Coin 5: \$20.
In how many way can we get \$20 using those coins and combinations of them?
The only way I could do that was by counting all possibilities and it took forever.I started counting with this in mind : "in how many ways can only one of coins add up to \$20" . then went for combination of 2 coins ,after that of 3 coins . I got total of 40 combinations but it was very time consuming and illogical because if you have like \$50 to add up to you will never count that by hand .
Is there any other easier way maybe ,formula ?
 A: There are $41$ combinations in all.  The following solution is essentially a twist on the usual approach using generating functions.  
Start by noticing that if we want to make a total of 20 dollars, we can use any combination of the 2, 5, 10, and 20 dollar coins and make up the rest with 1 dollar coins.  So we can solve the problem without 1 dollar coins for $r$ dollars for $0 \le r \le 20$ and add up the 21 solutions to get the total number of combinations.  Let's say $a_r$ is the number of solutions (not using 1 dollar coins) for $r$ dollars.  If you think about it a bit, I think you can see that $a_r$ is the coefficient of $x^r$ in a polynomial which we will denote by $f(x)$, defined by
$$f(x) = P_2(x) P_5(x) P_{10}(x) P_{20}(x)$$
where
$$\begin{align}
P_2(x) &= 1 + x^2 + x^4 + x^6 + \dots + x^{20} \\
P_5(x) &= 1 + x^5 + x^{10} + x^{15} + x^{20} \\
P_{10}(x) &= 1 + x^{10} + x^{20} \\
P_{20}(x) &= 1 + x^{20} \\
\end{align}$$
To see this, think about the way multiplication of polynomials works.  It may help to start by computing a smaller example, say $P_{10}(x) P_{20}(x)$, and see how the result relates to the problem of making change with only 10 and 20 dollar coins.
Expanding $f(x)$ is a straightforward computation.  We start by computing $P_{20}(x)P_{10}(x)$, then compute $P_{20}(x)P_{10}(x)P_5(x)$, and then finish with $P_{20}(x)P_{10}(x)P_5(x)P_2(x)$. And since we are only interested in $a_r$ for $r \le 20$, we can discard any powers of $x$ higher than $x^{20}$. So here goes:
$$P_{20}(x) P_{10}(x) = 1+x^{10}+2 x^{20}+ O(x^{30})$$
$$P_{20}(x) P_{10}(x) P_5(x) = 1+x^5+2 x^{10}+2 x^{15}+4 x^{20} + O(x^{25})$$
$$P_{20}(x) P_{10}(x) P_5(x) P_2(x) = 1+x^2+x^4+x^5 + \\ x^6+x^7+x^8+x^9+3 x^{10}  + \\ x^{11}+3 x^{12}+x^{13}+3 x^{14}+3 x^{15}  + \\3
   x^{16}+3 x^{17}+3 x^{18}+3 x^{19}+7 x^{20}+O(x^{21})$$
This last polynomial is $f(x)$, and if we sum its coefficients up to the coefficient of $x^{20}$ we find the answer to the problem is $41$.
