Permutations of race positions

Suppose there are $n$ racers. We consider the following cases:

• If there is one winner, there are $\binom{n}{1}$ ways to choose the winner and $P(n-1)$ ways to order the rest.

• If there are two (tied) winners, there are $\binom{n}{2}$ ways to choose the two winners, and $P(n-2)$ ways to order the rest

  $\vdots$

• If there are $n$ (tied) winners, there are $\binom{n}{n}$ ways to choose the $n$ winners, and $P(0)$ ways to order the rest.

So we get the recurrence relation $$P(n)=\sum_{k=1} ^n\binom{n}{k}P(n-k).$$ Starting with $P(0)=1$, you can use this formula to get all the values for $P(n)$. For example, for $P(5)$ (the smallest value that you haven't yet computed), we have

$$\begin{align*} P(5)&=\binom{5}{1}\times75+\binom{5}{2}\times13+\binom{5}{3}\times3\\ &\qquad+\binom{5}{4}\times1+\binom{5}{5}\times1\\ &=541. \end{align*}$$

The sequence $P(n)$ being described is called the ordered Bell numbers.

Say that you have $n$ contestants, and they finish in $k$ groups. There are $n\brace k$ ways to partition the $n$ contestants into $k$ non-empty sets, and the $k$ sets can be permuted in $k!$ different orders, so there are $k!{n\brace k}$ possible ways for the contestants to finish in $k$ groups. Here $n\brace k$ is a Stirling number of the second kind. Thus,

$$P(n)=\sum_{k=0}^nk!{n\brace k}\,.$$

(I include $k=0$ to cover the case $n=0$: ${0\brace 0}=1$, and ${n\brace 0}=0$ for $n\ge 1$.)

These are the so-called Fubini numbers, OEIS A000670; you’ll find many references at the link.