Horse Race


Problem: (An interesting counting exercise)
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.)

Update(21/01/10): (simple combinatorics problem)
Solution: Solution posted by Nikhil Garg (Sophomore, IIT Delhi) in comments!!
Update(06/02/10): Interesting solution posted by Aman too.


  1. General solution assuming n horses.

    Let all horses which reach at same time (have a tie ) belong to a group. Finally let there are k groups of horses. ( 1<=k<=n) . We can partition n horses in k such sets in S(n,k) ways. Now once we have k groups , we can arrange their order in k! ways.
    So number of ways in which k groups are there is : S(n,k) * k !

    Answer to problem is:
    summation over all k -> S(n,k) * k!

  2. Thanx. Elegant and simple solution to a very simple problem. :) Nice

  3. eejee. however for the readers, you should bother to specify that S(n,k) are the stirling numbers of the second kind, or rather the obv recursive relation is S(n,k)= k*S(n-1,k) + S(n-1,k-1) or whtever:P

  4. Another solution:

    The number of ways in which k ranks can be allotted to n horses such that each rank is allotted at least once is :

    coeff. of x^n in
    n!*(x + x^2/2! + x^3/3!......)^k
    = n!*(e^x -1)^k

    summing the above over all k and collecting the coefficients gives the answer.

  5. Ramdas is referring to "Stirling numbers of second kind"
    Thanx :)

    @Aman.. How? Am I missing something? :(

  6. I accept, it wasn't so trivial, I should have explained it before.

    Here is the explanation:

    Suppose the horses are divided into k groups with x1 in 1st, x2 in 2nd and so on.
    Then the number of permutations with this particular grouping is n!/(x1!*x2!.....*xk!)

    The above expression essentially gives the sum of all such permutations with different values of x1,x2...xk such that x1 + x2 +....xk = n (i.e. all possible different groupings)

    We can extend each of the expressions (x + x^2/2! .....)
    upto infinity as none of the higher terms contribute to the desired coeff. of x^n.

  7. I got a recursive solution which I wasn't able to convert in closed form. The logic is this -
    Let N(i) be the solution for i horses
    Then N(n) = summation(nCi*N(n-i)) for i in {1,...,n}
    It can be explained as follows - pick only one horse for 1st rank in nC1 ways and multiply it by N(n-1) else pick exactly two in nC2 and multiply by N(n-2) and so on.

    I don't know what Stirling numbers are but since those are themselves recursive, I suppose there is no closed form solution to this.

  8. Win Bets Consistently It Teaching Horse Race Betters The Correct Procedures To Win Bets On High-odds Horses Consistently And To Enjoy The Races. It Also Teaches Betting Strategies


Post a Comment