组合数学

3 - Sieve Methods

2019-09-25 14:00 CST
2019-09-30 00:12 CST
CC BY-NC 4.0

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