Counting, Subsets and Inclusion-Exclusion

The power set $P(A)$ is the set of all subsets of A, and it always contains the empty set $\varnothing$ and A itself. For $A = \{a, b\}$ the subsets are $\varnothing$, $\{a\}$, $\{b\}$ and $\{a, b\}$, so $P(A) = \{\varnothing, \{a\}, \{b\}, \{a, b\}\}$: its members are sets, and there are $4 = 2^2$ of them. Each element gives two choices (in or out), and $2 \times 2 = 4$. The counting rules:

• A set with $n$ elements has $2^n$ subsets, so $|P(A)| = 2^n$. Of these, $2^n - 1$ are proper subsets (all except the set itself).
• Supersets of a fixed set $\{x\}$: fix x as 'in', let the other $n-1$ elements vary $\Rightarrow 2^{n-1}$ subsets contain x.
• Count carefully when elements are themselves sets: $A=\{\{1,2,3\}\}$ has ONE element, so $|P(A)|=2$.
• Symmetry trick: in a $(2n+1)$-element set, the subsets of size $\le n$ are exactly half of all subsets $= \tfrac{1}{2}\cdot 2^{2n+1} = 2^{2n}$.
• Subsets of a given SIZE: an $n$-set has $\binom nr$ subsets with exactly $r$ elements (they sum to $2^n$ over $r$); e.g. a 6-set has $\binom62=15$ two-element subsets and $\binom63=20$ three-element ones. Subsets with at least $r$ elements: $\sum_{k\ge r}\binom nk$.

The two-set rule and its uses:

• $|A\cup B| = |A| + |B| - |A\cap B|$.
• For sets of multiples, $A\cap B$ uses the LCM: multiples of 3 $\cap$ multiples of 2 are multiples of 6.
• Least overlap: $|A\cap B| \ge |A|+|B|-|U|$ (when the union can't exceed the universe). Most overlap: $|A\cap B| \le \min(|A|,|B|)$.
• The mirror bounds on the union: $\max(|A|,|B|)\le|A\cup B|\le\min(|A|+|B|,\,|U|)$ — the minimum is attained when one set contains the other, the maximum when they are disjoint.
• Counting multiples: the number of multiples of $d$ in $\{1,\dots,N\}$ is $\lfloor N/d\rfloor$; so among $1..100$ there are 50 multiples of 2, 20 of 5, 10 of 10 (the LCM), and $50+20-10=60$ of 2 or 5.

The three-set rule:

• $|A\cup B\cup C| = |A|+|B|+|C| - |A\cap B| - |B\cap C| - |A\cap C| + |A\cap B\cap C|$.
• This equals the sum of the seven disjoint Venn regions.
• Maximising/minimising the union: the only free quantity is the triple overlap $x = |A\cap B\cap C|$. The union grows with x; x is bounded by $0 \le x \le \min$ of the pairwise intersections.

The accounting identities (let one/two/three = people in exactly one / exactly two / all three regions):

• Total in the union $= (\text{exactly one}) + (\text{exactly two}) + (\text{exactly three})$. This is the 'exactly' decomposition — NOT the raw inclusion-exclusion sum.
• Sum of pairwise intersections $= (\text{exactly two}) + 3\cdot(\text{all three})$, so exactly two $= \sum\text{pairwise} - 3\cdot(\text{all three})$.
• At least two $= (\text{exactly two}) + (\text{all three})$.
• Exactly one $= \text{total} - (\text{at least two})$.