2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You could rephrase this answer: Our set is determined by its intersection with {1,..n} which is an arbitrary element of the powerset, 2^n. $\endgroup$ – Jacob Wakem Jun 29 '16 at 22:55
  • $\begingroup$ Actually I don't think it could be rephrased like that, not exactly anyway. However I encourage you to write an answer based on powersets, although bearing in mind that the question asker may not be familiar with the concept so may need a little bit of introduction to it. $\endgroup$ – Joffan Jun 29 '16 at 23:15
0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Do you think this is a more conceptually satisfying proof than the others? I cannot comprehend parts of this one. $\endgroup$ – Jacob Wakem Jun 30 '16 at 4:21
-1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.