Suggested languages for you:

Americas

Europe

Q. 1.10

Expert-verifiedFound in: Page 17

Book edition
9th

Author(s)
Sheldon M. Ross

Pages
432 pages

ISBN
9780321794772

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 role="math" localid="1647945358534" $\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 role="math" localid="1647945372759" $\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 role="math" localid="1647945385288" $n\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$ possible choices.

(d) Conclude from parts (a), (b), and (c) that role="math" localid="1647945400273" $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).

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

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 localid="1647947695401" ${}^{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$.

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 role="math" localid="1647948253033" ${}^{n}C_{k-1}$ways $=\left(\begin{array}{c}n\\ k-1\end{array}\right)$ways.

The left number of persons will be role="math" localid="1647948086924" $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)$.

Out of $n$ persons, one can be selected as chairperson in role="math" localid="1647948578979" ${}^{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)$.

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 role="math" localid="1647950480646" $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)$

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

94% of StudySmarter users get better grades.

Sign up for free