# Formula to calculate the number of possible positions for $x$ numbers

What formula do I use to calculate the number of possible positions for $x$ numbers?

Let's say I have $3$ people in a race. What are all the possible combinations of the order they can finish in? Let's assume ties are not possible. I heard I use factorial but its been a while since I have used factorials. So I want to verify.

-
Incidentally, it's also known how to compute this (well, asymptotically) if you do allow ties. See oeis.org/A000670 . – Qiaochu Yuan Jun 15 '12 at 1:02

It is easy to enumerate for three people. Lets call the people $x_1,x_2,x_3$. The possible orderings are shown below.

1. $x_1,x_2,x_3$
2. $x_1,x_3,x_2$
3. $x_2,x_1,x_3$
4. $x_2,x_3,x_1$
5. $x_3,x_1,x_2$
6. $x_3,x_2,x_1$

In general, in a $n$ people race, lets denote the people by $x_1,x_2,\ldots,x_n$. The first position can be taken by any one of the $n$ individuals. Hence, there are $n$ options for the first place. Now given that the first position is taken by $1$ individual, for each of the $n$ options for the first position, the second position can be taken by any one of the remaining $n-1$ individuals. Proceeding like this, in general the $k^{th}$ position can be taken by any one of the remaining $n-k+1$ individuals. Hence, the total number of ordering is given by $$n \times (n-1) \times \cdots \times (n-k+1) \times \cdots 2 \times 1$$which is nothing but $n!$.

In you case, $n=3$ gives us $3! = 6$ which matches with our enumeration.

-
Thank you! That was very well explained and exactly what I was looking for. – daniellopez46 Jun 18 '12 at 15:01

Suppose there is 1 person in the race. There is only one possible combination.

A 2nd racer ( #2) is in the race. This person can be placed in 2 places(in front of 1 , or behind 1) There are now 2 possible combinations 12 21

a 3rd person enters the race. Racers 1 and 2 are in place, number 3 has 3 possible places to fit in(in the front, between 1 and 2, or in the back. Because there are 2 possible positions for 1 and 2, there are 3*2 possible combinations for 3 racers

12 becomes 312, 132, or 123

21 becomes 321, 231, or 213

a 4th racer enters, there are 4 places this new racer can fit in There will be 4*6 possible combinations

n racers have n! possible positions

-

Number of possibilites for (1) to end first: two, as we have (1)-(2)-(3) and (1)-(3)-(2). A moment of thought will convince us it is the same for any of the three competitors (1), (2), (3) to finish at first place. Thus, all in all there are $\,3!=6\,$ possibilities.

Using this line of thought and some induction, you can prove a similar result for $n\,$ competitors: there are $\,n!\,$ different ways they can end the race.

-