How many ways can you partition a set with $2n$ elements into two sets?

Question

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?

Answer 1

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$.

Answer 2

Each element goes in set $1$ or set $2$. We have two choices for each element, leading to $2^{2n}$ choices in total. We need to remove a factor of $2$ because we don't care about which partition is which (presumably), so $2^{2n-1}$. Then we need to remove the possibility of one of the partitions being empty. There's only one way to choose that, so the answer is $2^{2n-1}-1$.

To compare to Galc127's answer, this is: $$2^{2n-1} - 1 = (4^n - 2)/2$$

The factor of $2$ has been taken out because the two partitions are indistinguishable. With $m$ partitions, we would divide by $m!$ instead.

Answer 3

$M$ has $2^{2n}$ subsets and each subset $A\subseteq M$ induces a pair $\{A,A^c\}$.

This pair is a partition of $M$ if $A\notin\{\varnothing,M\}$, so at first sight there are $2^{2n}-2$ partitions of $M$ that have $2$ elements.

Now observe that the sets $A$ and $A^c$ induce the same pair.

Repairing this double counting we eventually find: $$\frac12(2^{2n}-2)=2^{2n-1}-1$$ partitions of $M$ that have two elements.

---

If you would be working under the (not mentioned) extra condition that both elements of the partition must have equal cardinality then we must look at pairs $\{A,A^c\}$ where $|A|=n$.

There are $\binom{2n}{n}$ to choose a subset $A\subset M$ with $|A|=n$ so at first sight there are $\binom{2n}{n}$ partitions of $M$ that have two elements with equal cardinality.

Again there is double counting so eventually we find: $$\frac12\binom{2n}{n}$$ partitions of $M$ that have two elements with equal probability.

Answer 4

Partition of Set of $2^{2n } $ elements in to two sets. It depends on the way you can write $ 2n $ as sum of two numbers. I don't see why one partition cant be empty. It is about making a subset of cardinality $k$, where $k$ can be $0 \, to (2n/2).$. $ \, \sum_{k=0}^n {2n \choose k}$

Answer 5

Call the sets $A,\,A^c:=M\backslash A$. Choose whether $x_1\in A$ etc. in $2^{2n}$ ways. The symmetry $A\to A^c$ halves this to $2^{2n-1}$. If you insist neither set be empty, the answer is $2^{2n-1}-1$.