0
$\begingroup$

I am new to combinatorics and and struggling with the following questions.

If you have a set of n elements and you need to select two disjoint subsets containing k and r elements respectively. In how many ways can you select these subsets?

{the following text was added on 20 February 2017 after a request was received for more details and context}

Herewith an example of such a problem using n = 5 and k = r = 2: Consider a set S with 5 elements:
N = {1,2,3,4,5}

Calculating all the ways in which a subset of k (for example 2) elements can be selected from this set can be calculated using the standard formula for $${n \choose k}$$ and results in 10 ways.

If we for some reason need to count the number of ways in which two disjoint subsets (example 2 and 2) can be selected from set N I might use the following method. One way to think about this problem is as follows (Thank you drhab for your guidance on this):

I can first do a standard n choose k formula. 5 choose 2 = 10. Then I can re-do the formula for the second set using (5 - 2) choose 2 which gives 3. Finally I multiply the two results to get an answer of 10 * 3 = 30. This gives 30 ways to select 2 disjoint subsets of size 2 from a set of 5 elements.

Application of this logic to another problem as an example: How many ways can you choose two disjoint subsets from a set of 10 elements where the subsets have exactly 4 and 3 elements each? The answer (if the above logic is correct) is $${10 \choose 4} * {6 \choose 3}$$ which gives 210 * 20 = 4200 ways.

This feels correct to me ,however, I am not 100% sure. Please confirm whether it is.

$\endgroup$
  • 1
    $\begingroup$ Start by selecting $k$ elements of $n$ at the first round. Can you figure out how many possibilities there are? After that select $r$ elements of the $n-k$ elements that were not selected at the first round. $\endgroup$ – drhab Feb 19 '17 at 14:34
  • $\begingroup$ @drhab If $r=k$ then you double count. $\endgroup$ – ajotatxe Feb 19 '17 at 14:50
  • $\begingroup$ @ajotatxe You are correct (I overlooked that possibility). $\endgroup$ – drhab Feb 19 '17 at 14:55
0
$\begingroup$

First, select a subset with $r+k$ elements. There are $\binom n{r+k}$ ways to do this.

Then, if $r\neq k$, select a subset with $r$ elements from the previously chosen ones. There are $\binom{r+k}r$ ways to do this.

But if $r=k>0$ then we must divide by $2$ because choosing first $r$ elements is the same as choosing the other $r$ elements.

To sum up, the solution is $$\begin{cases} \frac12\binom n{2r}\binom{2r}r\text{ if }k=r>0 \\\binom{n}{r+k}\binom{r+k}r\text{ otherwise}\end{cases}$$

$\endgroup$
  • $\begingroup$ Thank you for the very fast response. I will go through the solution in detail and make comments. Thank you again! $\endgroup$ – Caspianstrider Feb 19 '17 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.