简谈排列组合和容斥原理
基础组合计数和容斥原理
因为是数学，所以今天的代码会额外的少，我会分几个板块来阐述今天的内容。
一、基本计数原理
-
加法原理
定义：若完成一件事的方法有
n 类，其中第i 类方法包括a_i 种不同的方法，且这些方法互不重合，则完成这件事共有a_1+a_2+a_3+\dots+a_n 种不同的方法。 有点太偏理论了，我们来举个栗子：
如图，点
-
乘法原理
定义：若完成一件事需要
n 个步骤，其中第i 个步骤有a_i 种不同的完成方法，且这些步骤互不干扰，则完成这件事共有a_1\times a_2\times\dots\times a_n 种不同的方法。
同样来举个栗子：
我们由上面的加法原理可知，点1到点2共有2种情况，点2到点3共有3种情况，则点1到点3共有
讲完了基本计数原理，我们就可以学习下一个篇章了。
二、排列组合
-
排列
顾名思义，就是指从
n 个不同元素中选择m 个元素有序排列的方案数，该数被称作排列数，记作：A_n^m 或P_n^m 。
基本公式： A_n^m=\frac{n!}{(n-m)!}
-
组合
组合是指从
n 个不同元素中选择m 个元素组合的方案数(之间无序)，记作C_n^m 或\binom{n}{m} 。
基本公式： C_n^m=\frac{n!}{(n-m)!m!}
有了这些基础，我们有了以下推导。
-
计算方法
-
- 求逆元：
\frac{1}{i!}=\frac{1}{(i+1)!}\times(i+1)
-
Lucas定理：对于质数
-
由于此处重点，所以我提供了代码实现：
int Lucas(int n,int m)
{
if(m == 0) return 1;
return C(n%p, m%p) * Lucas(n/p, m/p) % p;
}-
计数的基本技巧（没有详细解释）
（一）捆绑法
（二）插空法
（三）隔板法
-
推导公式（基本性质）
-
C_n^k=C_n^{n-k} -
-
C_n^mC_m^k=C_n^kC_{n-k}^{m-k} -
\sum\limits_{i=m}^{n}C_i^m=C_{n+1}^{m+1} 有如下意义：
-
我们想求杨辉三角中一列数字之和（红框），只需要求出图中篮框数字即可。
- 范德蒙德卷积：
\sum\limits_{i=0}^{n}C_x^iC_y^{n-i}=C_{x+y}^{n} - 二项式定理：
(x+y)^n=\sum\limits_{i=0}^nC_n^ix^iy^{n-i} -
kC_n^k=nC_{n-1}^{k-1}
-
多重集的排列组合
- 多重集的排列，设
S=\{n_1a_1,n_2a_2,...,n_ka_k\} ，其中n_1+n_2+···+n_k=n ，其排列数为\frac{n!}{n_1!n_2!...n_k!} 。
- 多重集的排列，设
- 多重集的组合，
S=\{n_1a_1,n_2a_2,...,n_ka_k\},r\le n_i(\forall i\epsilon[1,k]) ，从S 中取出r 个元素组成一个多重集，产生的不同多重集的数量为C_{k+r-1}^{k-1} 。
三、容斥原理
-
定义
在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。
-
表示
$ |A \cap B| $：集合A与B的交集大小。 -
公式：
-
|A \cup B|=|A|+|B|-|A \cap B|
-
-
|A \cup B \cup C|=|A|+|B|+|C|-|A \cap B|-|A \cap C|-|B \cap C|+|A \cap B \cap C|
-
一般形式
设
简记形式：
概率版本：
对于概率空间中的事件
总结
"千里之行，始于足下。" —— 老子
面对困难与挑战，遥远的路途，我们要敢于向前，敢于拼搏，走出属于自己的路，走出踏踏实实的路。
向着理想的银河迈进！