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 ]