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

We begin by considering fewer horses. We then develop a systematic way of counting the possible outcomes.

Consider the case of four horses. The horses may finish in 1, 2, 3, or 4 blocks. Labeling the horses a, b, c, d, one example of three blocks is: (a) (b) (c, d). This means that horses c and d have tied, and that horses a, b, and (c, d) have finished separately.

Note further that the three blocks -- (a), (b), (c, d) -- may be arranged in 3! = 6 ways. Clearly this is true of any partition that consists of three blocks.

The table below shows, for each number of blocks, the possible partitions and their number, the number of arrangements per partition, and the number of outcomes.

No. blocks | Partitions | No. partitions | Arrangements per partition | Outcomes |
---|---|---|---|---|

1 | (a, b, c, d) | 1 | 1! | 1 |

2 | (a) (b, c, d), (b) (a, c, d), (c) (a, b, d), (d) (a, b, c), (a, b) (c, d), (a, c) (b, d), (a, d) (b, c) | 7 | 2! | 14 |

3 | (a) (b) (c, d), (a) (c) (b, d), (a) (d) (b, c), (b) (c) (a, d), (b) (d) (a, c), (c) (d) (a, b) | 6 | 3! | 36 |

4 | (a) (b) (c) (d) | 1 | 4! | 24 |

Hence, counting ties, four horses can cross the finishing line in 1 + 14 + 36 + 24 = 75 ways.

To apply this approach to more horses we need a way to easily calculate the number of ways n horses can cross the finishing line in k blocks. We will develop a recurrence relation.

Let S(n, k) denote the number of ways n horses can cross the finishing line in k blocks. Suppose we add another horse, so that there are now have n + 1 horses that finish in k blocks. Then there are two mutually exclusive cases, which encompass all possibilities:

- The extra horse is alone in a block; i.e., it does not tie with any other horses. Then the other n horses must comprise k − 1 blocks. This can be done in S(n, k − 1) ways.
- The extra horse is in one of the k blocks. For each block, this may be done in S(n, k) ways.

We conclude that, for n > k, S(n + 1, k) = S(n, k − 1) + kS(n, k).

Using this recurrence relation, together with the initial conditions, S(n, 1) = S(n, n) = 1, we can determine S(8, 1), S(8, 2), ..., S(8, 8).

n\k | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|

1 | 1 | |||||||

2 | 1 | 1 | ||||||

3 | 1 | 3 | 1 | |||||

4 | 1 | 7 | 6 | 1 | ||||

5 | 1 | 15 | 25 | 10 | 1 | |||

6 | 1 | 31 | 90 | 65 | 15 | 1 | ||

7 | 1 | 63 | 301 | 350 | 140 | 21 | 1 | |

8 | 1 | 127 | 966 | 1701 | 1050 | 266 | 28 | 1 |

Letting H_{8} denote the number of ways 8 horses can cross the finishing line, we obtain:

H_{8} | = |

= 1×1! + 127×2! + 966×3! + 1701×4! + 1050×5! + 266×6! + 28×7! + 1×8! | |

= 545835. |

Therefore, counting ties, eight horses can cross the finishing line in 545835 ways.

The numbers {H_{n}} = 1, 3, 13, 75, 541, 4683, 47293, 545835, ... are known as ordered Bell numbers. They appear in many combinatorial guises; see for example *Combination Lock*, below.

- Stirling Numbers of the Second Kind
- Online Encyclopedia of Integer Sequences: A000670 and A001571
- Combination Lock
- Bell Numbers
- An Introduction to Mathematical Methods in Combinatorics

Source: Traditional