2
$\begingroup$

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.

  • 1
    Incidentally, it's also known how to compute this (well, asymptotically) if you _do_ allow ties. See http://oeis.org/A000670 .2012-06-15

4 Answers 4

3

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.

  • 0
    Thank you! That was very well explained and exactly what I was looking for.2012-06-18
1

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

0

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.

-1

Decent answers. However, with no duplicates, the solution may be more simply explained.

Since no ties are involved (duplicates) each position can have one less than the next highest finisher and thus we get:

3 * 2 * 1 = 6

If there were 5 people in the race, the solution would then be 5 * 4 * 3