Q. 1.16 - A First Course in Probability

Question

Consider a tournament of $n$ contestants in which the outcome is an ordering of these contestants, with ties allowed. That is, the outcome partitions the players into groups, with the first group consisting of the players who tied for first place, the next group being those who tied for the next-best position, and so on. Let $N\left(n\right)$ denote the number of different possible outcomes. For instance, $N\left(2\right) = 3$, since, in a tournament with $2$ contestants, player $1$ could be uniquely first, player $2$ could be uniquely first, or they could tie for first.

(a) List all the possible outcomes when $n=3$.

(b) With $N\left(0\right)$ defined to equal $1$, argue without any computations, that $N\left(n\right)=\sum _{i=1}^n\left(\begin{array}{c}n\\ i\end{array}\right)N\left(n-i\right)$

Hint: How many outcomes are there in which $i$ players tie for last place?

(c) Show that the formula of part (b) is equivalent to the following: 

$N\left(n\right)=\sum _{i=1}^{n-1}\left(\begin{array}{c}n\\ i\end{array}\right)N\left(i\right)$

(d) Use the recursion to find N(3) and N(4).

Step-by-Step Solution

Answer

(a) All possible outcomes are $13$.

(b) $\sum _{i=1}^n\left(\begin{array}{c}n\\ i\end{array}\right)N\left(n-i\right)=1$.

(c) It is proved that $\sum _{i=1}^n\left(\begin{array}{c}n\\ i\end{array}\right)N\left(n-i\right)=\sum _{i=1}^{n-1}\left(\begin{array}{c}n\\ i\end{array}\right)N\left(i\right)$

(d) The value of $N\left(3\right)=13$ and $N\left(4\right)=75$.

Part (a) Step 1. Find the possible outcomes.

If $n=3$, it means there are three contestants, so the possible number of outcomes will be:

Player 1 could be uniquely first, that is $\left(3<2<1 \text{or} 2<3<1 \text{or} 2=3<1\right)=3$ 

Player 2 could be uniquely first, that is $\left(3<1<2 \text{or} 1<3<2 \text{or} 1=3<2\right)=3$

Player 3 could be uniquely first, that is $\left(2<1<3 \text{or} 1<2<3 \text{or} 2=1<3\right)=3$

Player 1 and 2 can be uniquely first, that is $\left( 3<1=2\right)=1$

Player 1 and 3 can be uniquely first, that is $\left(2<1=3\right)=1$

Player 2 and 3 can be uniquely first, that is $\left( 1<3=2\right)=1$

Player 1, 2 and 3 can be uniquely first, that is $\left( 1=2=3\right)=1$

Therefore, the possible outcomes are $=3+3+3+1+1+1+1=13$

Part (b) Step 1. Prove that N ( n ) = &#8721; i = 1 n n i N n - i .

It is given that $N\left(0\right)=1$...................... (1)

Assume that the possible ranking has $i (i=1,2,....,n)$ contestant's in the last place.

Let the last place be $i$.

The number of possible combinations of $n$ contestants in the last place is $\left(\begin{array}{c}n\\ i\end{array}\right)$, and from the remaining $(n-i)$ contestants remain to be ranked above and the number of possibilities for that is $N(n-i)$.

Hence, for every possible number of contestants in the last place, there are $N\left(n\right)$ possible rankings.

That is $N\left(n\right)=\sum _{i=1}^n\left(\begin{array}{c}n\\ i\end{array}\right)N\left(n-i\right)$.......... (2)

Substitute $i=n$ in equation (2)

$$\begin{gathered} N\left(n\right)=\left(\begin{array}{c}n\\ n\end{array}\right)N\left(n-n\right) \\ N\left(n\right)=\left(1\right)N\left(0\right) \end{gathered}$$

From equation 1, we have $N\left(0\right)=1$

So, $\left(1\right)N\left(0\right)=1\times 1$

$\Rightarrow N\left(n\right)=1$

Therefore, $\sum _{i=1}^n\left(\begin{array}{c}n\\ i\end{array}\right)N\left(n-i\right)=1$

Part (c) Step 1. Prove that &#8721; i = 1 n n i N n - i = &#8721; i = 1 n - 1 n i N i

