Ways to add up 10 numbers between 1 and 12 to get 70

I know this has something to do with factorials, and combinations and permutations. I've been puzzling over this for a little while, and I can't come up with an answer. My question is, How would one figure out how many ways there are to use exactly 10 numbers from 1 to 12 to sum 70. Order is important. Therefore permutations not combinations. Thank You in advance! :D

Edit: They are not necessarilly distinct numbers as in 12,12,12,12,12,2,2,2,2,2 would work.

-
Distinct or not necessarily distinct numbers? – André Nicolas Feb 18 '13 at 12:48
not necessarilly distinct numbers as in 12,12,12,12,12,2,2,2,2,2 would work. – Ethan Brouwer Feb 18 '13 at 12:52
Do you need a closed form expression or a efficient algorithm? – Paresh Feb 18 '13 at 13:15
either or just some way to solve it – Ethan Brouwer Feb 18 '13 at 13:26

Generating functions would work, I think. Consider the product

$$(x + x^2 + \ldots + x^{12})^{10}$$

Then the coefficient of $x^{70}$ in the resulting polynomial is your answer: we have to pick a power from each factor (and we could take the same power several times, in different factors) such that their sum equals 70, and order does matter.

taking out the $x$ from each term we need the coefficient of $x^{60}$ in

$$(1 + x + \ldots + x^{11})^{10}$$ to get the answer.

We write the term as $\frac{1-x^{12}}{1-x}$, so we need the coefficient of $x^{60}$ in

$$(1 - x^{12})^{10} (1-x)^{-10}$$ and we can expand the latter using the (generalized) binomial theorem twice:

$$\left(\sum_{k=0}^{10} \binom{10}{k} (-1)^{k}x^{12k}\right)\left(\sum_{k=0}^{\infty} \binom{9+k}{k} x^k\right)\mbox{.}$$

To get $x^{60}$, there are several ways: in the left hand sum we have the powers $1,x^{12},\ldots,x^{60}$ to consider with their coefficients $1,-\binom{10}{1},\binom{10}{2},\ldots ,-\binom{10}{5}$ that we multiply with their complementary powers $x^{60},x^{48},\ldots,x^0$ and their coefficients $\binom{69}{9},\binom{57}{9},\ldots,1$ respectively.

So we get as answer $$\binom{69}{9} - \binom{10}{1}\binom{57}{9} + \binom{10}{2}\binom{45}{9} - \binom{10}{3}\binom{33}{9} + \binom{10}{4}\binom{21}{9} - \binom{10}{5}$$

-
The answer here, 2,018,464,261, agrees with the answer calculated by my implementation of Paresh's algorithm. – MJD Feb 18 '13 at 14:17
@MJD that's nice to know. I probably made no errors then... – Henno Brandsma Feb 18 '13 at 14:18
This result can also be derived using inclusion-exclusion and stars and bars: There are $\binom{69}9$ compositions of $70$ with $10$ positive parts, which yields the first term; but some of these have parts above $12$; so we need to subtract those that have at least one such part, which yields the second term; but then we've overcompensated for the ones that have more than one such part, and so on. – joriki Feb 18 '13 at 14:22
thank you so much! :D – Ethan Brouwer Feb 19 '13 at 0:02

I am not sure that an algorithm is what you are looking for, but for what its worth, here is a simple dynamic programming based algorithm formed from the following recurrence relation:

Let $f(n, x) = \text{number of ways to generate a sum of } x \text{ using exactly } n \text{ numbers from 1 to 12}$

Then, $f(n, x) = \sum\limits_{i=1}^{12}f(n-1, x-i)$

You are selecting the number $i$, then the remaining sum would be $x - i$, to be formed using $n-1$ more numbers. And you can select any of $1$ to $12$. $f(n, x) = 0$ if $x \le 0$.

What you want is $f(10, 70)$. Proceed in a bottom up approach. Create a $10$x$70$ matrix, where the $i^{th}$ row and $j^{th}$ column stores the value of $f(i, j)$. Fill up row 1, which would be the base case. Notice that the $i$th column in row $1$ means the number of ways to get a sum of $i$ using only $1$ number out of $1 \dots 12$. Hence, $f(1, i) = 1$ if $1 \le i \le 12$, and $0$ otherwise.

Proceed with successively calculating the subsequent rows. For any row, you would require values only from the previous row, which you have already computed. Keep this till you reach the $10^{th}$ row, and $70^{th}$ column.

This would be tedious by hand, but with a short computer code, this should be solved in a fraction of a second.

-
gist.github.com/mjdominus/4977692 is an implementation of this algorithm. If my code is correct, and we have not made any other errors, the answer is 2,018,464,261. – MJD Feb 18 '13 at 14:11
@MJD Thanks! And its great that the the answer tallies with the generating functions based approach in Henno's answer. – Paresh Feb 18 '13 at 14:30
Your prediction that it would take a fraction of a second was correct; around 0.026 seconds on my laptop. Also, getting the base cases of the algorithm correct is at least as tricky as getting the recursion correct. I was able to do it easily only because I have solved many such problems before. You might want to say something about the base cases. – MJD Feb 18 '13 at 14:38
@MJD I have explained the base case in more details. – Paresh Feb 18 '13 at 15:19
Spreadsheets are made for this sort of calculation. Once you have the second row, you just copy down for the rest. – Ross Millikan Feb 18 '13 at 15:39