Thread: Number of ways of selecting r letters?

1. Number of ways of selecting r letters?

If out of $\displaystyle 3n$ letters there are $\displaystyle n\ As,n\ Bs\ \mbox{and}\ n\ Cs$, show that the number of ways of selecting $\displaystyle r$ letters out of these is the same as selecting $\displaystyle (3n - r)$ letters out of them. If $\displaystyle n < r < 2n + 1$, show that the number of ways of selecting $\displaystyle r$ letters is given by $\displaystyle \frac{1}{2}(n + 1)(n + 2) + (r - n)(2n - r)$

2. Originally Posted by fardeen_gen
If out of $\displaystyle 3n$ letters there are $\displaystyle n\ As,n\ Bs\ \mbox{and}\ n\ Cs$, show that the number of ways of selecting $\displaystyle r$ letters out of these is the same as selecting $\displaystyle (3n - r)$ letters out of them. If $\displaystyle n < r < 2n + 1$, show that the number of ways of selecting $\displaystyle r$ letters is given by $\displaystyle \frac{1}{2}(n + 1)(n + 2) + (r - n)(2n - r)$
When you select $\displaystyle r$ letters, you leave behind $\displaystyle (3n-r)$ letters. Hence the number of ways of selecting $\displaystyle r$ letters is the same as the number of ways of leaving behind $\displaystyle (3n-r)$ letters, so $\displaystyle {3n\choose r}={3n\choose 3n-r}.$

Let $\displaystyle n_{\mathrm A},\,n_{\mathrm B}$ be the number of A’s and B’s respectively in the selection.

(1) $\displaystyle 0\le n_{\mathrm A}\le r-n-1$

When $\displaystyle n_{\mathrm A}=0,$ the minimum value of $\displaystyle n_{\mathrm B}$ is $\displaystyle r-n$ (since there are at most $\displaystyle n$ C’s) and the maximum is $\displaystyle n.$ Hence there are $\displaystyle 2n-r+1$ values for $\displaystyle n_{\mathrm B}$ when $\displaystyle n_{\mathrm A}=0.$ When $\displaystyle n_{\mathrm A}=1,$ $\displaystyle r-n-1\le n_{\mathrm B}\le n$ so $\displaystyle n_{\mathrm B}$ can have $\displaystyle 2n-r+2$ values. Continuing, we have that when $\displaystyle n_{\mathrm A}=3,$ $\displaystyle |n_{\mathrm B}|=2n-r+3;$ …. When $\displaystyle n_{\mathrm A}=r-n-1,$ $\displaystyle |n_{\mathrm B}|=2n-r+r-n=n.$

Hence the number of selections in which $\displaystyle 0\le n_{\mathrm A}\le r-n-1$ is $\displaystyle \sum_{k\,=\,1}^{r-n}(2n-r+k)=(2n-r)(r-n)+\frac12(r-n)(r-n+1).$

(2) $\displaystyle r-n\le n_{\mathrm A}\le n$

When $\displaystyle n_{\mathrm A}=r-n,$ $\displaystyle n_{\mathrm B}$ can range from 0 to $\displaystyle n,$ so $\displaystyle |n_{\mathrm B}|=n+1.$ When $\displaystyle n_{\mathrm A}=r-n+1,$ $\displaystyle 0\le n_{\mathrm B}le n-1$ so $\displaystyle |n_{\mathrm B}|=n.$ Hence: when $\displaystyle n_{\mathrm A}=r-n+2,$ $\displaystyle |n_{\mathrm B}|=n-1,$ …, when $\displaystyle n_{\mathrm A}=n,$ $\displaystyle |n_{\mathrm B}|=r-n+1.$

Hence the number of selections in which $\displaystyle r-n\le n_{\mathrm A}\le n$ is $\displaystyle \sum_{k\,=\,r-n+1}^{n+1}k=\frac12(2n-r+1)(r+2).$

Now if you add the results in (1) and (2), you should hopefully find that $\displaystyle \frac12(r-n)(r-n+1)+\frac12(2n-r+1)(r+2)$ simplifies to $\displaystyle \frac12(n+1)(n+2).$