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.

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.

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

2 Answers 2

up vote 8 down vote accepted

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

share|improve this answer
    
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
1  
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.

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

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.