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.

No.
blocks
PartitionsNo.
partitions
Arrangements
per partition
Outcomes
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
11       
211      
3131     
41761    
511525101   
61319065151  
7163301350140211 
8112796617011050266281

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.


Remarks

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