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?
Best Answer
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.