# Inclusion Exclusion Application

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?

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

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.

• @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. – Jean Marie May 7 at 9:23
• @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. – saulspatz May 7 at 14:25
• sorry i will go back and do that; in addition, this answer is perfection thank you – james black May 8 at 8:45

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

• 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. – saulspatz May 4 at 7:16