3. Sieve Methods

Principle of Inclusion-Exclusion

\( \left\vert \bigcup\limits_{i=1}^n A_i \right\vert = \sum\limits_{I \subseteq {1, \dots, n}, I \neq \emptyset} (-1)^{\vert I \vert - 1} \left\vert \bigcap\limits_{i \in I} A_i \right\vert \).

Suppose \( A_1, \dots, A_n \subseteq U \), then \[ \left\vert \overline{A_1} \cap \dots \cap \overline{A_n} \right\vert = \left\vert U - \bigcup\limits_{i=1}^n A_i \right\vert. \]

Denote \( A_I = \bigcap\limits_{i \in I} A_i \), \( A_{\emptyset} = U \).

Surjections

What is # of onto functions from \( [n] \) to \( [m] \)?

Let \( U \) be the domain of functions \( [n] \rightarrow [m] \). \( A_i = [n] \rightarrow ([m] \setminus {i}). \)

Then we have \[ \left\vert \bigcap_{i \in [m]} \overline{A_i} \right\vert = \sum\limits_{I \subseteq [m]} (-1)^{\vert I \vert} \vert A_I \vert = \sum\limits_{I \subseteq [m]} (-1)^{\vert I \vert} (m - \vert I \vert)^n = \sum\limits_{k=0}^{m} (-1)^{m-k} {m \choose k} k^n. \]

Therefore, the sterlin number of the second kind is \[ {n \brace m} = \dfrac{1}{m!} \sum\limits_{k=0}^{m} (-1)^{m-k} {m \choose k} k^n. \]

Derangement

# of permutation \( \pi \) of \( [n] \), \( \forall i \), \( \pi(i) \neq i \). (permutations with no fixed point, denoted as \( !n \)).

\( U \): all permutations of \( [n] \) (a symetric group), \( A_i \): permutations with \( \pi(i) = i \).

Size of \( A_I \) is \( (n - \vert I \vert)! \).

\[ \left\vert \bigcap_{i \in [n]} \overline{A_i} \right\vert = \sum\limits_{I \subseteq [n]} (-1)^{\vert I \vert} \vert A_I \vert = \dots = n! \sum_{k=0}^n \dfrac{(-1)^k}{k!} = \dfrac{n!}{e}. \]

Permutations with restricted positions

  • Derangement: \( \forall i, \pi(i) \neq i \)
  • Generally: \( \pi(i_1) \neq j_1, \pi(i_2) \neq j_2, \dots \)
  • Forbidden patterns: \( B \subseteq [n] \times [n], \forall i, (i, \pi(i)) \notin B \)

A chess board: a grid of \( [n] \times [n] \). To put \( n \) chess pieces on the board and with no two pieces on same row/column. (A placement of non-attacking rooks).

Forbidden positions \( B \subseteq [n] \times [n] \)

Derangement: \( \forall i, (i, i) \notin B \) (not on the diagonal).

\( r_k \): # of ways of placing \( k \) non-attacking rooks in \( B \).

\[ r_k = {n \choose k}. \]

\( N_0 \): # of placements of \( n \) non-attacking rooks.

\[ N_0 = \sum\limits_{k=0}^{n} (-1)^k r_k (n-k)! = \sum\limits_{k=0}^{n} (-1)^k {n \choose k} (n-k)! \rightarrow \dfrac{n!}{e}. \]

Ménage Problem

# of ways that \( n \) couples sit around a table, satisfying

  • male-female alternative
  • no one sit next to its spouse

Ladies first choose where to sit: \( 2 \cdot n! \) ways (all odd or all even).

Then gentlemen sit, each way has a corresponding permutation \( \pi \) of \( [n] \).

  • \( i \): husband of the lady at the \( i \)-th position.
  • \( \pi(i) \): his position

Requires

  • \( \pi(i) \neq i \)
  • \( \pi(i) \neq i+1 \mod n \)

\( \Rightarrow \) Chess game again: \( B = {(i, i), (i, i+1 \mod n)} \).

  • \( r_k \): # of ways of placing \( k \) non-attacking rooks in \( B \).
  • \( r_k \): # of ways of choosing \( k \) non-consecutive points from a circle of \( 2n \) points

\( \Rightarrow \) \( L(m, k) \): # of ways to choose \( k \) non-consecutive objects from a line of \( m \) objects.

  • select \( k \) slots from \( n-k+1 \) slots after removing \( k \) objects.

\[ L(m, k) = {n-k+1 \choose k}. \]

