# Horse race

luskin
Posers and Puzzles 20 May '08 13:56
1. 20 May '08 13:56
In how many ways, counting ties, can eight horses cross the finishing line?

(For example, two horses, A and B, can finish in three ways: A wins, B wins, A and B tie.)
2. wolfgang59
20 May '08 16:271 edit
3. forkedknight
Defend the Universe
20 May '08 20:113 edits
the Sum from i=1 to 8 of ( C(n, i) * P(n-i+1, n-i+1) )

*edit* where:
C(n, k) is the number of combinations of size k from a set of size n, and
P(n, r) is the number of permutations of size r from a set of size n

*edit 2*
and n = 8

*edit 3*
and this only accounts for cases where there is only one tie, but that tie can be between any or all of the horses, so it's not a complete solution...
4. forkedknight
Defend the Universe
21 May '08 18:282 edits
this should be a complete answer....

for i = 1:
P(8,8) = 8!
for i = 2:
for 1 tie: C(8, 2) * P(7, 7) = 8!/(6!2!) * 7!
for 2 ties: C(8,2) * C(6,2) * P(6,6) = 8!/(6!2!) * 6!/(4!2!) * 6!
for 3 ties: C(8,2) * C(6,2) * C(4,2) * P(5,5) = " * " * 4!/4 * 5!
for 4 ties: C(8,2) * C(6,2) * C(4,2) * C(2,2) * P(4,4) = " * " * " * 2 * 4!
for i = 3:
for 1 tie: C(8,3) * P(6,6) = 8!/(5!3!) * 6!
for 2 ties: C(8,3) * C(5,3) * P(4,4) = 8!/(5!3!) * 5!/(3!2!) * 4!
for i = 4:
for 1 ties C(8,4) * P(5,5) = 8!/(4!4!) * 5!
for 2 ties C(8,4) * C(4,4) * P(2,2) = 8!/(4!4!) * 1 * 2
for i = 5:
only 1 tie possible: C(8,5) * P(4,4) = 8!/(3!5!) * 4!
for i = 6:
" " " ": C(8,6) * P(3,3) = 8!/(6!2!) * 6
for i = 7:
" " " ": C(8,7) * P(2,2) = 16
for i = 8: 1

Therefore, the total is:
1 + 16 + 8!/(6!2!) * 6 + 8!/(3!5!) * 4! + 8!/(4!4!) * 5 * 2 +

8!/(4!4!) * 5! + 8!/(5!3!) * 5!/(3!2!) * 4! + 8!/(5!3!) * 6! +

8!/(6!2!) * 6!/(5!2!) * 4!/4 * 2 * 4! +

8!/(6!2!) * 6!/(4!2!) * 4!/4 * 5! +

8!/(6!2!) * 6!/(4!2!) * 6! + 8!/(6!2!) * 7! + 8!

*edit* fixed errors
5. forkedknight
Defend the Universe
21 May '08 18:28
I don't have time to simplify that; someone else can if they want...
6. forkedknight
Defend the Universe
21 May '08 18:32
btw, i is the number of horses in each tie...