Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

2 Answers

up vote 1 down vote accepted

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)

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.