**Source:**http://www.qbyte.org/puzzles/puzzle14.html

**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.

General solution assuming n horses.

ReplyDeleteLet 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!

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

ReplyDeleteeejee. 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

ReplyDeleteAnother solution:

ReplyDeleteThe 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.

Ramdas is referring to "Stirling numbers of second kind"

ReplyDeleteThanx :)

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

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

ReplyDeleteHere 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.

Awesome.. good one.. Thanx..

ReplyDeleteI got a recursive solution which I wasn't able to convert in closed form. The logic is this -

ReplyDeleteLet 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.

Looks correct to me :)

ReplyDeleteWin 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

ReplyDelete