0
$\begingroup$

Consider X = P({1 2 3 4}) i.e. power set of a set of 4 numbers.

There are 4 sets containing the elements {1 2}:

{1 2 3 4}
{1 2 3}
{1 2 4}
{1 2}

There are 6 sets containing the elements {1 2} OR {1 3}:

{1 2 3 4}
{1 2 3}
{1 2 4}
{1 3 4}
{1 2}
{1 3}

Is there a formula to calculate this? Just the count of such sets is sufficient but a way to get the sets is nice too. Thank you!

$\endgroup$
2
$\begingroup$

If you want to count the subsets of $\{1,\ldots, n\}$ that contain one of two pairs $\{a,b\}$ or $\{c,d\}$ this can be counted as $$n_1 + n_2 - n_{1 \land 2}$$

where I denote by $n_1$ the number of subsets that contain the first pair, $n_2$ the number of subsets that contain the second pair, and by $n_{1 \land 2}$ the number of sets that contain both.

It's easy to see that $n_1 = n_2 = 2^{n-2}$ as one pair must be in the subset and all other points have a two-way choice of being in the set of not. Suppose $|\{a,b\} \cup \{c,d\}|=k$, ($k=3$ if the pairs overlap, $k=4$ of they don't), then a similar argument gives $n_{1 \land 2}=2^{n-k}$. So the number you want is

$$2^{n-1} - 2^{n-|\{a,b\} \cup \{c,d\}|} $$

which in your case, where $n=4$ and $\{1,2,3\}$ is the union comes down to $2^3 - 2^{1} = 6$ as we'd expect.

$\endgroup$
2
$\begingroup$

Given a set $X$ of $n$ elements we have $|2^X|=2^n$. To count the number of subsets containing the given $k\le n$ elements exclude them from the set and count the subsets of the remaining set to get $2^{n-k}$.

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