Set Theory and Notation

Set operations as bit operations

Representing a subset of $\{0,\dots ,n-1\}$ as an integer makes every set operation $O(1)$:

Set operation	Notation	Bitwise
Intersection	$A\cap B$	A & B
Union	$A\cup B$	A | B
Symmetric difference	$A△B$	A ^ B
Difference	$A\setminus B$	A & ~B
Complement	$\overline{A}$	~A & ((1<<n)-1)
Subset test	$A\subseteq B$	(A & B) == A, or (A | B) == B
Disjoint	$A\cap B=\varnothing$	(A & B) == 0
Cardinality	$|A|$	__builtin_popcount(A)
Add element $i$	$A\cup \{i\}$	A | (1<<i)
Remove element $i$	$A\setminus \{i\}$	A & ~(1<<i)
Toggle $i$		A ^ (1<<i)
Membership	$i\in A$	A >> i & 1
Empty / universal set	$\varnothing$ / $U$	0 / (1<<n)-1

See Bit Operations and Enumerating Submasks.

Inclusion-exclusion

$\left|{\bigcup }_{i=1}^n{A}_i\right|={\sum }_i|A_i|-{\sum }_{i<j}|A_i\cap A_j|+\cdots +(-1{)}^{n+1}|A_1\cap \cdots \cap A_n|$

$={\sum }_{\varnothing \ne S\subseteq [n]}(-1{)}^{|S|+1}\left|{\bigcap }_{i\in S}{A}_i\right|.$

long long total = 0;
for (int mask = 1; mask < (1 << n); mask++) {
    long long size = intersectionSize(mask);
    total += (__builtin_popcount(mask) & 1) ? size : -size;
}

$O(2^n)$. When the sets are “divisible by $p_i$”, the signs are exactly the Möbius function, and the sum can be sieved instead of enumerated — see Möbius Function.

Complementary counting is the same idea used backwards: count what you do not want and subtract. Often much easier.

Notation reference

Symbol	Meaning
$\in$, $\notin$	element of, not an element of
$\subseteq$, $⊊$	subset, proper subset
$\cup$, $\cap$, $\setminus$, $△$	union, intersection, difference, symmetric difference
$|A|$	cardinality
$2^A$ or $\mathcal{P}(A)$	power set — all $2^{|A|}$ subsets
$A\times B$	Cartesian product
$\left(\genfrac{}{}{0ex}{}{A}{k}\right)$	all $k$-element subsets
$\varnothing$	the empty set
$\mathbb{N},\mathbb{Z},\mathbb{Q},\mathbb{R},\mathbb{C}$	naturals, integers, rationals, reals, complexes
${\mathbb{Z}}_n$, ${\mathbb{F}}_q$	integers mod $n$, the field of order $q$
$[n]$	$\{1,2,\dots ,n\}$
$\lfloor x\rfloor$, $\lceil x\rceil$	floor, ceiling
$\sum$, $\prod$	sum, product
$\forall$, $\exists$	for all, there exists
$\Rightarrow$, $⟺$	implies, if and only if
$\equiv$	congruent (modular)
$\mid$, $\nmid$	divides, does not divide
$\oplus$	XOR (or direct sum)
$\mathrm{mex}$	minimum excluded non-negative integer
$[P]$	Iverson bracket: 1 if $P$ holds, else 0

The Iverson bracket is worth adopting: writing $[\gcd (i,j)=1]$ inside a sum makes Möbius manipulations mechanical.

Counting sets

Quantity	Count
Subsets of an $n$-set	$2^n$
$k$-subsets	$\left(\genfrac{}{}{0ex}{}{n}{k}\right)$
Ordered pairs $(A,B)$ with $A\subseteq B$	$3^n$
Ordered pairs with $A\cap B=\varnothing$	$3^n$
Partitions into non-empty blocks	$B_n$ (Bell)
Partitions into exactly $k$ blocks	$S(n,k)$ (Stirling 2nd kind)
Chains $\varnothing \subset A_1\subset \cdots \subset A_k$	ordered set partitions
Antichains in the subset lattice	Dedekind numbers (no closed form)

The $3^n$ identity is the one that matters computationally: it is exactly why submask enumeration over all masks is $O(3^n)$.

The subset lattice

Subsets ordered by $\subseteq$ form a lattice — a hypercube graph $Q_n$. Consequences:

• SOS DP is a zeta transform over this lattice.
• Gray code is a Hamiltonian path on it.
• Möbius inversion on the lattice is the inclusion-exclusion formula.
• The maximum antichain has size $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ (Sperner’s theorem).

See also: Bit Operations · Combinatorics · Möbius Function