组合数学

1 - Basic Enumeration

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

Preface

Combinatorial problems:

  • Enumeration (counting):有多少个符合条件的解?
  • Existence:是否存在解?
    • Extremal(极问题):满足特定约束的解最大/最小是多少?
    • Ramsey:当解很大的时候会出现什么结构?
  • Optimization:找到最优解
  • Construction (design):构造一个解

Enumeration

How many ways are there:

  • to rank $n$ people: $n!$
  • to assign $m$ zodiac signs to $n$ people: $m^n$
  • to choose $m$ people out of $n$ people: $\binom{n}{m}$
  • to partition $n$ people into $m$ groups: ${n \brace m} = \binom{n+m-1}{m-1}$ (stirling numbers of the second kind)
  • to distribute $m$ yuan to $n$ people: $n^m$
  • to partition $m$ yuan to $n$ parts: $p_n(m)$ (partition number)
  • $\dots$

The Twelvefold Way

Knuth’s version: $n$ balls are put into $m$ bins

balls per bin any $\leqslant 1$ $\geqslant 1$
$n$ distinct balls, $m$ distinct bins $m^n$ $(m)_n$ $m!{n \brace m}$
$n$ identical balls, $m$ distinct bins $\left({m \choose n}\right)$ ${m \choose n}$ ${n-1 \choose m-1}$
$n$ distinct balls, $m$ identical bins $\sum\limits_{k=1}^{m} {n \brace k}$ $\begin{cases}1 \text{ if } n \leqslant m \\ 0 \text{ if } n > m\end{cases}$ ${n \brace m}$
$n$ identical balls, $m$ identical bins $\sum\limits_{k=1}^m p_k(n)$ $\begin{cases}1 \text{ if } n \leqslant m \\ 0 \text{ if } n > m\end{cases}$ $p_m(n)$


Tuples

符号定义:

  • $[m] = \lbrace 1, 2, \dots, m \rbrace$
  • $[m]^n = [m] \times \dots \times [m]$
  • $\vert [m]^n \vert = m^n$

Product rule: $\vert S \times T \vert = \vert S \vert \cdot \vert T \vert$.

Functions

Bijection rule: 若存在$S$到$T$的双射,则$\vert S \vert = \vert T \vert$.

Therefore, the number of functions:

  • $f: [n] \rightarrow [m]$
  • $f \Leftrightarrow (f(1), \dots, f(n)) \in [m]^n$
  • $\vert [n] \rightarrow [m] \vert = \vert [m]^n \vert = m^n$.

The number of 1-1 functions (injections):

  • $\pi = (f(1), \dots, f(n))$
  • $n$-permutation: $\pi \in [m]^n$ of distinct elements
  • $\vert \pi \vert = \dfrac{m!}{(m-n)!} = (m)_n$ ($m$ lower factorial $n$)

Subsets

  • $[n] = \lbrace 1, 2, \dots, n \rbrace$
  • Power set: $2^{[n]} = \lbrace S | S \subseteq [n] \rbrace$
  • $\vert 2^{[n]} \vert = 2^n$

Sum rule: finite disjoint sets $S$ and $T$, $\vert S \cup T \vert = \vert S \vert + \vert T \vert$.

$\Rightarrow \vert 2^{[n]} \vert = 2\vert 2^{[n-1]} \vert, \vert 2^{\emptyset} \vert = 1$.

Subsets of fixed size:

  • $k$-uniform: ${S \choose k} = \lbrace T \subseteq S | \vert T \vert = k \rbrace$
  • ${n \choose k} = \vert {[n] \choose k} \vert = \dfrac{n!}{k!(n-k)!}$

Binomial coefficients

Binomial coefficient: ${n \choose k} = \dfrac{n!}{k!(n-k)!}$

Properties:

  • ${n \choose k} = {n \choose n-k}$
  • $\sum\limits_{k=0}^{n} {n \choose k} = 2^n$
  • # of odd subsets = # of even subsets

Binomial theorem: $(1+x)^n = \sum\limits_{k=0}^{n} {n \choose k} x^k$.

Compositions of an integer

$n$块钱分给$k$个不同的人,每个人至少一块钱:

$k$-composition of $n$: a $k$-tuple $(x_1, x_2, \dots, x_k)$, satisfying

