# Thread: Total number of permutations

1. ## Total number of permutations

Hello -

I have a problem that I am trying to solve at work and am a little rusty. I think this may be a stars and bars problem but am not certain.

Here is the gist:

-- I can select 9 numbers (1 through 17) that when added together must equal 144.
-- Repetition is allowed (e.g. 17, 17, 17, 17, 17, 17, 17, 17, 8)
-- This needs to be permutations and not combinations as 17, 17, 17, 17, 17, 17, 17, 17, 8 and 8, 17, 17, 17, 17, 17, 17, 17, 17 are not the same....

Jeff

2. ## Re: Total number of permutations

Originally Posted by jeffsbenson
Hello -

I have a problem that I am trying to solve at work and am a little rusty. I think this may be a stars and bars problem but am not certain.

Here is the gist:

-- I can select 9 numbers (1 through 17) that when added together must equal 144.
-- Repetition is allowed (e.g. 17, 17, 17, 17, 17, 17, 17, 17, 8)
-- This needs to be permutations and not combinations as 17, 17, 17, 17, 17, 17, 17, 17, 8 and 8, 17, 17, 17, 17, 17, 17, 17, 17 are not the same....

Jeff
The answer is $\dfrac{9!}{8!}$

If it were $17, 17, 17, 17, 17, 15, 15, 15, 14$ The answer is $\dfrac{9!}{5!\cdot 3!}$

3. ## Re: Total number of permutations

Hmmmm....I don't think this solution works. I probably wasn't clear enough. For each of the 9 choices, I am allowed to choose between 1 and 17 with repetition as long as it adds up to 144. There is way more than the number of permutations than your formula suggests.

4. ## Re: Total number of permutations

24,310 if you are just looking for the answer.

5. ## Re: Total number of permutations

I would like to know the formula and possibly a link or brief explanation. Based on my math, there are a total of 68,719,476,736 possible permutations if I am allowed to choose 16 numbers 9 times (16^9). I want to know how many of those possible permutations when added together equals 144.

6. ## Re: Total number of permutations

I created an Excel spreadsheet. On the first row, I put 17,17,17,17,17,17,17,17,8. Then, in the columns below, I put the following formulas:
Code:
A2: =IF(B1=8+17-A1,A1-1,A1)
B2: =IF(A2<A1,17,IF(C1=8+34-A1-B1,B1-1,B1))
C2: =IF(OR(A2<A1,B2<B1),17,IF(D1=8+51-SUM(A1:C1),C1-1,C1))
D2: =IF(OR(A2<A1,B2<B1,C2<C1),17,IF(E1=8+68-SUM(A1:D1),D1-1,D1))
E2: =IF(OR(A2<A1,B2<B1,C2<C1,D2<D1),17,IF(F1=8+85-SUM(A1:E1),E1-1,E1))
F2: =IF(OR(A2<A1,B2<B1,C2<C1,D2<D1,E2<E1),17,IF(G1=8+102-SUM(A1:F1),F1-1,F1))
G2: =IF(OR(A2<A1,B2<B1,C2<C1,D2<D1,E2<E1,F2<F1),17,IF(H1=8+119-SUM(A1:G1),G1-1,G1))
H2: =IF(I1=17,17,H1-1)
I2: =IF(I1=17,144-SUM(A2:H2),I1+1)
I copied those formulas down 100,000 rows. Then, I found the minimum row number where the value in column A was at no more than 8. That was 24,310.

7. ## Re: Total number of permutations

What about the permutation 15,15,15,12,17,16,15,16,13? looks like you are fixing things to the value of 17?

8. ## Re: Total number of permutations

Originally Posted by jeffsbenson
What about the permutation 15,15,15,12,17,16,15,16,13? looks like you are fixing things to the value of 17?
That adds to 134. I thought you wanted it to add to 144. If you go down to the bottom, eventually, it will get to all of the permutations. I fix 17 as the maximum, but it can be less than 17 for every number.

9. ## Re: Total number of permutations

You're right that addition didn't work on my example ;-). Part of the reason I am trying to stay away from excel, however, is that what if the possibilities increase to 30, 40, 60, etc.. numbers? I would like to know what the formula is to figure this out rather than calculating in Excel.....

10. ## Re: Total number of permutations

$\displaystyle \displaystyle \sum_{a_1=8}^{17} \left[ \sum_{a_2=25-a_1}^{17} \left( \sum_{a_3=42-a_1-a_2}^{17} \left[ \sum_{a_4=59-a_1-a_2-a_3}^{17} \left( \sum_{a_5=76-a_1-a_2-a_3-a_4}^{17} \left[ \sum_{a_6=93-a_1-a_2-a_3-a_4-a_5}^{17} \left( \sum_{a_7=110-a_1-a_2-a_3-a_4-a_5-a_6}^{17} \left[ \sum_{a_8=127-a_1-a_2-a_3-a_4-a_5-a_6-a_7}^{17} 1 \right] \right) \right] \right) \right] \right) \right]$

11. ## Re: Total number of permutations

Originally Posted by jeffsbenson
What about the permutation 15,15,15,12,17,16,15,16,13? looks like you are fixing things to the value of 17?
I though you were asking about a particular solution. But clearly you are not.

So try this. How many solutions are there $\sum\limits_{k = 1}^9 {{x_k}} = 144,\quad \& \quad 0 \leqslant {x_k} \leqslant 17$

That is the same as asking: How many ways are there to put one hundred and forty-four identical balls into nine different cells, where cells may be empty but no cell may contain more than seventeen balls.

That is well known and not easy to solve. If that is a correct reading I can give several references.

If is not correct, please explain in detail why not.

12. ## Re: Total number of permutations

This sounds right. The constraints could change as well. In other words, it could be that we need to choose numbers 0 to 30....

13. ## Re: Total number of permutations

Originally Posted by Plato
I though you were asking about a particular solution. But clearly you are not.

So try this. How many solutions are there $\sum\limits_{k = 1}^9 {{x_k}} = 144,\quad \& \quad 0 \leqslant {x_k} \leqslant 17$

That is the same as asking: How many ways are there to put one hundred and forty-four identical balls into nine different cells, where cells may be empty but no cell may contain more than seventeen balls.

That is well known and not easy to solve. If that is a correct reading I can give several references.

If is not correct, please explain in detail why not.
Close. You are allowing 0's, but the OP is not. Anyway, we should probably look at the paired system $y_k = 17-x_k$. Then, $\displaystyle \sum_{k=1}^9 y_k = 17\cdot 9-144 = 9$ has $\binom{9+9-1}{9} = 24,310$ possible solutions.

14. ## Re: Total number of permutations

Originally Posted by SlipEternal
Close. You are allowing 0's, but the OP is not