The Principle of Inclusion & Exclusion

Let $S$ be a set with $|S| = N$.

Let $c_1, c_2, ..., c_t$ be conditions on the elements of $S$.

$N(a b c ...)$ denotes the number of elements of $S$ that satisfy

$$ a \land b \land c \land ... $$

So $N(\bar c_1 \bar c_2, ... \bar c_t)$ denotes the number of elements of $S$ that satisfy none of the conditions $c_i$.

$$ \begin{aligned} N(\bar c_1 \bar c_2 ... \bar c_t) &= N - \sum_{i \leq i \leq t} N(c_i) + \sum_{i \leq i < j \leq t} N(c_ic_j)

• \sum_{1 \leq i < j < k \leq t} N(c_ic_jc_k) + ...

• (-1)^t N(c_1c_2...c_t) \\ &= \sum_{k = 0}^t(-1)^k \sum_{1 leq i_1 < i_2 < ... < i_k \leq t} N(c_{i_1}c_{i_2}...c_{i_k})

\end{aligned} $$

• Simplification of Notation

  Define

  $$ \begin{aligned} S_0 &\triangleq N, \\ S_1 &\triangleq N(c_1) + N(c_2) + ... N(c_t), \\ S_2 &\triangleq N(c_1c_2) + N(c_2c_3) + ... N(c_{t - 1}c_t) \\ \vdots \\ S_k &\triangleq \sum_{1 \leq i_1 < i_2 < ... < i_k \leq t}N(c_{i_1}c_{i_2}...c_{i_k})

  \end{aligned} $$

  The principle of inclusion and exclusion simplifies to

  $$ N(\bar c_1 \bar c_2 ... \bar c_t) = S_0 - S_1 + S_2 - .... + (-1)^tS_t $$

• Corollary

  By DeMorgan’s Law,

  $$ c_1 \lor c_2 \lor ... \lor c_t = \lnot(\lnot c_1 \land \lnot c_2 \land ... \land \lnot c_t) $$

  So,

  $$ \begin{aligned} N(c_1 \lor c_2 \lor ... \lor c_t) &= N - N(\bar c_1 \bar c_2 ... \bar c_t) \\ &= S_1 - S_2+ ... + (-1)^{t - 1}S_t \end{aligned} $$

• Further Simplification

  define

  $$ N_k \triangleq N(c_{i_1}c_{i_2}...c_{i_k}) $$

  then,

  $$ S_k = \binom{t}{k}N_k $$

• Number of onto func.

Venn Diagram

Euler Phi Func.

Arithmetic & Multiplicative Func.

Permutation w/o fixed points

Derangements

Integer Sol. of Linear Eq. with Upper Bound

Generalized Principle of Inclusion & Exclusion