0
$\begingroup$

How many elements in $(A \cup B \cup C \cup D \cup E)$ are only in two of these subsets?

I understand that for $(A \cup B \cup C \cup D)$ the answer is $|A \cap B| + |A \cap C| ... - 3|A \cap B \cap C| - 3|A \cap B \cap D| ... + 6|A \cap B \cap C \cap D|$

But I just can't figure out what determines the coefficents. My best guess is it would follow the same pattern, but the coefficients would go 1, 3, 6, 10?

Sorry this is kind of a noob question, I've just been stuck on this chapter of my discrete book for a while, and I can't find any help online.

$\endgroup$
3
  • $\begingroup$ What subsets are you looking at? ( $\endgroup$ Nov 20, 2017 at 19:22
  • $\begingroup$ The expression that you have looks quite a bit like the formula for the number of elements that are in exactly 2 subsets (which is a case of a generalized version of inclusion-exclusion). Is this what you are looking for? Just checking. $\endgroup$ Nov 20, 2017 at 19:27
  • $\begingroup$ @AirConditioner yes that's what I'm asking. And actually, just giving it a name helped me find some help finding the solution, so thank you! $\endgroup$
    – Zaya
    Nov 20, 2017 at 19:40

2 Answers 2

1
$\begingroup$

This is an application of a generalized inclusion-exclusion principle. (For a discussion/statement/proof, you can see the following.)

Demonstrate another way to solve the Inclusion–exclusion principle?

D'Antona-Rota generalized principle of inclusion & exclusion

$\endgroup$
0
$\begingroup$

Hint:

For $A\cup B \cup C$ you get $(|A\cap B| - |A\cap B\cap C|) + (|A\cap C| - |A\cap B\cap C|) + (|B\cap C|- |A\cap B \cap C|) = |A\cap B| + |A\cap C| + |B\cap C| - 3|A\cap B\cap C|$

For $A\cup B \cup C \cup D$ you get $\sum_{\{X,Y\}\subset\{A,B,C,D\}\text{ there are six of these}} (|X\cap Y| - (\sum_{Z\in \{A,B,C,D\}\setminus\{X,Y\}\text{ there are two of these}} |X\cap Y\cap Z|)+(|A\cap B\cap C\cap D|_{\text{ there is one of these}}) = $ the six $|A\cap B|, |A\cap C|$ etc... + each of the $|A\cap B\ \cap C|$ etc appear each in exact $3$ of the summands (that is, $A\cap B \cap C$ will be subtracted from each of the three: $A\cap B$, $A\cap C$ and $B \cap C$. or $3$ times total).. + $A\cap B\cap C\cap D$ appearing in each of the $6$ times.

So.... So that is where the coefficients come from.

So for $A\cup B \cup C \cup D \cup E$ you will have:

$10= {5 \choose 2}$ combinations of $X \cap Y$.

Each will substract some $X\cap Y\cap Z$. For each of the $X\cap Y$ there will be $3$ of these. (Example: for $A \cap B$ we will remove $A\cap B \cap C$ and $A\cap B \cap D$ and $A\cap B \cap E$; that is $3 = 5-2$ of them.) Of the ${5\choose 3} = 10$ combinations of $X\cap Y\cap Z$, $10*3= 30$ will be subtracted so each of them will be subtracted $\frac {30}{10} = 3$ times.

For each of the $X \cap Y$ you will subtract some of the $X\cap Y\cap Z\cap W$. There will but ${(5-2)\choose 2}={3\choose 2}= 3$ of these. (That is. For $A\cap B$ there will be $A\cap B \cap C\cap D$ or $A\cap B \cap C\cap E$ or $A\cap B \cap D\cap E$). So we will subtract $10*3=30$ of these 4-sects. There are ${5\choose 4} = 5$ of these 4-sects so each will be subtracted $\frac {30}4 = 6$ times.

And the $A\cap B \cap C \cap D \cap E$ will be subtracted $10$ times.

In general: TO find the elements in exactly $2$ of $n$ sets.

You will have ${n \choose 2}$ $A\cap B$ to consider.

For each of those you will have $n-2$ $A\cap B \cap C$ to subtract. That is ${n \choose 2}*(n-2)$ total so each of the $n \choose 3$ of the $A\cap B \cap C$ will each be subtracted $\frac {{n \choose 2}*(n-2)}{n\choose 3} = \frac {n!(n-3)!3!}{(n-2)!2!n!}(n-2)=3$

For each of the ${n \choose 2}$ $A\cap B$ that we consider there are ${n - 2\choose k}$ $A \cap B \cap .... \cap K$. That is ${n \choose 2}*{n - 2\choose k}$ so for each of the $n\choose k$ of the $A\cap B\cap ... K$ each will be subtracted /added $\frac {{n \choose 2}*{n - 2\choose k}}{n \choose k}={n-k \choose 2}$.

Basically. The coefficients for the elements of $n$ sets that occur in exactly $m$ sets will be ${n-k \choose m}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .