1
$\begingroup$

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).

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.