1. Joined
    14 Dec '05
    Moves
    5692
    20 May '08 13:56
    In how many ways, counting ties, can eight horses cross the finishing line?

    (For example, two horses, A and B, can finish in three ways: A wins, B wins, A and B tie.)
  2. Standard memberwolfgang59
    howling mad
    In the den
    Joined
    09 Jun '07
    Moves
    45641
    20 May '08 16:271 edit
    8! is the wrong answer
  3. Standard memberforkedknight
    Defend the Universe
    127.0.0.1
    Joined
    18 Dec '03
    Moves
    16018
    20 May '08 20:113 edits
    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...
  4. Standard memberforkedknight
    Defend the Universe
    127.0.0.1
    Joined
    18 Dec '03
    Moves
    16018
    21 May '08 18:282 edits
    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
  5. Standard memberforkedknight
    Defend the Universe
    127.0.0.1
    Joined
    18 Dec '03
    Moves
    16018
    21 May '08 18:28
    I don't have time to simplify that; someone else can if they want...
  6. Standard memberforkedknight
    Defend the Universe
    127.0.0.1
    Joined
    18 Dec '03
    Moves
    16018
    21 May '08 18:32
    btw, i is the number of horses in each tie...
Back to Top