Medium Practice — Set 1

Quick Recap — Sets: Counting & Relations

• Inclusion–exclusion: $n(A\cup B\cup C)=\sum n-\sum n(\text{pairs})+n(A\cap B\cap C)$.
• Relation counts on an $n$-set: all $=2^{n^2}$; reflexive $=2^{n^2-n}$; symmetric $=2^{n(n+1)/2}$.
• Function counts $A\to B$: all $|B|^{|A|}$; one-one $=|B|(|B|-1)\cdots$; onto by inclusion–exclusion.
• Equivalence relation = reflexive + symmetric + transitive; it partitions the set into classes.