Solution
Photo Finish
Show the problem again
Five horses run a race. Every horse finishes, and any number of horses may tie with one another at any position. A result specifies, for each pair of horses, whether one finished ahead of the other or they tied. (For example "A and C tie for first, then B, then D and E tie" is one result.) How many different results are possible? Give an integer.
Worked solution
**Answer: 541.** A result is an ordered sequence of nonempty groups (the horses tied for first, then those tied for the next place, and so on): an ordered set partition. Let a(n) count them for n horses. Choosing the k horses in the first group leaves an arbitrary result for the remaining n − k: a(n) = Σ_{k=1..n} C(n, k) a(n − k), with a(0) = 1. So a(1) = 1, a(2) = 3, a(3) = 13, a(4) = 75, and a(5) = 5·75 + 10·13 + 10·3 + 5·1 + 1 = 541. These are the Fubini (ordered Bell) numbers; equivalently a(n) = Σ_k k! S(n, k) = 1 + 30 + 150 + 240 + 120 = 541 for n = 5.
Source: Classic exercise in wide circulation; no traceable original source. Statement written for AxiomIQ.