Solution to puzzle 131: Horse race

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

S(n, k) for n = 1 to 8, k = 1 to n
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₈ denote the number of ways 8 horses can cross the finishing line, we obtain:

H₈	=
	= 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.

Remarks

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.

Solution to puzzle 131: Horse race

Remarks

Further reading