组合数学 学习笔记
AlanSP
·
·
个人记录
今天起，蒟蒻AlanSP要补一补自己本来就没多少水平的组合数学，我还会把学习方面的一些经验和收获写到博客上，希望dalao们能赏眼QAQ.
一.排列与组合
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!}{(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