组合数学 学习笔记

计数问题 Ⅰ

一.排列与组合

1.1 四个基本计数原理

划分：集合S的一个划分是它的子集$ S_1,S_2,S_3…S_m $ 使每个元素恰好只属于其中的一个子集。

加法原理：$ |S| = |S_1| + |S_2| + |S_3| +...+|S_m| $

乘法原理 ：设$ S$是有序对$ (a,b) $的集合，对象$a$来自大小为$p$的集合， 对象$b$来自大小为$q$的集合，则$ |S|=p*q $

减法原理：设$ A\subseteq U $,且 $\bar{A}=\complement_UA$ ，那么$ |A|=|U|-|\bar{A|}$

除法原理: $ k=\frac{|S|}{m} $，其中m为在一个部分中的对象数目。

1.2 集合的排列

排列：一个n元素集合S的r排列，我们理解为n个元素中的r个元素的有序放置

用$P(n,r)$表示n元素集合的r排列数目，我们有：

$P(n,r)=\frac{n!}{(n-r)!}$

特殊的 $P(n,0)=1$

n元素集合的循环r排列数目：

$\frac{P(n,r)}{r}=\frac{n!}{r·(n-r)!}$

1.3 集合的组合

组合（子集）：集合S元素的一个无序选择A。$A\subseteq S$

用$n\choose r$表示n元素集合的r子集的数目。我们有

${n\choose{r}}={\frac{n!}{r!(n-r)!}}={n\choose n-r}$

帕斯卡公式：对于所有满足$1\le k\le n-1$ 的整数n和k，有

${n\choose{k}}={n-1\choose k}+{n-1\choose k-1}$

吸收恒等式：

$\binom n m=\frac{n!}{m!(n-m)!} = \frac{n}{m}\times\frac{(n-1)(n-2)\cdots(n-m+1)}{(m-1)(m-2)\cdots 1}\\\binom n m=\frac n m\binom {n-1}{m-1}$

归纳恒等式

$\binom n m=\binom {n-1} {m}+\binom{n-1}{m-1}$

证明：从前n-1个物品中选择m个或m-1个两种情况，即最后一个物品选或不选。

特：Lucas定理：

若p为质数，有

${n\choose m}\equiv {{n\mod p}\choose{m\mod p}}*{{n/p}\choose{m/p}}$

1.4 杨辉三角及二项式定理

​ 第0列

杨辉三角 1 第1列 第0行

											1	    1     第2列                              第1行

​ 1 2 1 第3列 第2行

​ 1 3 3 1 第3行

$ \cdots$

注意到，第n行第k列的数为$\binom n k$ 。

第n行的和为$2^{n}$

$(x+1)^n=\sum^n_{i=0}x^i\binom n i$

简单证明：

$(x+1)^n=(x-1)\times(x-1)^{n-1}$

考虑其组合意义，$(x+1)^n$ 的第k项就是用x乘上$(x-1)^{n-1}$的第k-1项加上1乘上$(x-1)^{n-1}$ 的第k-1项。那么就有

$[x^k](x+1)^n=[x^{k-1}](x-1)^{n-1}+[x^k](x-1)^n$

即$[x^k](x-1)^n=\binom n k$

二项式定理

由上式，我们有：

$(x+1)^n=\sum^n_{i=0}x^i\binom n i$

取$x=\frac a b$,有：

$(\frac a b+1)^n=\sum^n_{i=0}\binom n ia^ib^{-i}$

两边同乘$b^n$,得：

$(a+b)^n=\sum^n_{i=0}\binom n ia^ib^{n-i}$

二.容斥原理和集合反演

2.1 容斥原理

$|A\cup B \cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C|$

这是最基础的集合容斥。

容斥定理

对于多个集合，我们有：

$|\bigcup^n_{i=1}A_i|=\sum_{T\subseteq[1,n]}(-1)^{|T|-1}|\bigcap_{j\in T}S_j|$

集合反演

对于函数$f(S),g(S)$，有

$f(S)=\sum_{T\subseteq S}g(T)\Leftrightarrow g(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|} f(T)$

证明，先咕着。

三.特殊方法

插板法，必须相邻，互不相邻

隔板法：n个物品分k堆，不可空，有$\binom n k$种分法。

插板法的应用：求方程

$x_1+x_2+x_3+\cdots+x_k=n$

的解的个数，且要求$x_i>d_i$