1
$\begingroup$

If $A$, $B$, and $C$ are finite sets then, the number of elements in EXACTLY ONE (i.e. at most one) of the sets $A$,$B$,$C$:$$n(A)+n(B)+n(C)-2 \times n(A \cap B)-2 \times n(A \cap C)-2 \times n(C \cap B) + 3 \times n(A \cap B \cap C)$$

I can derive the above through inclusion-exclusion, but would there be a general formula for $n$ finite sets?

$\endgroup$
  • 1
    $\begingroup$ thats not the inclusion exclusion since there is no 2 there? $\endgroup$ – james black May 4 at 6:42
  • 2
    $\begingroup$ @jamesblack Notice the OP says exactly one of the sets. $\endgroup$ – saulspatz May 4 at 6:56
  • 1
    $\begingroup$ @JeanMarie You are are overlooking the words "exactly one" $\endgroup$ – saulspatz May 4 at 6:57
  • $\begingroup$ Ah, yes, that makes a difference. $\endgroup$ – Graham Kemp May 4 at 7:00
  • $\begingroup$ @saulspatz You are right. Thanks ! $\endgroup$ – Jean Marie May 4 at 7:00
3
$\begingroup$

Suppose we have $n$ sets $A_1,A_2,\dots,A_n$. For $k=1,2,\dots,n$ define $$S_k=\sum|A_{n_1}\cap A_{n_2}\cap\cdots \cap A_{n_k}|,$$ where the sum is taken over all $k$-subsets $\{n_1,n_2,\dots,n_k\}\subseteq \{1,2,\dots,n\}$

I claim that the number of elements that occur in exactly one of the sets $A_1,A_2,\dots A_n$ is $$\sum_{k=1}^n(-1)^{k-1}kS_k\tag{1}$$ To see this, consider an element $x$ that occurs in exactly $m$ of the sets, where $1\leq m \leq n.$ If $m=1$, $x$ is counted exactly once in $S_1$ and nowhere else, so it is counted once by $(1).$ If $m>1$, then X occurs in ${m\choose k}$ of the terms in the definition of $S_k$ for $1\leq k\leq m$ and in none of the term when $k>m$. Therefore is is counted $$c(m)=\sum_{k=1}^m(-1)^{k-1}k{m\choose k}$$ times.

To evaluate $c(m)$ write $$(1-x)^m=\sum_{k=0}^m(-1)^k{m\choose k}x^k$$ by the binomial theorem. Differentiate both sides to get $$ -m(1-x)^{m-1}=\sum_{k=1}^m(-1)^k{m\choose k}kx^{k-1}$$

Substitute $x=1$ to get get $c(m)=0.$ Thus $(1)$ counts elements that occur in exactly one of the sets once, and does not count elements that occur in more than one of the sets, as was to be shown.

$\endgroup$
  • 1
    $\begingroup$ @james black I just had a look at your past questions. You never check good answers. This is not a good practise for this site. Please, at least for this answer by saulspatz which is absolutely perfect, check it as "the" answer. $\endgroup$ – Jean Marie May 7 at 9:23
  • 1
    $\begingroup$ @JeanMarie Thank you for "absolutely perfect." I agree with you about accepting answers. It's very annoying to start answering an open question, and then find that there's a perfectly good answer already. $\endgroup$ – saulspatz May 7 at 14:25
  • $\begingroup$ sorry i will go back and do that; in addition, this answer is perfection thank you $\endgroup$ – james black May 8 at 8:45
1
$\begingroup$

Let A,B,C be pairwise disjoint. Then
$n(A)+n(B)+n(C)-2 \times n(A \cap B)-2 \times n(A \cap C)-2 \times n(C \cap B) + 3 \times n(A \cap B \cap C)$
= $n(A)+n(B)+n(C)$
Pray do tell, which of A,B,C has $n(A)+n(B)+n(C)\ $ elements?
Does two of those sets have to be empty?
For example, A = {1}, B = {2}, C = {3}.

$\endgroup$
  • $\begingroup$ There are $n(A)$ elements that occur exactly in $A$, $n(B)$ that occur exactly in $B$, and $n(C)$ that occur exactly in $C$, giving $n(A)+n(B)+n(C)$ in all. $\endgroup$ – saulspatz May 4 at 7:16

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.