Results 1 to 2 of 2

Thread: Number of ways of selecting r letters?

  1. #1
    Super Member fardeen_gen's Avatar
    Joined
    Jun 2008
    Posts
    539

    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)$
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by fardeen_gen View Post
    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).$
    Last edited by TheAbstractionist; May 25th 2009 at 04:19 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. number of ways ?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Dec 14th 2011, 07:39 AM
  2. number of arrangements of letters ....
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jul 31st 2009, 10:43 PM
  3. Replies: 4
    Last Post: Apr 10th 2009, 02:03 PM
  4. Replies: 10
    Last Post: Apr 8th 2009, 11:56 AM
  5. number of ways
    Posted in the Statistics Forum
    Replies: 2
    Last Post: Apr 19th 2008, 02:54 PM

Search Tags


/mathhelpforum @mathhelpforum