Let $S=\{x_1,\dots ,x_{2n}\}$. How many subsets of size $n$ are in $S$ such that $\forall1\le i\le n: x_i$ and $x_{n+i}$ are not in the same set.
I ran into this problem when thinking how many distinct clauses are required to calculate all boolean functions $f_i:\{0,1\}^n\to\{0,1\}$ in CNF form.
Obviously, without the said restriction, the answer is ${2n \choose n}$. However, I can't think of a way to count the subsets with the said restriction without double counting.
I'd appreciate any help or direction.
Your condition $\forall1\le i\le n: x_i$ and $x_{n+i}$ are not in the same set means exactly one of $x_i$ or $x_{n+i}$ is in the set.
Your answer is simply $2^n$, since for every $i$, you choose between $x_i$ and $x_{n+i}$.