数学知识之组合计数

• 加法原理

$若完成一件事有n类方法,第i类方法有a_i种方法,一共有 \sum _{i=1}^{n}a_i 种方法$

• 乘法原理

$若完成一件事有n个步骤,第i个步骤有a_i种方法,一共有 \prod_{i=1\\}^na_i 种方法$

• 排列数

$从n个不同元素中依次取出m个元素排成一列,产生不同排列的数量为$

$$A_n^m = \frac{n!}{m!}$$

• 组合数

$从n个不同的元素选出m个组成一个集合(不考虑顺序),产生不同排列的数量为$

$$C_n^m = \frac{n!}{m!(n - m)}$$

性质

• $C_n^m = C_n^{n-m}$
• $C_n^m = C_{n-1}^m + C_{n-1}^{m-1}$
• $C_n^0 + C_n^1 + C_n^2 + .... + C_n^n = 2^n$

Lucas 定理

$若p是质数,对于任意整数1\leq m \leq n, 有$
$$C_n^m \equiv C_{n \space mod \space p}^{m\space mod\space p} * C_{n/p}^{m/p}(mod\space p)$$

卡特兰数列

$在数列中任意前缀满足莫种性质一定多于不满足莫种性质的长度为2n序列数量为$
$$Catalan_n = C_{2n}^{n} - C_{2n}^{n-1} = \frac{C_{2n}^{n}}{n+1}$$
$以下问题都与卡特兰数列有关$
1. $AcWing.130 火车进出栈问题$
2. $AcWing.1257 二叉树计数$
3. $AcWing.2641字符串$
4. $AcWing.415 栈$