Permutations of race positions Recently, I got this math question:

Alice, Bob, Caroline, and Derek are competing on a 400 m run.
a) How many different ways are there for them to arrive if participants can have joint places?
b) Is there a way to generalize this mathematically?

I started on a) then got the number 75 after laboring for hours, but I still don't know how to start on b).
I made a table of different possibilities if $n$ is the number of participants and $P(n)$ is the function to get the number of arrangements of the participants:




$n$
$P(n)$




0
1


1
1


2
3


3
13


4
75




but I still can't seem to generalise this (even though I keep getting super close).
Could you please help me?  I've been thinking about this for hours, but I can't get it...
 A: 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.
A: 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.
