Counting the number of subsets of a set of 2n elements satisfying some conditions.

Question

Let $X =\{v_1, v_2,\cdots, v_n, v_{n+1},\cdots, v_{2n}\}$ be a set of $2n$ elements. I want to find the number of subsets of $X$ with $n$ elements such that both $v_i$ and $v_{n+i} $ are not together in this subset.

I tried some small cases with $n=2,3,4$ and think it should be $2^n$ but I would like to prove it rigorously. I'm not sure how to use induction here. Is there a good combinatorial argument that can be used? Is my guess even correct?

Thank you.

Answer 1

You have set the requirement for subsets that do not contain both $v_i$ and $v_{n+i} $.

However, in order for such a subset to have $n$ elements, it is clear that it must contain one of these.

As such, every subset can be generated by combining all those choices between $v_i$ and $v_{n+i} $. Each of those choices is binary, and there are $n$ choices, giving a total of $2^n$ alternative subsets that meet the conditions.

Answer 2

Using inclusion-exclusion we obtain immediately

$$2^{2n} + \sum_{k=1}^n {n\choose k} (-1)^{k} 2^{2n-2k} = \sum_{k=0}^n {n\choose k} (-1)^{k} 2^{2n-2k} = (-1+4)^n \\ = 3^n.$$

Remark. This is for the case of the subsets not containing the forbidden pairs having any size. We now do the case of the subsets containing $n$ elements, with the same forbidden pairs.

Using inclusion-exclusion we once more obtain immediately

$${2n\choose n} + \sum_{k=1}^{\lfloor n/2\rfloor} {n\choose k} (-1)^{k} {2n-2k\choose n-2k} = \sum_{k=0}^{\lfloor n/2\rfloor} {n\choose k} (-1)^{k} {2n-2k\choose n-2k}.$$

There are several possibilities to evaluate this, one is to use the Egorychev method and introduce

$${2n-2k\choose n-2k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-2k+1}} (1+z)^{2n-2k} \; dz.$$

Observe that this vanishes when $2k\gt n$ so we may raise the upper limit of the sum to $n$, getting

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{2n} \sum_{k=0}^n {n\choose k} (-1)^k \frac{z^{2k}}{(1+z)^{2k}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{2n} \left(1-\frac{z^2}{(1+z)^2}\right)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+2z)^n \; dz = 2^n.$$

Answer 3

WLOG, $\{v_1,..v_2n\}=\{0,...,2n-1\}=2n$ (by the Von-Neumann ordinal convention of $k=\{0,..,k-1\}$).

Our chosen set is determined by its intersection with $n$ which is an arbitrarily chosen element of the powerset $P(n)$ with cardinality $2^n$.