programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Tim Cooke
• Campbell Ritchie
• Paul Clapham
• Ron McLeod
• Liutauras Vilda
Sheriffs:
• Jeanne Boyarsky
• Rob Spoor
• Bear Bibeault
Saloon Keepers:
• Jesse Silverman
• Tim Moores
• Stephan van Hulst
• Tim Holloway
• Carey Brown
Bartenders:
• Piet Souris
• Al Hobbs
• salvin francis

# Another horse race

Ranch Hand
Posts: 1907
1
• Number of slices to send:
Optional 'thank-you' note:
In a horse race there are N horses.In how many ways they can finish the race?

Ranch Hand
Posts: 1923
• Number of slices to send:
Optional 'thank-you' note:
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.

Ranch Hand
Posts: 867
• Number of slices to send:
Optional 'thank-you' note:
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: 1907
1
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
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: 1907
1
• Number of slices to send:
Optional 'thank-you' note:
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: 1907
1
• Number of slices to send:
Optional 'thank-you' note:
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

Ranch Hand
Posts: 309
• Number of slices to send:
Optional 'thank-you' note:

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
• Number of slices to send:
Optional 'thank-you' note:

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 ]

 You showed up just in time for the waffles! And this tiny ad: Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton