Results 1 to 6 of 6

Math Help - Combinatorics problem

  1. #1
    Newbie
    Joined
    Mar 2008
    Posts
    9

    Combinatorics problem

    How many ways are there first to pick a subset of n numbers from 50 distinct numbers, and next pick a second subset of k numbers such that each number in the first subset is less than each number in the second subset
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by bulldog106 View Post
    How many ways are there first to pick a subset of n numbers from 50 distinct numbers, and next pick a second subset of k numbers such that each number in the first subset is less than each number in the second subset
    Well, what have you tried? Please show some effort.

    Hint: Fix the least element of the k-subset.

    (Edit: I originally switched n and k due to misreading the problem.)
    Last edited by undefined; October 10th 2010 at 12:41 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2008
    Posts
    9
    Quote Originally Posted by undefined View Post
    Well, what have you tried? Please show some effort.

    Hint: Fix the least element of the n-subset.
    First choose n numbers from 50 C(n+50-1,n) ways. Then after determining the minimum number, choose k numbers C(k + (numbers less than k) -1,k)

    How do I determine the minimum number in the first subset?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by bulldog106 View Post
    First choose n numbers from 50 C(n+50-1,n) ways. Then after determining the minimum number, choose k numbers C(k + (numbers less than k) -1,k)

    How do I determine the minimum number in the first subset?
    I will use some new letters to discuss general counting results, to avoid confusion.

    The number of ways to select v elements from a set of u elements is simply \binom{u}{v}, evidenced by the fact that it's acceptable to say out loud "u choose v". What you wrote is the number of multisets of cardinality v whose elements belong to a set with u (distinct) elements, \binom{u+v-1}{v}. From the wording of the problem, we need \binom{u}{v}.

    So, obviously if n+k>50 then the answer is 0. Assume n+k is less than or equal to 50. We can also assume n and k are positive, and if need be consider the cases n=0 or k=0 as special (trivial) cases.

    Assume for simplicity that the set with 50 elements is {1,...,50}.

    Then the least element of the k-subset can range from n+1 to 50-k+1.

    Fix the least element of the k-subset and name it i. For the k-subset, we have k-1 elements remaining, to be chosen from 50-i elements. For the n-subset, we have n elements to be chosen from i-1 elements.

    Then take the sum as i goes from n+1 to 50-k+1.

    (Edit: Sorry, originally I had n and k switched throughout, due to misreading the problem.)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by bulldog106 View Post
    How many ways are there first to pick a subset of n numbers from 50 distinct numbers, and next pick a second subset of k numbers such that each number in the first subset is less than each number in the second subset
    Isn't this effectively the same as selecting n+k numbers out of the set of 50?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by awkward View Post
    Isn't this effectively the same as selecting n+k numbers out of the set of 50?
    Haha, so it is!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. problem in combinatorics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 21st 2011, 09:23 AM
  2. Help with combinatorics problem
    Posted in the Advanced Statistics Forum
    Replies: 5
    Last Post: December 7th 2010, 04:35 PM
  3. a combinatorics problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 23rd 2010, 04:39 AM
  4. Combinatorics problem
    Posted in the Statistics Forum
    Replies: 6
    Last Post: November 12th 2009, 08:05 AM
  5. Combinatorics Problem
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: March 5th 2008, 09:29 AM

Search Tags


/mathhelpforum @mathhelpforum