In how many ways can you select two disjoint subsets from the an n-set $\{x_1, x_2,…,x_n\}$?
[Math] Number of two disjoint subsets from the an n-set $\{x_1, x_2,…,x_n\}$.
combinatorics
Related Solutions
As the other answers have stated, if you want to partition $A$ into pairwise-disjoint sets $A_1, A_2, ..., A_t$, each of size $r$, there are $\binom{rt}{\underbrace{r,r,...,r}_{t \text{ times}}} = \frac{(rt)!}{(r!)^t}$.
One way to see where this formula comes from is to imagine ordering all $rt$ elements ($(rt)!$ possibilities), and then taking the first $r$ to make the first set, the second $r$ to make the second set, and so on, until the last ($t$th) set of $r$ elements form the final set. However, the relative order of the elements in each set is irrelevant, so we should divide through by a factor of $r!$ for each of the $t$ sets.
Note that in this answer, the sets themselves are ordered - we have a first set $A_1$, a second set $A_2$, and so on, until a $t$th set $A_t$. If you do not care about the order of the sets, then you should further divide by the $t!$ ways there are of ordering the sets, which would give an answer of $\frac{(rt)!}{(r!)^t t!}$.
Finally, the asymptotic analysis will depend on how our parameters behave. Note that Stirling's Approximation gives $n! = (1 + o(1)) \sqrt{ 2 \pi n} \left( \frac{n}{e} \right)^n$ when $n \rightarrow \infty$. If, however, $n$ is fixed, then one must use $n!$ in asymptotic estimates ($n!$ is just a constant).
Hence, if $r$ is fixed and $t \rightarrow \infty$, $$ \binom{rt}{r, r, ..., r} = \frac{(rt)!}{(r!)^t} = \frac{ (1 + o(1)) \sqrt{2 \pi rt} \left( \frac{rt}{e} \right)^{rt} }{ (r!)^t} = (1 + o(1)) \sqrt{ 2 \pi rt} \left( \frac{r^r t^r}{r! e^r} \right)^t. $$
If $r$ tends to infinity as well, then we can also estimate the $r!$ in the above expression, giving $$ \binom{rt}{r, r, ..., r} = (1 + o(1)) \sqrt{2 \pi rt} \left( \frac{t^r}{( 1 + o(1)) \sqrt{ 2 \pi r} } \right)^t = \left( \frac{(1 +o(1)) t^r}{ \sqrt{ 2 \pi r} } \right)^t, $$ since the $\sqrt{2 \pi rt}$ is insignificant compared to $t^{rt}$.
Note that the latter estimate is valid even when $r \rightarrow \infty$ but $t$ is fixed, since then we still have $rt$ and $r$ tending to infinity, and hence our use of Stirling's Approximation is valid. In this case, though, since $(1 + o(1))^t = (1 + o(1))$, we can take the error term from inside the parentheses outside and get the sharper expression $(1 + o(1)) \sqrt{2 \pi r t } \left( \frac{t^r}{\sqrt{2 \pi r}} \right)^t$.
Finally, if the order of the sets is unimportant, then you should divide all of the above estimates by $t!$, which you can approximate by $\sqrt{2 \pi t} \left( \frac{t}{e} \right)^t$ when $t \rightarrow \infty$.
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}$$
Best Answer
We are essentially partitioning our original set $X$ into three pieces: those in $A$, those in $B$, and those in neither set. Suppose $|A|=k$. How many ways are there to choose $B$? Of the $n-k$ items remaining, there are $2^{n-k}$ possible subsets to choose from. And there are ${n\choose k}$ ways to choose $A$ with $|A|=k$. So the total number of possibilities is
$$\frac12\sum_{k=0}^n{n\choose k}2^{n-k}+\frac12,$$
where the factor $1/2$ accounts for the fact that except in the case $A=B=\emptyset$ swapping $A$ and $B$ amounts to the same choice (assuming that the two sets are not distinguished, it is not clear from your wording if this is the case).
Alternatively, as suggested by Qidi we can go elementwise, indicating for each element if it is in $A$, $B$ or neither, and this yields the answer $\frac123^n+\frac12$. So in fact this gives a combinatorial proof of $\sum_{k=0}^n{n\choose k}2^{n-k}=3^n$ (which can also be derived by the binomial formula on $(1+2)^n=\sum_{k=0}^n{n\choose k}1^k2^{n-k}$).