Results 1 to 2 of 2

Math Help - 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 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)
    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 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).
    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: December 14th 2011, 07:39 AM
  2. number of arrangements of letters ....
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 31st 2009, 10:43 PM
  3. Replies: 4
    Last Post: April 10th 2009, 02:03 PM
  4. Replies: 10
    Last Post: April 8th 2009, 11:56 AM
  5. number of ways
    Posted in the Statistics Forum
    Replies: 2
    Last Post: April 19th 2008, 02:54 PM

Search Tags


/mathhelpforum @mathhelpforum