CM-ALL

Lesson 1

• combinatorial $\sim$ discrete & finite

  • solution combinatorial object
  • constraint combinatorial structure

• Enumeration: How many solutions satisfying the constraints

• Existence: Does there exist a solution
• Extremal: How large/small a solution can be to preserve/avoid structure
• Ramsey: when a solution is sufficiently large, some structures must emerge
• Optimization: find the optimal solution

• Construction: construct a solution

• Enumeration(Counting)

  • How many ways are there:
    1. $n!$ to rank $n$ people
    2. $12^n$ to assign $m$ zodiac signs to $n$ people
    3. $n \choose m$ to choose $m$ people out of $n$ people
    4. $n-1 \choose m-1$ to partition $n$ people into $m$ groups
    5. $?$ to distribute $m$ yuan to $n$ people
    6. $?$ to partition $m$ yuan to $n$ parts

Name	Description	Notation	Number	Repetition	Ordered
Tuple	$n$-tuples of $[m]$	$[m]^n$	$m^n$	Y	Y
Nultiset	$k$-multiset of $n$-set	-	${n+k-1\choose k}$	Y	N
Subset	$k$-uniform of $n$-set, $\	S\	=n$	-	$\binom{n}{k}$	N	N
Partition	$k$-partition of $n$-set	-	$\{ {n\atop k} \}$	N	N

• The product rule: $|S\times T|=|S|\cdot|T|$
• The bijection rule: if there exists a bijection between finite sets $S$ and $T$, then $|S|=|T|$.

• Tuples
  • $[m]=\{1,2,\cdots,m\}$
  • $[m]^n=[m] \times [m] \times\cdots\times [m]$
  • $#$ of tuples: $|[m]^n|=m^n$
• Functions
  • $f:[n]\to[m]$
  • $#$ of functions: $m^n$

    Proof: $f:[n]\to[m]\Leftrightarrow v_f\in[m]^n$

• Subsets
  • Power set: $2^{[n]}={S|S\subseteq [n]}$
  • $|2^{[n]}|=2^n$
  • Proof: $S\subseteq [n]\leftrightarrow \{0,1\}^n$
• Subsets of fixed size
  • $#$ of $k$-uniform: ${n \choose k}=\frac{n!}{k!(n-k)!}$
  • $(n)_k=n(n-1)\cdots(n-k+1)$ is $n$ lower factorial of $k$
• Binomial coefficients
  • ${n \choose k}={n\choose n-k}$
  • $\sum_{k=0}^{n}{n \choose k}=2^n$
  • $(1+x)^n=\sum_{k=0}^{n}{n \choose k}x^k$

    Proof: $(1+x)^n=(1+x)(1+x)\cdots(1+x)$, $#$ of $x^k$ is $n\choose k$

  • $S=\{x_1, x_2,\cdots,x_n\}$, $#$ of odd subsets $=$ $#$ of even subsets

    proof: let $x=-1$

• Compositions of an integer
  • $k$-composition of $n$: $k$-tuple that $x_1+x_2+\cdots+x_n=n$, $x_i\in\{1,2,\cdots x_n\}$
  • $#$ of $k$-composition: $n-1 \choose k-1$
  • weak $k$-composition of $n$: $x_i$ can be 0, aka $(x_1+1)+(x_2+1)+\cdots+(x_n+1)=n+k$
  • $#$ of weak $k$-composition: $n+k-1\choose k-1$
• Multisets
  • Combinations with repetitions can be formally defined as multisets.
  • $({n \choose k})={n+k-1\choose k}$
• Multinomial coefficients
  • $\binom{n}{m_1,m_2,\cdots, m_k}=\frac{n!}{m_1!m_2!\cdots m_k!}$, $\sum_i m_i=n$
  • $\binom{n}{m, n-m}=\binom{n}{m}$
  • $(x_1,x_2,\cdots,x_k)^n=\sum_{m_1+m_2+\cdots+m_k=n}\binom{n}{m_1,m_2,\cdots, m_k}x_1^{m_1}\cdots x_k^{m_k}$
• Partitions of a set
  • partition of $S$: $P={S_1,S_2,\cdots,S_k}$, $S_i\ne\emptyset$, $S_i\cap S_j$ if $i\ne j$, $\bigcup S_i=S$
  • if $|P|=k$, then $P$ is a $k$-partition of $S$
  • $#$ of $k$-partitions of a $n$-set is $\{ {n\atop k} \}$
  • Stirling number of the second kind
• The twelvfold way

$n$ balls	$m$ bins	unrestricted	$\leq 1$ for all bin	$\geq 1$ for all bin
distinct	distinct	$m^n$	$(m)_n=n!\binom{m}{n}$	$m!\{ {n\atop m} \}$
identical	distinct	$(\binom{m}{n})$	$m\choose n$	$\binom{m-1}{n-1}$
distinct	identical	$\sum_{k=1}^m\{ {n\atop k} \}$	$1$	$\{ {n\atop m} \}$
identical	identical	$-$	$-$	$-$