基础组合计数和容斥原理

因为是数学，所以今天的代码会额外的少，我会分几个板块来阐述今天的内容。

一、基本计数原理

加法原理

定义：若完成一件事的方法有

n

类，其中第

i

类方法包括

a_i

种不同的方法，且这些方法互不重合，则完成这件事共有

a_1+a_2+a_3+\dots+a_n

种不同的方法。有点太偏理论了，我们来举个栗子：

如图，点

1

和点

2

之间有三条不同的路线，那么就有

1+1+1=3

种情况。

乘法原理

定义：若完成一件事需要

n

个步骤，其中第

i

个步骤有

a_i

种不同的完成方法，且这些步骤互不干扰，则完成这件事共有

a_1\times a_2\times\dots\times a_n

种不同的方法。

同样来举个栗子：

我们由上面的加法原理可知，点1到点2共有2种情况，点2到点3共有3种情况，则点1到点3共有

2\times 3=6

种情况。

讲完了基本计数原理，我们就可以学习下一个篇章了。

二、排列组合

排列

顾名思义，就是指从 $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!}$

有了这些基础，我们有了以下推导。

计算方法

$C_n^m=C_{n-1}^{m-1}+C_{n-1}^m$ 其中边界条件为 $C_0^0=1,C_i^0=1$ （组合计数的递推式）
求逆元： $\frac{1}{i!}=\frac{1}{(i+1)!}\times(i+1)$

Lucas定理：对于质数

p\le n

的情况可以使用：

$C_n^m \equiv C_{n\bmod p}^{m\bmod p}C_{{\lfloor \frac{n}{p}\rfloor}}^{{\lfloor \frac{m}{p}\rfloor}}\pmod p$

~~由于此处重点，所以~~我提供了代码实现：

CPP

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}$
$\sum\limits_{k=0}^{n}C_{n}^{k}=2^n\$ （二项式定理拓展）
$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 \cup B|

：集合A与B的并集大小。

|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|$

一般形式

设

A_1, A_2, \dots, A_n

是有限集合，则它们的并集的大小为：

\left| \bigcup_{i=1}^n A_i \right| = \sum_{i=1}^n |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \dots + (-1)^{n+1} \left| \bigcap_{i=1}^n A_i \right|

简记形式：

\left| \bigcup_{i=1}^n A_i \right| = \sum_{\emptyset \neq S \subseteq \{1,2,\dots,n\}} (-1)^{|S|+1} \left| \bigcap_{j \in S} A_j \right|

概率版本：

对于概率空间中的事件

A_1, A_2, \dots, A_n

：

P\left( \bigcup_{i=1}^n A_i \right) = \sum_{k=1}^n (-1)^{k+1} \sum_{1 \leq i_1 < \dots < i_k \leq n} P(A_{i_1} \cap \dots \cap A_{i_k})

总结

"千里之行，始于足下。" —— 老子

面对困难与挑战，遥远的路途，我们要敢于向前，敢于拼搏，走出属于自己的路，走出踏踏实实的路。

向着理想的银河迈进！

简谈排列组合和容斥原理

文章操作

基础组合计数和容斥原理

一、基本计数原理

加法原理

乘法原理

二、排列组合

排列

基本公式： $A_n^m=\frac{n!}{(n-m)!}$

组合

基本公式： $C_n^m=\frac{n!}{(n-m)!m!}$

计算方法

$C_n^m \equiv C_{n\bmod p}^{m\bmod p}C_{{\lfloor \frac{n}{p}\rfloor}}^{{\lfloor \frac{m}{p}\rfloor}}\pmod p$

计数的基本技巧（没有详细解释）

推导公式（基本性质）

多重集的排列组合

三、容斥原理

定义

表示

公式：

一般形式

简记形式：

概率版本：

总结

相关推荐

评论

简谈排列组合和容斥原理

文章操作

基础组合计数和容斥原理

一、基本计数原理

加法原理

乘法原理

二、排列组合

排列

基本公式：Anm=n!(n−m)!A_n^m=\frac{n!}{(n-m)!}Anm​=(n−m)!n!​

组合

基本公式：Cnm=n!(n−m)!m! C_n^m=\frac{n!}{(n-m)!m!}Cnm​=(n−m)!m!n!​

计算方法

Cnm≡Cn mod pm mod pC⌊np⌋⌊mp⌋(modp)C_n^m \equiv C_{n\bmod p}^{m\bmod p}C_{{\lfloor \frac{n}{p}\rfloor}}^{{\lfloor \frac{m}{p}\rfloor}}\pmod pCnm​≡Cnmodpmmodp​C⌊pn​⌋⌊pm​⌋​(modp)

计数的基本技巧（没有详细解释）

推导公式（基本性质）

多重集的排列组合

三、容斥原理

定义

表示

公式：

一般形式

简记形式：

概率版本：

总结

相关推荐

评论

基本公式： $A_n^m=\frac{n!}{(n-m)!}$

基本公式： $C_n^m=\frac{n!}{(n-m)!m!}$

$C_n^m \equiv C_{n\bmod p}^{m\bmod p}C_{{\lfloor \frac{n}{p}\rfloor}}^{{\lfloor \frac{m}{p}\rfloor}}\pmod p$