# Number of ways of selecting r letters?

• May 25th 2009, 10:21 AM
fardeen_gen
Number of ways of selecting r letters?
If out of $3n$ letters there are $n\ As,n\ Bs\ \mbox{and}\ n\ Cs$, show that the number of ways of selecting $r$ letters out of these is the same as selecting $(3n - r)$ letters out of them. If $n < r < 2n + 1$, show that the number of ways of selecting $r$ letters is given by $\frac{1}{2}(n + 1)(n + 2) + (r - n)(2n - r)$
• May 25th 2009, 02:54 PM
TheAbstractionist
Quote:

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

When you select $r$ letters, you leave behind $(3n-r)$ letters. Hence the number of ways of selecting $r$ letters is the same as the number of ways of leaving behind $(3n-r)$ letters, so ${3n\choose r}={3n\choose 3n-r}.$

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

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

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

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

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

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

Hence the number of selections in which $r-n\le n_{\mathrm A}\le n$ is $\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 $\frac12(r-n)(r-n+1)+\frac12(2n-r+1)(r+2)$ simplifies to $\frac12(n+1)(n+2).$