Begin by considering fewer horses. 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. Determine the number of ways n horses can cross the finishing line in 1, 2, 3, and 4 blocks.
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.
Finally, develop a recurrence relation to facilitate the calculation of S(n, k) = number of ways n horses can cross the finishing line in k blocks.