8! Different possibilities if no two cars pass at the same time. Added to that are all the different possible ties, including ties for 2nd, 3rd etc.
If it were only 3 cars, it'd be 3! = 6 plus the ties. There are 6 possible 2 way ties for 1st and 6 for 2nd. There is one possible three way tie. That's 19 possibilities.
4 cars, we have 4! = 10 plus the 4 way tie, 4 3 way ties, 4 1 way ties, and 12 2 way ties, each multiplied by all the positions they can be in...
This does not seem like an easy problem.
Originally posted by AThousandYoungIt indeed is no simple one. I didn't check to see the other threads answer, but if it doesn't start iwth 5 then it is wrong.
8! Different possibilities if no two cars pass at the same time. Added to that are all the different possible ties, including ties for 2nd, 3rd etc.
If it were only 3 cars, it'd be 3! = 6 plus the ties. There are 6 possible 2 way ties for 1st and 6 for 2nd. There is one possible three way tie. That's 19 possibilities.
4 cars, we have 4! = 10 ...[text shortened]... multiplied by all the positions they can be in...
This does not seem like an easy problem.
Originally posted by forkedknight[i]the Sum from i=1 to 8 of ( C(n, i) * P(n-i+1, n-i+1) )
The link to the "horse race" thread contains my attempted solution. Not sure if anyone has taken a deeper look at it...
*edit* where:
C(n, k) is the number of combinations of size k from a set of size n, and
P(n, r) is the number of permutations of size r from a set of size n
*edit 2*
and n = 8
*edit 3*
and this only accounts for cases where there is only one tie, but that tie can be between any or all of the horses, so it's not a complete solution...
this should be a complete answer....
from my previous answer:
for i = 1:
P(8,8) = 8!
for i = 2:
for 1 tie: C(8, 2) * P(7, 7) = 8!/(6!2!) * 7!
for 2 ties: C(8,2) * C(6,2) * P(6,6) = 8!/(6!2!) * 6!/(4!2!) * 6!
for 3 ties: C(8,2) * C(6,2) * C(4,2) * P(5,5) = " * " * 4!/4 * 5!
for 4 ties: C(8,2) * C(6,2) * C(4,2) * C(2,2) * P(4,4) = " * " * " * 2 * 4!
for i = 3:
for 1 tie: C(8,3) * P(6,6) = 8!/(5!3!) * 6!
for 2 ties: C(8,3) * C(5,3) * P(4,4) = 8!/(5!3!) * 5!/(3!2!) * 4!
for i = 4:
for 1 ties C(8,4) * P(5,5) = 8!/(4!4!) * 5!
for 2 ties C(8,4) * C(4,4) * P(2,2) = 8!/(4!4!) * 1 * 2
for i = 5:
only 1 tie possible: C(8,5) * P(4,4) = 8!/(3!5!) * 4!
for i = 6:
" " " ": C(8,6) * P(3,3) = 8!/(6!2!) * 6
for i = 7:
" " " ": C(8,7) * P(2,2) = 16
for i = 8: 1
Therefore, the total is:
1 + 16 + 8!/(6!2!) * 6 + 8!/(3!5!) * 4! + 8!/(4!4!) * 5 * 2 +
8!/(4!4!) * 5! + 8!/(5!3!) * 5!/(3!2!) * 4! + 8!/(5!3!) * 6! +
8!/(6!2!) * 6!/(5!2!) * 4!/4 * 2 * 4! +
8!/(6!2!) * 6!/(4!2!) * 4!/4 * 5! +
8!/(6!2!) * 6!/(4!2!) * 6! + 8!/(6!2!) * 7! + 8!
*edit* fixed errors
Thread 94066
OK, I have an answer for this one, but first the approach.
The possibility of ties in any number of ways complicates calculations greatly, and so the first step is to list all possible kinds of car groupings first, where a "group" of cars are all the cars that tied for a particular position. The actual position tied for does not matter at this point, but will be considered later.
No ties is one possibility, while an eight-way tie is the opposite possibility. A three-way tie and a two-way tie is also a possibility.
After these are listed out, I then consider each one separately, counting the total number of ways the cars could be grouped and multiplying it by the number of orders the groups could finish, and accounting for duplications based on several groups being the same size.
After calaculating this for every possible scenario, I then add up the number of possibilities.
My answer was 545,835 ways broken down like this.
* 8-way tie - 1
* 7-way tie - 16
* 6-way tie and 2-way tie - 56
* 6-way tie - 168
* 5-way tie and 3-way tie - 112
* 5-way tie and 2-way tie - 1,008
* 5-way tie - 1,344
* 2 4-way ties - 70
* 4-way tie and 3-way tie - 1,680
* 4-way tie and 2 2-way ties - 1,260
* 4-way tie and 2-way tie - 10,080
* 4-way tie - 8,400
* 2 3-way ties and 2-way tie - 1,680
* 2 3-way ties - 6,720
* 3-way tie and 2 2-way ties - 20,160
* 3-way tie and 2-way tie - 67,200
* 3-way tie - 40,320
* 4 2-way ties - 2,520
* 3 2-way ties - 50,400
* 2 2-way ties - 151,200
* 2-way tie - 141,120
* No ties - 40,320
GRAND TOTAL - 545,835 ways to finish..
Feel free to analyze and correct any mistakes above.