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

Question

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.

Answer 1

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}$$

Answer 2

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.