Q. 1.10 - A First Course in Probability

Question

From a group of $n$ people, suppose that we want to choose a committee of k, $k\le n$, one of whom is to be designated as chairperson.

(a) By focusing first on the choice of the committee and then on the choice of the chair, argue that there are $\left(\begin{array}{c}n\\ k\end{array}\right)k$ possible choices.

(b) By focusing first on the choice of the non-chair committee members and then on the choice of the chair, argue that there are $\left(\begin{array}{c}n\\ k-1\end{array}\right)\left(n-k+1\right)$ possible choices.

(c) By focusing first on the choice of the chair and then on the choice of the other committee members, argue that

there are $n\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$ possible choices.

(d) Conclude from parts (a), (b), and (c) that $k\left(\begin{array}{c}n\\ k\end{array}\right)=\left(n-k+1\right)\left(\begin{array}{c}n\\ k-1\end{array}\right)=n\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$.

(e) Use the factorial definition of $\left(\begin{array}{c}m\\ r\end{array}\right)$ to verify the identity in part (d).

Step-by-Step Solution

Answer

(a) The possible number of choices are $\left(\begin{array}{c}n\\ k\end{array}\right)k$

(b) The possible number of choices are $\left(\begin{array}{c}n\\ k-1\end{array}\right)\left(n-k+1\right)$

(c) The possible number of choices are $n\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$

(d) It is proved that $k\left(\begin{array}{c}n\\ k\end{array}\right)=\left(n-k+1\right)\left(\begin{array}{c}n\\ k-1\end{array}\right)=n\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$

(e) It is proved that $k\left(\begin{array}{c}n\\ k\end{array}\right)=\left(n-k+1\right)\left(\begin{array}{c}n\\ k-1\end{array}\right)=n\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$

Part (a) Step 1. Find the possible number of choices.

Total no. of persons $=n$

No. of persons to be chosen for committee $=k$

So, the number of members for the committee can be chosen in ${}^{n}C_k$ ways = $\left(\begin{array}{c}n\\ k\end{array}\right)$ways

Out of $k$ members, one can be selected as chairperson in ${}^{k}C_1$ ways = $k$ ways

Therefore, total no. of ways are $\left(\begin{array}{c}n\\ k\end{array}\right)k$.

Part (b) Step 1. Find the possible number of choices.

Out of $k$ members, $1$ member will be the chair person. So, the non-chair members will be $k-1$.

So, non-chair members can be selected out of $n$ members in ${}^{n}C_{k-1}$ways $=\left(\begin{array}{c}n\\ k-1\end{array}\right)$ways.

The left number of persons will be $n-(k-1)=n-k+1$

Out of the left members, one can be selected as chairperson in ${}^{n-k+1}C_1$ ways $=n-k+1$ ways.

Therefore, total no. of ways are $\left(\begin{array}{c}n\\ k-1\end{array}\right)\left(n-k+1\right)$.

Part (c) Step 1. Find the possible number of choices.

Out of $n$ persons, one can be selected as chairperson in ${}^{n}C_1$ ways $=n$ ways.

The remaining no. of people will be $=n-1$

The number of non-chair members of the committee will be $=k-1$

So, non-chair members can be selected out of $n-1$ members in ${}^{n-1}C_{k-1}$ways = $\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$ways

Therefore, total no. of ways are $n\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$.

Part (d) Step 1. Give conclusion.

In all the above parts, (a), (b) and (c), we have found the ways in which we could select $k$ committee members out of the group of $n$ persons and one chair person of the committee.

Therefore, the total number of ways will be equal.

Hence, it is proved that  $k\left(\begin{array}{c}n\\ k\end{array}\right)=\left(n-k+1\right)\left(\begin{array}{c}n\\ k-1\end{array}\right)=n\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$

Part (e) Step 1. Verify the identity.

As per the factorial definition, $\left(\begin{array}{c}m\\ r\end{array}\right)=\frac{m!}{r!(m-r)!}$.

Therefore,

$k\left(\begin{array}{c}n\\ k\end{array}\right)=k\times \frac{n!}{k!(n-k)!}=k\times \frac{n!}{k\times (k-1)!(n-k)!}=\frac{n!}{(k-1)!(n-k)!}$................ (1)

$\left(n-k+1\right)\left(\begin{array}{c}n\\ k-1\end{array}\right)=\left(n-k+1\right)\times \frac{n!}{(k-1)!(n-k+1)!}=\left(n-k+1\right)\times \frac{n!}{(k-1)!(n-k+1)\times (n-k)!}=\frac{n!}{(k-1)!(n-k)!}$............ (2)

$n\left(\begin{array}{c}n-1\\ k-1\end{array}\right)=n\times \frac{(n-1)!}{(k-1)!(n-1-k+1)!}=\frac{n\times (n-1)!}{(k-1)!(n-k)!}=\frac{n!}{(k-1)!(n-k)!}$............... (3)

As (1) = (2) = (3)

Therefore, it is proved that $k\left(\begin{array}{c}n\\ k\end{array}\right)=\left(n-k+1\right)\left(\begin{array}{c}n\\ k-1\end{array}\right)=n\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$