In a race among 10 contestants, how many orders of finish are there, counting possibilities of ties?

For example, in a 4-person race, A and B finishing at the same time, before C and D finish simultaneously, is a different order from C and D finishing together before A and B finishing together, and of course each of the 4! ways of all finishing separately are different orders.

Suppose there are N participants in the race with J1 coming in distinct positions (J1! ways to order this group), J2 coming in two way ties (J2! to order this group) etc. So then the total number of ways to get such an occurrence is

J1! J2! .. JN! (J1 + J2 +.. + JN)!

These terms have to be added up for all combinations of the Js subject to the constraint that

J1 + 2*J2 + 3*J3 + ... + N*JN = N

I suspect there is no simpler expression for this sum, which becomes rather tedious to calculate by hand once N grows above about 5. To demonstrate the workings of the formula I'll examine the situation for N=4. Here we have to sum over 5 terms:

(J4=1) + (J3=1, J1=1) + (J2=2) + (J2=1, J1=2) + (J1=4) giving

1 + 2 + 2 + 6 + 24 = 35

 

 

Posted by FrankM on 2008-01-13 23:58:49