Page 2 of 2 FirstFirst 12
Results 16 to 27 of 27

Thread: Total number of permutations

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

    Re: Total number of permutations

    Does this account for the fact that the order matters? In other words, is 8,17,17,17,17,17,17,17,17 and 17,17,17,17,17,17,17,17,8 considered two different solutions?

    Jeff
    Follow Math Help Forum on Facebook and Google+

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

    Re: Total number of permutations

    Quote Originally Posted by jeffsbenson View Post
    Does this account for the fact that the order matters? In other words, is 8,17,17,17,17,17,17,17,17 and 17,17,17,17,17,17,17,17,8 considered two different solutions?

    Jeff
    Yes
    Follow Math Help Forum on Facebook and Google+

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

    Re: Total number of permutations

    15 15 15 12 17 16 15 16 13
    Follow Math Help Forum on Facebook and Google+

  4. #19
    Newbie
    Joined
    Oct 2017
    From
    Phoenix
    Posts
    13

    Re: Total number of permutations

    Disregard this...having issues obviously ;-)
    Follow Math Help Forum on Facebook and Google+

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

    Re: Total number of permutations

    Can you point me to any further information on solving this equation? It's been a while ;-) and just need to refresh myself. I want to understand how to solve if say 0<=xk<=30 or 20<=xk<=30 and so forth (sorry I don't have the proper symbols like in your post). I really appreciate the help on this!
    Follow Math Help Forum on Facebook and Google+

  6. #21
    Newbie
    Joined
    Oct 2017
    From
    Phoenix
    Posts
    13

    Re: Total number of permutations

    Can you please send me some references on this? It's been a while and wanting to understand this a little more as well as the way it is solved so that if I want to change the constraints (i.e. 0<=x<=30 or 5<=x<=25, etc...) I can easily do it. Thank you!
    Follow Math Help Forum on Facebook and Google+

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

    Re: Total number of permutations

    It is the number of integral solutions to linear Diophantine equations. Here is the idea. You have:

    $x_1+x_2+x_3+\cdots x_n = k $

    That is n variables that have to add up to k. Suppose we have the constraints $0 \le x_i $.

    Now, we can consider an alternate problem. Suppose we have n-1 vertical separators and k * symbols. Now, when we permute these symbols, we get a pattern like this:
    **|***||*|...
    However many *'s wind up to the left of the first separator represent a value for $x_1$, between the first and second ones is the value of $x_2$, etc. So, in the example I gave, we have
    $x_1=2$
    $x_2=3$
    $x_3=0$
    $x_4=1$
    .
    .
    .

    So, as you can see, each $x_i $ will have at least 0, but the upper bound will be k. The total number of permutations is
    $\dbinom{n-1+k}{n-1} $

    Now, what happens when you have a lower bound that is not zero? You need to consider an associated problem where the lower bound is zero. Example $20\le x_i $. Consider the associated problem where $y_i=x_i-20$. Now $0\le y_i$ and $\displaystyle \sum_{i=1}^n y_i = \sum_{i=1}^n (x_i-20) = \left[ \sum_{i=1}^n x_i \right] -20n = k-20n $

    So, this associated problem has a number of solutions equal to $\dbinom{n-1+k-20n}{n-1} $

    Upper bounds are a little more tricky. You need to use inclusion/exclusion. So, if $0\le x_i \le 30$, you need to calculate the total number of solutions with no upper bound, subtract the number of solutions where exactly 1 of the $x_i$'s violates the upper bound, add back in where exactly two violate the upper bound, subtract off for exactly 3 violations, etc.

    If exactly 1 violates the upper bound then for some j, $31\le x_j $ so, now we have a lower bound and we can apply the associated problem technique. For all $i\neq j $ we have $y_i=x_i $ and $y_j=x_j-31$. There are $\dbinom{n-1+k-31}{n-1}$ solutions that violate the upper bound for $x_j $. Some of those solutions also violate the upper bound for other $x_i$'s, which is why we need Inclusion/Exclusion.

    The end formula:
    $\displaystyle \sum_{i=0}^n (-1)^i\dbinom{n}{i}\dbinom{n-1+k-31i}{n-1} $

    If you have $a\le x_i\le b $ then the final formula becomes:

    $\displaystyle \sum_{i=0}^n (-1)^i\dbinom{n}{i}\dbinom{n-1+k-na-(b-a+1)i}{n-1}$

    Here, I define that for any positive integers $r,s $, $\dbinom{-r}{s}=0$ (this becomes tricky when you start looking at Gamma function generalizations of the binomial coefficients, so it must be defined to be true).
    Last edited by SlipEternal; Oct 14th 2017 at 06:17 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #23
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,454
    Thanks
    2728
    Awards
    1

    Re: Total number of permutations

    Quote Originally Posted by jeffsbenson View Post
    Can you please send me some references on this? It's been a while and wanting to understand this a little more as well as the way it is solved so that if I want to change the constraints (i.e. 0<=x<=30 or 5<=x<=2en5, etc...) I can easily do it. Thank you!
    Two books: Discrete Mathematics, by J.A. Anderson & Mathematics of Choice by Ivan Niven. The latter is a renown mathematician. I think his book is among the best. I will say that on this topic, I find his approach too tedious.

    How many solutions are there for $\sum\limits_{k = 1}^9 {{x_k}} = 450$ in the non-negative integers?
    The answer is $\dbinom{450+9-1}{450}$ that is the number of ways of placing 450 identical object into nine distinct cells.

    Lets take that problem as the base problem.
    The given solution allows for the cases in which some of the variables could equal zero.

    a)What would be the solution if we only want positive solutions?
    Well think of taking nine ones and placing one each into the nine cells $(x_i)$.
    So how many ways can we place the remaining 441 ones into the nine cells: $\dbinom{441+9-1}{441}$


    b) Now suppose we want to require that $x_5\ge 6~\&~x_8>3~?$
    OK. go ahead and place six balls into cell $\#5(x_5) $ & four balls into cell $\#8(x_8)$ [Why four ball in cell eight?]
    Thus the answer is $\dbinom{440+9-1}{440}$


    c) Now suppose we want to require that $x_1\le 6~?$ Now we do not want to count any case in which $x_1>6$.
    If we go ahead and put seven into cell #1 and then distribute the remaining 443 ones in $\dbinom{443+9-1}{443}$ ways.
    BUT we do not those because in all of those $x_1>6$. So subtract the unwanted cases off.
    The answer is $\dbinom{450+9-1}{450}-\dbinom{443+9-1}{443}$
    Follow Math Help Forum on Facebook and Google+

  9. #24
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,691
    Thanks
    318

    Re: Total number of permutations

    A Picassonian solution, Plato.
    You are our CELLular zero...whoops...hero !
    Follow Math Help Forum on Facebook and Google+

  10. #25
    Newbie
    Joined
    Oct 2017
    From
    Phoenix
    Posts
    13

    Re: Total number of permutations

    Thank you both for your responses - this is taking me back to my good ole college days. Just to make sure I understand. If I assume that any number between 0 to 30 can be selected 9 different time and must add up to 144, the solution would be:

    Sum (k=1 to 9) = 30*9-144 = 126 = 2,083,664,995,984. Am I following correctly - it's a big number so just want to make sure I am on track? Sorry for not being able to do the proper math formatting :\
    Follow Math Help Forum on Facebook and Google+

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

    Re: Total number of permutations

    Quote Originally Posted by jeffsbenson View Post
    Thank you both for your responses - this is taking me back to my good ole college days. Just to make sure I understand. If I assume that any number between 0 to 30 can be selected 9 different time and must add up to 144, the solution would be:

    Sum (k=1 to 9) = 30*9-144 = 126 = 2,083,664,995,984. Am I following correctly - it's a big number so just want to make sure I am on track? Sorry for not being able to do the proper math formatting :\
    Let's use my formula from above:

    $\displaystyle \sum_{i=0}^9 (-1)^i \dbinom{9}{i} \dbinom{9-1+144-31i}{9-1} = \dbinom{152}{8} - 9\dbinom{121}{8}+\dbinom{9}{2}\dbinom{90}{8}-\dbinom{9}{3}\dbinom{59}{8}+\dbinom{9}{4}\dbinom{2 8}{8}$

    That adds up to:

    $366,665,344,714$
    Follow Math Help Forum on Facebook and Google+

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

    Re: Total number of permutations

    Thank you!
    Follow Math Help Forum on Facebook and Google+

Page 2 of 2 FirstFirst 12

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