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.

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.

share|improve this question
1  
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
add comment

3 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
Thank you! That was very well explained and exactly what I was looking for. –  daniellopez46 Jun 18 '12 at 15:01
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.