\( C(m, k) \): # of ways to choose \( k \) non-consecutive objects from a circle of \( m \) objects.

  • choose \( k \) non-consecutive objects from a circle and mark one of the remaining objects: \( (m-k) \cdot C(m, k) \).
  • mark one object and disconnect the circle by removing the object, then choose \( k \) non-consecutive objects from the \( m-1 \) objects: \( m \cdot L(m-1, k) \).

\[ C(m, k) = \dfrac{m}{m-k} L(m-1, k) = \dfrac{m}{m-k} {m-k \choose k}. \]

\( \Leftarrow \) \( r_k = \dfrac{2n}{2n-k}{2n-k \choose k} \). Therefore,

\[ N_0 = \sum\limits_{k=0}^{n} (-1)^k r_k (n-k)! = \sum\limits_{k=0}^{n} (-1)^k \dfrac{2n}{2n-k} {2n-k \choose k} (n-k)! \]

Inversion

\( V \): \( 2^n \)-dimensional vector space of all mappings

\[ f: 2^{[n]} \rightarrow \mathbb{N}. \]

linear transformation \( \phi: V \rightarrow V \).

\[ \forall S \subseteq [n], \ \ \phi(f(S)) \overset{\Delta}{=} \sum_{T \supseteq S, T \subseteq [n]} f(T). \]

then its inverse:

\[ \forall S \subseteq [n], \ \ \phi^{-1} (f(S)) = \sum_{T \supseteq S, T \subseteq [n]} (-1)^{[T \setminus S]} f(T). \]

\( f_{=}(I) = \left\vert \left\{ x \in U | \forall i \in I, x \in A_i, \forall j \notin I, x \notin A_j \right\} \right\vert = \left\vert \left(\bigcap\limits_{i \in I} A_i\right) \setminus \left(\bigcap\limits_{j \notin I} A_j\right) \right\vert. \)

\( f_{\geqslant} (I) = \sum\limits_{J \supseteq I, J \subseteq [n]} f_{=}(J) = \left\vert \bigcap\limits_{i \in I} A_i \right\vert = \vert A_I \vert. \)

PIE:

  • \( \sum\limits_{I \subseteq S} (-1)^{\vert S \vert - \vert I \vert} = \begin{cases}1, & S = \emptyset, \\ 0, & \text{otherwise}.\end{cases} \)
  • for all \( T \subseteq S \), \[ \sum\limits_{T \subseteq I \subseteq S} (-1)^{\vert S \vert - \vert I \vert} = \begin{cases}1, & S = T, \\ 0, & \text{otherwise}.\end{cases} \]

Bipartite perfect matching

Given a bipartite graph \( G([n], [n], E) \), # of permutations \( \pi \) of \( [n] \) satisfying that \( (i, \pi(i)) \in E \).

\( n \times n \) matrix \( A \): \( A_{ij} = \begin{cases}1, & (i, j) \in E, \\ 0, & (i, j) \notin E. \end{cases} \)

# of perfect matching in \( G = \sum\limits_{\pi \in S_n} \prod\limits_{i \in [n]} A_{i, \pi(i)} \).

  • permanent: \( \text{perm}(A) = \sum\limits_{\pi \in S_n} \prod\limits_{i \in [n]} A_{i, \pi(i)} \).
  • determinant: \( \det(A) = \sum\limits_{\pi \in S_n} (-1)^{r(\pi)} \prod\limits_{i \in [n]} A_{i, \pi(i)}. \)

Ryser's formula \( O(n!) \rightarrow O(n 2^n) \):

\[ \sum\limits_{\pi \in S_n} \prod\limits_{i \in [n]} A_{i, \pi(i)} = \sum\limits_{I \subseteq [n]} (-1)^{n - \vert I \vert} \prod_{i \in [n]} \sum_{j \in I} A_{ij}. \]

Sieve of Eratosthenes

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Euler Totient Function

\( \phi(n) = \left\vert \left\{ 1 \leqslant a \leqslant n | \gcd(a,n) = 1 \right\} \right\vert \).

prime decomposition: \( n = p_1^{k_1} p_2^{k_2} \cdots p_{r}^{k_r} \).

\( U = [n], A_i = \left\{ 1 \leqslant a \leqslant n \ {\large|} \ p_i \vert a \right\} \).

\( \vert A_i \vert = \dfrac{n}{p_i}, \vert A_I \vert = \dfrac{n}{\prod p_i}. \)

Therefore, \( \phi(n) = \sum_{I \subseteq [r]} (-1)^{\vert I \vert} \vert A_I \vert = n \prod\limits_{i=1}^{r} \left( 1 - \dfrac{1}{p_i} \right). \)