一、加法原理和乘法原理

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 个元素”的方案数,我们将它称为组合数。

(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_n^m=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] ; //递推
}

文章转载于本人原博客

赏

I am ordinary yet unique.