Let $\underset{ i=1}{\overset{ n}{N\left(n\right)=\sum }}\left(\begin{array}{c}n\\ i\end{array}\right)N\left(n-i\right)=\sum _{i=1}^{n-1}\left(\begin{array}{c}n\\ i\end{array}\right)N\left(i\right)$

Now, $\sum _{i=1}^n\left(\begin{array}{c}n\\ i\end{array}\right)N\left(n-i\right)={}^{n}C_{1}N\left(n-1\right) + {}^{n}C_{2}N\left(n-2\right) + {}^{n}C_{n-1}N\left(n-n+1\right) + {}^{n}C_{n}N\left(n-n\right)$

$$\begin{gathered} =nN\left(n-1\right)+\frac{n!}{2!(n-2)!}N\left(n-2\right)+.......+\frac{n!}{(n-n+1)!(n-1)!}N\left(n-n+1\right)+\left(1\right)N\left(n-n\right) \\ =nN\left(n-1\right)+\frac{n(n-1)N\left(n-2\right)}{2!}+.......+nN\left(1\right)+N\left(0\right) \end{gathered}$$

As $N\left(0\right)=1$

So, $\sum _{i=1}^n\left(\begin{array}{c}n\\ i\end{array}\right)N\left(n-i\right)=nN\left(n-1\right)+\frac{n(n-1)N\left(n-2\right)}{2!}+.......+nN\left(1\right)+1$

Now, $\sum _{i=1}^{n-1}\left(\begin{array}{c}n\\ i\end{array}\right)N\left(i\right)={}^{n}C_{0}N\left(0\right) + {}^{n}C_{1}N\left(1\right) + {}^{n}C_{n-2}N\left(n-2\right) + {}^{n}C_{n-1}N\left(n-1\right)$

$$\begin{gathered} =1+nN\left(1\right)+\frac{n(n-1)}{2!}N\left(2\right)+.......+\frac{n(n-1)}{2!}N\left(n-2\right)+nN\left(n-1\right) \\ =nN\left(n-1\right)+\frac{n(n-1)N\left(n-2\right)}{2!}+.......+nN\left(1\right)+N\left(0\right) \end{gathered}$$

Therefore, it is proved that $\sum _{i=1}^n\left(\begin{array}{c}n\\ i\end{array}\right)N\left(n-i\right)=\sum _{i=1}^{n-1}\left(\begin{array}{c}n\\ i\end{array}\right)N\left(i\right)$

Part (d) Step 1. Find the value of N ( 3 ) .

We have, $N\left(n\right)=\sum _{i=1}^n\left(\begin{array}{c}n\\ i\end{array}\right)N\left(n-i\right)$

So, $N\left(3\right)=\sum _{i=1}^3\left(\begin{array}{c}3\\ i\end{array}\right)N\left(3-i\right)$

$$\begin{gathered} ={}^{3}C_{1}N\left(3-1\right)+{}^{3}C_{2}N\left(3-2\right)+{}^{3}C_{3}N\left(3-3\right) \\ =3N\left(2\right)+3N\left(1\right)+1N\left(0\right) \end{gathered}$$

It is given that, $N\left(0\right)=1, N\left(1\right)=1, N\left(2\right)=3$

So, $N\left(3\right)=3\left(3\right)+3\left(1\right)+1\left(1\right) = 9+3+1=13$.

Part (d) Step 2. Find the value of N ( 4 ) .

We have, $N\left(n\right)=\sum _{i=1}^n\left(\begin{array}{c}n\\ i\end{array}\right)N\left(n-i\right)$

So, $N\left(4\right)=\sum _{i=1}^4\left(\begin{array}{c}4\\ i\end{array}\right)N\left(4-i\right)$

$$\begin{gathered} ={}^{4}C_{1}N\left(4-1\right)+{}^{4}C_{2}N\left(4-2\right)+{}^{4}C_{3}N\left(4-3\right)+{}^{4}C_{4}N\left(4-4\right) \\ =4N\left(3\right)+6N\left(2\right)+4N\left(1\right)+1N\left(0\right) \end{gathered}$$

It is given that, $N\left(0\right)=1, N\left(1\right)=1, N\left(2\right)=3, N\left(3\right)=13$

So, $N\left(4\right)=4\left(13\right)+6\left(3\right)+4\left(1\right)+1\left(1\right) = 52+18+4+1=75$