# Thread: Total number of permutations

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

2. ## Re: Total number of permutations

Originally Posted by jeffsbenson
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

3. ## Re: Total number of permutations

15 15 15 12 17 16 15 16 13

4. ## Re: Total number of permutations

Disregard this...having issues obviously ;-)

5. ## 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!

6. ## 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!

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

8. ## Re: Total number of permutations

Originally Posted by jeffsbenson
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}$

9. ## Re: Total number of permutations

A Picassonian solution, Plato.
You are our CELLular zero...whoops...hero !

10. ## 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 :\

11. ## Re: Total number of permutations

Originally Posted by jeffsbenson
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}$

$366,665,344,714$