# 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).$$