# Ways to add up 10 numbers between 1 and 12 to get 70, where order is unimportant

How would I solve this: "Ways to add up 10 numbers between 1 and 12 to get 70" if order is unimportant? Thank you!

-
Using generating functions, you can write this as $$[y^{10}x^{70}](1+yx+y^2x^2+\dotso)\cdots(1+yx^{12}+y^2x^{2\cdot12}+\dotso)\\=[y^{‌​10}x^{70}]\frac1{1-yx}\cdots\frac1{1-yx^{12}}\;,$$ but I don't know how you could efficiently use that to compute the answer. – joriki Feb 19 '13 at 8:53

Let $f(n,k,s)$ be the number of ways to add up $n$ numbers from $\{1,\ldots,k\}$ to get $s$. Then you want $f(10,12,70)$. We have the recursion $$f(n,k,s)=\sum_{j=1}^{\min\{k,s\}}f(n-1,j,s-j)$$ and base cases $$f(1,k,s)=\begin{cases}1&\text{if }k\geq s\\0&\text{if }k<s\end{cases}.$$ (Also one can use $f(n,k,s)=0$ if $s>n$ or $nk<s$ to simplify)

-
I've modified the formula for the base case, which appeared to be wrong. – Marc van Leeuwen Feb 19 '13 at 10:51
If anyone could help, I'm trying to put this in python code. Here is my question on stackoverflow: Here Thanks a lot Hagen von Eitzen and Marc van Leeuwem! – Ethan Brouwer Feb 19 '13 at 11:31
As you can see in my answer, it can be done somewhat more concisely. – Marc van Leeuwen Feb 19 '13 at 11:46

This question is equivalent to counting the number of ways to pay an amount of $70$ cents using precisely $10$ coins, where possible values of the coins are $1,2,\ldots,12$ cents.

One way to concretely compute this value is to use a $0$-based $71\times11$ integer matrix $A$ where $A[i,j]$ with $0\leq i\leq 70$ and $0\leq j\leq 10$ counts the number of ways to pay $i$ cents with $j$ coins; this array is iteratively updates as new denominations of coins become available. Initially there aren't any coins, so $A[0,0]=1$ and all other values are $0$.

When a new denomination $k$ becomes available, it can either be used or not, so we update $A$ using a loop

for from k to 70
for j from 1 to 10
A[i,j] +:= A[i-k,j-1]


where "+:=" means the RHS is added to the entry on the left. A crucial point is that since the loops on $i,j$ are increasing, the value added to $A[i,j]$ was already updated before it is used, and therefore incorporates the possibility of using coin $k$ again in what remains after taking one coin $k$. So what is left is to run this set of loops in another loop for $k=1,2,\ldots,12$. If I made no mistakes in keyboarding this, the answer is $9160$ possibilities.

-