【笔记】基础计数原理与组合数
一、加法原理和乘法原理
1、定义：
①加法原理：
加法原理是分类计数原理，常用于排列组合中，具体是指：做一件事情，完成它有N类方式，第一类方式有M_1 种方法，第二类方式有M_2 种方法，……，第n类方式有Mn种方法，那么完成这件事情共有M_1+M_2+……+M_n 种方法。
口诀：类类独立
②乘法原理：
做一件事，完成它需要分成N个步骤，做第一步有M_1 种不同的方法，做第二步有M_2 种不同的方法，……，做第n步有M_n 种不同的方法。那么完成这件事共有 N=M_1×M_2×M_3×…×M_n 种不同的方法。
口诀：步步相关
2、例：
（1）某中学八年级一班有12名男生，16名女生；二班有9名男生，17名女生。
问：
从这两个班的同学中，选择 1 名男生、1 名女生作为主持人。有几种选法?
利用乘法原理，总方案数等于 总男生数 * 总女生数
（12+9）* （16+17）=693
3、模运算
在得数较大时，要每进行一步计算就取余。
模运算符合以下规律
（1）(a - b) % p = (a % p - b % p ) % p
（2）(a + b) % p = (a % p + b % p) % p
（3）(a b) % p = (a % p b % p) % p
（4）(a^b ) % p = ((a\%p)^b ) % p
二、排列与组合
1、排列数
定义：从 n 个人里面选出 m 个人站成一排，方案数是： n ⋅ (n − 1) ⋯ (n − m + 1) = \frac{ n ! }{ (n-m)! } 。我们将它称为排列数。
排列数用 A^m_n 表示“从 n 个元素里面取 m 个元素，排成一排的方案数”，也就是A^m_n = \frac{ n ! }{ (n-m)! } 。
2、组合数
（1）定义：用 C^m_n 表示“从 n 个元素里面选出 m 个元素”的方案数。C^2_3 =3。
我们将它称为组合数。
（2）公式:
组合数的递推公式，称为帕斯卡公式。
C^m_n = C^{m-1}_{n-1} + C^{m-1}_{n}
C^n_0 =1;C^n_n =1;C^0_0 =1
组合数的通项公式
C^m_n = \frac{A_n^m}{A_m^m} = \frac{n\cdot(n-1)\cdot\cdot\cdot(n-m+1)}{m(m-1)\cdot\cdot\cdot2\cdot1} = \frac{n!}{m!\cdot(n-m)!}
互补性质
C^m_n =C^{n-m}_n
（3）代码实现
①通项公式
long long fac(int n)
{
long long f=1;
for(int i=n;i>0;i--)
f *= i;
return f;
}//求阶乘
long long C(int n, int m)
{
return fac(n)/(fac(n - m)*fac(m));
}②递归公式
for (int i=0;i<=21;i++)
{
C[i][0] = C[i][i] = 1;
for (int j=1;j<i;j++)
C[i][j]=C[i-1][j]+C[i-1][j-1] ; //递推
}