Suppose $M=\{x_1,\ldots,x_{2n}\}$. How many ways can we partition this into two sets s.t. their cardinality equals $n$? Recall how to make a partition of a set.
My work so far:
This is a combinatorial problem, and I think this cooks down to how many ways you can choose $n$ elements out of $2n$ without overcounting and then split it up into two sets. With this reasoning I've checked that it works for $|M|\leq 6$, but I don't know if this is right in general. Expressing it mathematically we get: $$\dfrac{^{2n}\mathrm{C}_n}{2}=\binom{2n}{n}:2=\dfrac{2n!}{(2n-n)!n!2}=\dfrac{2n!}{(n!)^22}$$
Can someone explain why this is correct or incorrect?
Best Answer
First, choose $k$ items for first set. The remaining items will be in second set. Number of options of choosing $k$ items from $2n$ items is $\displaystyle {2n\choose k}$. Now we need to sum all the options, i.e $k$ between $1$ and $2n-1$, thus the number of ways is $$\sum_{k=1}^{2n-1}{2n\choose k}=\sum_{k=0}^{2n}{2n\choose k}-{2n\choose 0}-{2n\choose 2n}=2^{2n}-2=4^n-2$$
This number should be divided by $2$ as we are actually double counting the same partition, hence number of ways is $2^{2n-1}-1$.