# horse race counting

#### feminist

In a race there are n horses.In that race, more than one horse may get the same position. For example, 2 horses can finish in 3 ways.

1. Both first
2. horse1 first and horse2 second
3. horse2 first and horse1 second
How can I find out the number of ways the race can finish for any n.Is there any recurrence relation to calculate the number of ways? Need help to understand the solving way with better explanation.

#### chiro

MHF Helper
Hey feminist.

You should break this up into two groups: the first group contains situations when you have two horses get the same position for all possible positions, and the next should be when no horse gets the same position as another.

If you have n positions (and n horses) then you can only have n - 1 instances of a tie with a position (1,2,..,n-1).

If you don't have any ties then you are basically finding the number of ways (1,2,3,...,n) can be ordered in any way possible.

You should be able to find a combinatoric identity for this and I would do the second part first before the first one.