# Number of ways to order numbers such that greatest number proceeds smallest number

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?

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

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.

-
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!}$$

-

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

-
Velcome to the site! –  kjetil b halvorsen May 19 at 8:27