Assuming two horses, they can finish: 1-2 2-1 (1,2) dead race 1 (2 DNF) 2 (1 DNF) (1,2 DNF)

DNF: Did not finish. (Horse lost jockey, for instance). Instead of DNF disqualification could occur. But the difference isn't important for betters or price-money.

Do you have a more clean abstract idea of 'finishing' a race.

Of course we should argue, whether 'did not finish' is a way to finish. Sounds absurd.

In how many ways they can finish the race? If I understand what you ask Um.......... Assume that there are n horse and without any accident within the racing the permutation will be nx(n-1)....x1 ==n!

If one accident occurs the permutation will be 2(n)x2(n-1)....x1== 2(n)!-1

If there are k accident the permutation will be k(n)xk(n-1)x....x1== k(n)!-(k-1)

It may be wrong Does it require to write a program to show it out all the permutation and generate it out? [ October 05, 2004: Message edited by: siu chung man ]

Francis Siu
SCJP, MCDBA

Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1878

posted

0

No accident.Assume everything goes well. Suppose there are two horses,1 and 2 then race can be finished as 1 finished the race followed by 2 1 and 2 finish at the same time. 2 finished the race followed by 1 So there are three ways in which 2 horses can finish the race. Hope this helps.

Excluding dead-race, we get n! results for n horses.

But how many dead-races are possible? n possibilities 1 0 2 1 3 7 4 ... ?

Hm. With result of the race, are we interested in every position, or only in the first 3 horses?

Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1878

posted

0

Yes,dead race means reaching at same time ,right? if we exclude that then n! possibilities.But we want to consider dead race!!.That is interesting.Actually its integer partition problem. Say there are 4 horses then 4 can be partitioned as 4----Means all arrive at same time 1+1+2(one followed by second and rest arrive at same moment).Now 2 horses can be chosen in 6 ways.and another horse in two ways.So there will be 6*3! ways in which this combination can arrive. in similar fashion, 1+1+1+1 Each arrives at different time,4!,24 ways 1+3---4*2! ways 2+2---6 ways In all there are 75 ways How to generalize for N?I am not sure.

Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1878

posted

0

Is there any similarity between this and factorization of a number.? Say number is 24.Factors are 2,2,2,3.Number of ways in which 24 can be factored are 2*(12),2*2*(6),2*3*(4),2*2*2*3,3*(8),4*6

Originally posted by Arjun Shastry: Is there any similarity between this and factorization of a number.? Say number is 24.Factors are 2,2,2,3.Number of ways in which 24 can be factored are 2*(12),2*2*(6),2*3*(4),2*2*2*3,3*(8),4*6

Let me try. 1. No dead races(one winner) = n! 2. 2 winners = nc2*(n-2)! We have nc2 ways to choose 2 winners. The rest (n-2) can be arranged in (n-2)!

So on and so forth.

Total = nc1*(n-1)! + nc2*(n-2)! + nc3*(n-3)! + ....+ ncn(n-n)!

Notes: First term = n! is essentially point# 1 stated above. Last term = 1 = all horses are winners

Let me try. 1. No dead races(one winner) = n! 2. 2 winners = nc2*(n-2)! We have nc2 ways to choose 2 winners. The rest (n-2) can be arranged in (n-2)!

So on and so forth.

Total = nc1*(n-1)! + nc2*(n-2)! + nc3*(n-3)! + ....+ ncn(n-n)!

Notes: First term = n! is essentially point# 1 stated above. Last term = 1 = all horses are winners

Is this OK?

SHankar.

[ October 25, 2004: Message edited by: shankar vembu ]

I assumed that dead race applies only to position 1. A more general solution would be:

Let A(n) = total no. of arrangements for n horses(where dead races are possible in every position). So A(n) = nc1.A(n-1) + nc2.A(n-2) + nc3.A(n-3)......... where (recurse....) A(n-1) = (n-1)c1.A(n-2) + (n-1)c2.A(n-3) + (n-1)c3.A(n-4)...... A(n-2) = (n-2)c1.A(n-3) + (n-2)c2.A(n-4) + (n-2)c3.A(n-5)...... . . . . . I guess I am near to the solution. Any other formulations? Basically, this would be a "bottom-up" computation.