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.

here is a simple algoritm that I implimented in Excel to come up with the answer

create a list for each N where N is the number of contestants where the kth element of the list corresponds with the number of finishings with k "groups".  for example if for 5 contestants (a,b,c,d,e) you consider the finishing ab,c,de  there are 3 groups.  1) ab tie  2) c 3) de tie.  hopefully that makes sense.

so for N=1 the list is obviously just {1}

now I will explain how to create the Nth list based on the (N-1) list.

the first value is always one,  then for every kth element with k<N we get its value by adding the k and k-1 value from the N-1 list.  for the Nth value it is simply N!.

so for N=2 we get {1,2}

for N=3 we get {1,6,6}

for N=4 we get {1,14,36,24}

and so on and so forth.  to get the number of combinations you simply total the list

using this I get the flowing series

1,3,13,75,541,4683,47293,545835,7087261,102247563

and so for N=10 we get 102,247,563 which coincides with Dennis' submission.

I am currently trying to find a simple closed form based on this algoritm by it is currently alluding me :-)

Posted by Daniel on 2008-01-13 09:53:07