Skip to main content.

Solution to puzzle 131: Horse race

Skip restatement of puzzle.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.

per partition
1(a, b, c, d)11!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)72!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)63!36
4(a) (b) (c) (d)14!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:

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  1234567 8

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

H8 = Sum from k = 1 to 8 of S(8, k) times k factorial
 = 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 {Hn} = 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.

Further reading

  1. Stirling Numbers of the Second Kind
  2. Online Encyclopedia of Integer Sequences: A000670 and A001571
  3. Combination Lock
  4. Bell Numbers
  5. (Adobe) Portable Document Format An Introduction to Mathematical Methods in Combinatorics

Source: Traditional

Back to top