Page 1 of 2 12 LastLast
Results 1 to 15 of 27

Thread: Total number of permutations

  1. #1
    Newbie
    Joined
    Oct 2017
    From
    Phoenix
    Posts
    13

    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....

    Thank you for your help!

    Jeff
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,454
    Thanks
    2728
    Awards
    1

    Re: Total number of permutations

    Quote Originally Posted by jeffsbenson View Post
    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....

    Thank you for your help!

    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!}$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2017
    From
    Phoenix
    Posts
    13

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,967
    Thanks
    1140

    Re: Total number of permutations

    24,310 if you are just looking for the answer.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2017
    From
    Phoenix
    Posts
    13

    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,967
    Thanks
    1140

    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.
    Last edited by SlipEternal; Oct 13th 2017 at 01:02 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Oct 2017
    From
    Phoenix
    Posts
    13

    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?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,967
    Thanks
    1140

    Re: Total number of permutations

    Quote Originally Posted by jeffsbenson View Post
    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.
    Last edited by SlipEternal; Oct 13th 2017 at 01:12 PM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Oct 2017
    From
    Phoenix
    Posts
    13

    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.....
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,967
    Thanks
    1140

    Re: Total number of permutations

    \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]
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,454
    Thanks
    2728
    Awards
    1

    Re: Total number of permutations

    Quote Originally Posted by jeffsbenson View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Oct 2017
    From
    Phoenix
    Posts
    13

    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....
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,967
    Thanks
    1140

    Re: Total number of permutations

    Quote Originally Posted by Plato View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,454
    Thanks
    2728
    Awards
    1

    Re: Total number of permutations

    Quote Originally Posted by SlipEternal View Post
    Close. You are allowing 0's, but the OP is not
    Look at reply #12.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,967
    Thanks
    1140

    Re: Total number of permutations

    Quote Originally Posted by Plato View Post
    Look at reply #12.
    Good point
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: Mar 2nd 2015, 06:18 PM
  2. Total number of possible JPEG's
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Jun 29th 2011, 10:40 AM
  3. Replies: 0
    Last Post: Jul 11th 2010, 06:18 AM
  4. Total Number of Points
    Posted in the Pre-Calculus Forum
    Replies: 9
    Last Post: Oct 17th 2008, 02:37 PM
  5. total number of combinations
    Posted in the Statistics Forum
    Replies: 3
    Last Post: Sep 11th 2007, 05:49 PM

/mathhelpforum @mathhelpforum