$$x_1 + x_2 + \dots + x_k = n, \ x_i \in \mathbb{Z}^+$$

# of $k$-composition of $n$: ${n-1 \choose k-1}$ (can be proven in the following ways)

  • 高中的插板法
  • Define $\phi((x_1, \dots, x_k)) = \lbrace x_1, x_1 + x_2, \dots, x_1 + x_2 + \dots + x_{k-1} \rbrace$, then $\phi$ is a 1-1 correspondence between $k$-compositions of $n$ and ${[n-1] \choose k-1}$.

Weak $k$-composition of $n$: $x_i \in \mathbb{N}$ $$(x_1 + 1) + (x_2 + 1) + \dots + (x_k + 1) = n + k$$

# of weak $k$-composition of $n$: ${n+k-1 \choose k-1}$

Multisets

$k$-subset of $S$: “$k$-combination of set $S$ without repetition”.

# of $k$-subset is denoted as $\left( {n \choose k} \right) = {n+k-1 \choose n-1} = {n+k-1 \choose k}$.

$k$-subset of $S$ is a weak $n$-composition of $k$.

Multinomial coefficients

Permutations of a multiset of size $n$ with multiplicities $m_1, m_2, \dots, m_k$

= Assign $n$ distinct balls to $k$ distinct bins with the $i$-th bin receiving $m_i$ balls

E.g. # of reordering of “multinomial” $\Leftrightarrow$ permutations of {a, i, i, l, l, m, m, n, o, t, u}

Multinomial coefficient is denoted as ${n \choose m_1, \dots, m_k} = \dfrac{n!}{m_1! m_2! \dots m_k!}$.

Multinomial theorem: $(x_1 + \dots + x_k)^n = \sum\limits_{m_1+\dots+m_k = n} {n \choose m_1, \dots, m_k} x_1^{m_1} \cdots x_k^{m_k}$

Partitions of a set

把$n$个人分到$k$艘船上,每艘船至少一个人

Divide a set of $n$ into $k$ partitions

$P = \lbrace A_1, \dots, A_k \rbrace$ is a partition of $S$ if:

  • $A_i \neq \emptyset$,
  • $A_i \cap A_j = \emptyset$,
  • and $\bigcup A_i = S$.

# of $k$-partitions of an $n$ set (Stirling number of the second kind) is denoted as ${n \brace k}$.

# of all partitions of an $n$ set (Bell number) is $B_n = \sum\limits_{k=1}^{n} {n \brace k}$.

Satisfies: ${n \brace k} = k {n-1 \brace k} + {n-1 \brace k-1}$ (as the following two cases)

  • case 1: $\lbrace n \rbrace$ is not a partition block
  • case 2: $\lbrace n \rbrace$ is a partition block

Surjections

$\forall i \in [m]$, $f^{-1}(i) \neq \emptyset$, then

$f \Leftrightarrow (f^{-1}(1), \dots, f^{-1}(m))$.

Surjections is equal to an ordered $m$-partition of $[n]$

Therefore # of surjections is $m! {n \brace m}$.

Partitions of a number

$p_k(n)$: # of partitions of $n$ into $k$ parts

Equal to # of integral solutions to

$$\begin{cases}x_1 + \dots + x_k = n, \ x_1 \geqslant \dots \geqslant x_k \geqslant 1\end{cases}$$

Depending on $x_k = 1$ or not, we have

$$p_k(n) = p_{k-1}(n-1) + p_k(n-k)$$

Difference of partition and composition:

  • partition: $x_1 \geqslant \dots \geqslant x_k \geqslant 1$
  • composition: $x_i \geqslant 1$

Every partition is a composition (onto).

If we have a partition of $n$ into $k$ parts $x_1 \dots x_k$, then by defining $y_i = x_i + k - i$, we have a $k$ composition of $n + \dfrac{k(k-1)}{2}$ (1-1).

Therefore, we have

$$\dfrac{{n-1 \choose k-1}}{k!} \leqslant p_k(n) \leqslant \dfrac{n + \frac{k(k-1)}{2} -1 \choose k-1}{k!}$$

Results of Young Graph:

  • # of partitions of $n$ into $k$ parts = # of compositions of $n$ with largest part being $k$
  • # of partitions of $n$ into $k$ parts = # of partitions of $n-k$ into at most $k$ parts