1. ## 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

2. Originally Posted by bulldog106
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.)

3. Originally Posted by undefined
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?

4. Originally Posted by bulldog106
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 $\displaystyle \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, $\displaystyle \binom{u+v-1}{v}$. From the wording of the problem, we need $\displaystyle \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.)

5. Originally Posted by bulldog106
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?

6. Originally Posted by awkward
Isn't this effectively the same as selecting n+k numbers out of the set of 50?
Haha, so it is!