Car Race

In how many ways, counting ties, can eight cars cross the finishing line?

(For example, two cars, A and B, can finish in three ways: A wins, B wins, A and B tie.)

Originally posted by uzless
In how many ways, counting ties, can eight cars cross the finishing line?

(For example, two cars, A and B, can finish in three ways: A wins, B wins, A and B tie.)

This makes me think of horses.

Originally posted by heinzkat
This makes me think of horses.

http://www.redhotpawn.com/board/showthread.php?subject=Horse_race&threadid=94066

Originally posted by heinzkat
http://www.redhotpawn.com/board/showthread.php?subject=Horse_race&threadid=94066

Ya, but this one is about cars damn it!

Originally posted by uzless
Ya, but this one is about cars damn it!

...with horse powers...

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.

The link to the "horse race" thread contains my attempted solution. Not sure if anyone has taken a deeper look at it...

Originally posted by AThousandYoung
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.

It 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.

Originally posted by forkedknight
The link to the "horse race" thread contains my attempted solution. Not sure if anyone has taken a deeper look at it...

[i]the Sum from i=1 to 8 of ( C(n, i) * P(n-i+1, n-i+1) )

*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.