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.
Best Answer
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}$$