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.

With a set of numbers of length n, how many ways are there to order the set such that the greatest number always proceeds the smallest number.

For example, if n = 3, there are 6 total permutations, but only 3 ways to order it with the restriction in place:

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

I brute force wrote down the permutations for n=2, n=3, n=4 and n=5 and came up with a solution:

$$ \frac{n!}{2!} $$

This seems to be a correct solution, but not sure how it relates to the problem. Can anyone point me in the right direction?

share|improve this question
1  
In words, you seem to be describing the complement of the set that you've illustrated. You crossed out those permutations in which $3$ precedes (note: spelling) $1$. –  Sammy Black May 19 at 5:46
1  
There are $n!$ ways to order the numbers. By symmetry the greatest will proceed the smallest in exactly half of them. –  Improve May 19 at 5:47
5  
For this problem, it doesn't matter, as you could just as well be reading from right to left. This actually explains your answer. –  Sammy Black May 19 at 5:48
1  
Your formula is correct, there are always pairs where every position is the same except for the smallest and largest number, and from each pair you only select one. –  LutzL May 19 at 5:48

3 Answers 3

up vote 7 down vote accepted

Take any permutation; then switch the greatest and smallest numbers if they are the wrong way around. So, exactly half of all permutations satisfy your condition.

share|improve this answer
    
which is equal to $\frac{n!}{2}$ –  ratchet freak May 19 at 12:53

This problem is equivalent to arranging $n-2$ distinct numbers and $2$ alike numbers. Whichever alike number comes first, we name it smallest and the latter as largest. Hence, $$\dfrac{(n-2+2)!}{2!}=\dfrac{n!}{2!}$$

share|improve this answer

Consider that the size of the set of locations for the min and max is equal to the number of combinations computed when taking 2 locations from n locations, nC2. This computation only takes into account all instances of sets of size 2 with a unique non-ordered composition of locations. We then consider that for every set of two locations occupied by the min and max (such that the min and max are indistinguishable), the size of the set of (n-2) distinguishable digits occupying (n-2) locations is equal to (n-2)!.

Thus, the number of permutations for which the Max precedes the Min equals:

nC2 * (n-2)!

which is equivalent to:

n!(n-2)!/2!(n-2)!

which simplifies to:

n!/2!

QED

share|improve this answer
    
Velcome to the site! –  kjetil b halvorsen May 19 at 8:27

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.