Race Problem counting

In a race there are n horses.In the race more than one horse may get the same position. For example, 2 horses can finish in 3 ways.

  1. Both first
  2. horse1 first and horse2 second
  3. horse2 first and horse1 second

In how many ways,the race can finish so that a particular horse can never be first.If f(n) is the number of ways, is there any recurrence relation to get f(n).

Solutions Collecting From Web of "Race Problem counting"

Let $g(h,p)$ be the number of ways that $h$ horses can be ordered in $p$ positions. Then consider introducing an extra horse: it go in one of the $p$ existing positions of $h-1$ horses or in one of the gaps between the positions or before or after all the $p-1$ positions of $h-1$ horses. This leads to the recurrence $$g(h,p)= kg(n-1,p)+kg(n-1,p-1)$$ starting at $g(1,p)=0$ except $g(1,1)=1$. This gives a table of numbers which are in fact factorials multiplied by Stirling numbers of the second kind.

So for $h$ horses, the number of possibilities is the sum of these, e.g. $\displaystyle G(h)=\sum_{p=1}^h g(h,p)$. These are called Fubini numbers or ordered Bell numbers.

But you want to exclude a particular horse from being first alone or equal first. The number of cases where it would be first alone among $h$ horses is equal to the total number of cases with $h-1$ horses and (assuming there is more than one horse) the number of cases where it would be equal first among $h$ horses is also equal to the total number of cases with $h-1$ horses. So subtract these from the total with $h$ horses to get $$f(h)=G(h)-2G(h-1)$$ and for the special case of $h=1$ see that obviously $f(1)=0$ since the single horse must come first.

Possible Outline: Let $N(n)$ be the number of possible positions for $n$ horses (not worrying about making sure that one doesn’t come in first). Define $N(0)=1$. Let’s start counting $N(1) = 1$ clearly. $N(2) = 3$ since both could tie for first, horse A could win and B lose, or B wins and A loses. $N(3) = {{3}\choose{0}}N(0) + {{3}\choose{1}}N(1) + {{3}\choose{2}}N(2)$ because we have that of the $n=3$ horses, we can rearrange the $k = 0, 1, 2$ horses that don’t win in $N(k)$ ways.. Continuing you will find that $$N(n) = \sum\limits_{k=0}^{n-1} {{n}\choose{k}} N(k).$$ Now, if you ask how many of those $N(n)$ arrangements have it so that horse A doesn’t win, it seems you will find $$f(n) = N(n) – 2N(n-1)$$ where $2N(n-1)$ is the number of ways where horse A does win. Indeed, there are $N(n-1)$ ways to arrange the $n-1$ horses that aren’t horse A if horse A is the unique winner, and there are $N(n-1)$ ways to arrange the horses that aren’t horse A if horse A is not the unique winner.

Let’s say there’re $n$ horses and we don’t want horse pony to be the first.

Let’s first define $g(k,n)$ which is the number of all possibilities for the $n$ horses to take positions, and they all got ranks from $1$ to $k$. $g(k,n)$ is exactly equal to $k^n – k\times (k-1)^n + \binom k 2 \times (k-2)^n – \dots = \sum_{i=0}^{k}{(-1)^i \binom k i (k-i)^n}$ by inclusion-exclusion principle.

Now the problem is easy. First order the other $n-1$ horses, and take the position of pony at last. If the other $n-1$ horses take rank from $1$ to $k$ their are $2k-1$ possible position for pony not to be on the first. Therefore, $f(n)=\sum_{k=1}^{n-1}{(2k-1)g(k,n-1)} = \sum_{k=1}^{n-1}{\Big( (2k-1)\sum_{i=0}^{k}{(-1)^i \binom {k} i (k-i)^{n-1}}\Big)}$