Permutations and Combinations
9.0 Possible selections from $n$ distinct objects
9.0 Possible selections from $n$ distinct objects
- The number of selections from $n$ different objects, taking at least one is given by $$^n{C_1}{ + ^n}{C_2} + .........{ + ^n}{C_n} = {2^n} - 1$$
Proof: Let $n=1$, Thus $^1{C_1}$ is the only possibility. $$\begin{equation} \begin{aligned} = {\,^1}{C_1} \\ = 1 \\ = 2 - 1 \\ = {2^1} - 1 \\\end{aligned} \end{equation} $$
Let $n=2$,
$$\begin{equation} \begin{aligned} { = ^2}{C_1}{ + ^2}{C_2} \\ = 2 + 1 \\ = 3 \\ = 4 - 1 \\ = {2^2} - 1 \\\end{aligned} \end{equation} $$
Now let us assume this is true for all $n = k$,
Then, $$^k{C_1}{ + ^k}{C_2} + .........{ + ^k}{C_k} = {2^k} - 1$$
When $n= k + 1$
$$\begin{equation} \begin{aligned} = {\,^{k + 1}}{C_1}{ + ^{k + 1}}{C_2} + .........{ + ^{k + 1}}{C_{k + 1}} \\ = \,{\{ ^{k + 1}}{C_1}\} + {\{ ^{k + 1}}{C_2}\} + ......... + {\{ ^{k + 1}}{C_k}\} + {\{ ^{k + 1}}{C_{k + 1}}\} \\ = {\{ ^k}{C_1}{ + ^k}{C_0}\} + {\{ ^k}{C_2}{ + ^k}{C_1}\} + ......... + {\{ ^k}{C_k}{ + ^k}{C_{k - 1}}\} + {\{ ^k}{C_{k + 1}}{ + ^k}{C_k}\} \\\end{aligned} \end{equation} $$
Since, $$^{n + 1}{C_r}{ = ^n}{C_r}{ + ^n}{C_{r - 1}}$$
$$ = {\,^k}{C_0} + 2{\{ ^k}{C_1}{ + ^k}{C_2} + .........{ + ^k}{C_{k - 1}}{ + ^k}{C_k}\} { + ^k}{C_{k + 1}}$$
As, $^k{C_{k + 1}}$ is not defined, eliminating it we get,
$$ = 1 + 2{\{ ^k}{C_1}{ + ^k}{C_2} + .........{ + ^k}{C_{k - 1}}{ + ^k}{C_k}\} $$
Since, $$\begin{equation} \begin{aligned} { \Rightarrow ^n}{C_0} = 1 \\ \Rightarrow 1 + 2({2^k} - 1) \\\end{aligned} \end{equation} $$
Since, $$\begin{equation} \begin{aligned} ^k{C_1}{ + ^k}{C_2} + .........{ + ^k}{C_{k - 1}}{ + ^k}{C_k} = {2^k} - 1 \\ = 1 + {2.2^k} - 2 \\ = {2^{k + 1}} - 1 \\ = {2^n} - 1\quad {\text{where}}\quad n = k + 1 \\\end{aligned} \end{equation} $$
Thus, there are $\left( {{2^n} - 1} \right)$ selections possible.
Question 22. There are $20$ cookies in a box. Each of them are unique. In how many ways can you select atleast one?
What is the maximum number of ways you can select, if you need atleast two?
Solution: Number of ways of selecting atleast one, $$\begin{equation} \begin{aligned} { = ^{20}}{C_1}{ + ^{20}}{C_2} + .........{ + ^{20}}{C_{20}} \\ = {2^{20}} - 1 \\\end{aligned} \end{equation} $$
Ways of selecting atleast two = Ways of selecting at least one - ways of selecting one
$$\begin{equation} \begin{aligned} = {\,^{20}}{C_1}{ + ^{20}}{C_2} + .........{ + ^{20}}{C_{20}}{ - ^{20}}{C_1} \\ = {2^{20}} - 1 - \frac{{20!}}{{1!\left( {20 - 1} \right)!}} \\ = {2^{20}} - 1 - 20 \\ = {2^{20}} - 21 \\\end{aligned} \end{equation} $$
