Win a copy of Functional Reactive Programming this week in the Other Languages forum!

# Another horse race

Arjun Shastry
Ranch Hand
Posts: 1899
1
In a horse race there are N horses.In how many ways they can finish the race?

Stefan Wagner
Ranch Hand
Posts: 1923
Assuming two horses, they can finish:
1-2
2-1
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.

Francis Siu
Ranch Hand
Posts: 867
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 ]

Arjun Shastry
Ranch Hand
Posts: 1899
1
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.

Stefan Wagner
Ranch Hand
Posts: 1923
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
Posts: 1899
1
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
Posts: 1899
1
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

shankar vembu
Ranch Hand
Posts: 309
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

Is this OK?

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

shankar vembu
Ranch Hand
Posts: 309
Originally posted by shankar vembu:

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.

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