Number of balanced partitions of a set

Question

Question:

A balanced bipartition of set $X$ splits $X$ into two parts $A$ and $B$ so that the sizes of $A$ and $B$ differ by at most $1$. In particular, when $X$ is even, $|A| = |B| = \frac{|X|}{2}$; when $|X|$ is odd, $|A| = |B|—1 = \lfloor |X|/2\rfloor$. We refer to the bipartition as $A \cup B$. For example, $\{b, e\} \cup \{a, c,d\}$ and $\{a,c\} \cup \{b, d, e\}$ are two different balanced bipartitions of {a,b,c,d,e}. On the other hand, we treat $\{a,b\} \cup \{c,d\}$ and $\{c,d\} \cup \{a,b\}$ as the same bipartition of $\{a, b, c,d\}$.

Solution:

• For $|X| = 2$ we have $\{1\}\cup\{2\}$

• For $|X| = 3$ we have $\{1,2\}\cup\{3\}$, $\{1,3\}\cup\{2\}$, $\{2,3\}\cup\{1\}$

• For $|X| = 4$ we have $\{1,2\}\cup\{3,4\}$, $\{1,4\}\cup\{2,3\}$, $\{1,3\}\cup\{2,4\}$

My thinking is the number of ways are:

• If $X$ is even then $\frac{\binom{X}{\frac{X}{2}}}{2}$
• If $X$ is odd then $\binom{X}{\lfloor \frac{X}{2} \rfloor}$

But I am unsure if this is correct or how to prove it.

Answer 1

Yes, your answers are correct.

Suppose $|X|$ is even. To obtain a balanced partition of $X$, we can choose a subset $A$ of $X$ of size $\frac{|X|}{2}$, at which point $A$ and its complement $X -A$ form a balanced partition of $X$. Furthermore, note that all balanced partitions of $X$ are of the form $A$, $X-A$ with $|A| = |X-A| = \frac{|X|}{2},$ so this obtains all balanced partitions.

There are $\binom{|X|}{\frac{|X|}{2}}$ ways of choosing such an $A$. But note that choosing $A$ first and choosing $X-A$ first give the same pair $A, X-A$, so we have double counted. Therefore, the number of balanced partitions is $$\frac{\binom{|X|}{\frac{|X|}{2}}}{2},$$ which is what you got.

Now, suppose $|X|$ is odd. Any balanced partition of $X$ is of the form $A, X-A$, where $|A| +1 = |X-A|$, and thus $|A| = \left\lfloor\frac{|X|}{2}\right\rfloor$. So, to obtain all balanced partitions of $X$, we simply need to calculate the number of ways of choosing a subset $A$ of $X$ with size $\left\lfloor\frac{|X|}{2}\right\rfloor$, which is $$\binom{|X|}{\left\lfloor\frac{|X|}{2}\right\rfloor},$$ which is what you got.

Note that the reason we don't double count in the $|X|$ odd case is because there is an asymmetry: one of the sets in the balanced partition has size one smaller than the other, so we can't reverse their roles and obtain the same partition as we can in the even case.