计数原理 学习笔记

模板及讲解
排列

一般地,从$n$个不同元素中取出$m(1≤m≤n)$个元素,按照一定的顺序排成一列,叫做从$n$个元素中取出$m$个元素的一个排列(顺序不同是不同的两种方案)
(约定$0!=1$)

1 无重排列
从$n$个不同元素中有序且不重复取出$k(1≤k≤n)$个元素,称为$n$个不同元素中取出$k$个元素的一个无重排序,简称k-排列,所有这样的排列个数记为$A^{k}_{n}$
$$A^{k}_{n} = \frac{n!}{(n-k)!}$$
2 全排列
(1) 无重
当k-排列中的$k=n$时
$$A^n_n=n!$$

3 重复排列
从$n$个不同元素中有序且可重复取出$k(1≤k≤n)$个元素,称为$n$个不同元素中取出$m$个元素的一个无重排序,简称k-可重排列
重复排列个数为
$$n^k$$

4 圆周排列
从$n$个不同元素中无重复地取出$k(1≤k≤n)$个元素排在一个圆周上,称为$n$个不同元素的一个圆周排列,简称k-圆排列
圆周排列个数为
$$\frac{A^k_n}{k} = \frac{n!}{k\cdot(n-k)!}$$


组合

一般地,从$n$个不同元素中取出$m(1≤m≤n)$个元素组成一组,叫做从$n$个元素中取出$m$个元素的一个组合(顺序不同是相同的两种方案)
(约定$0!=1$)

1 无重组合
从$n​$个不同元素中无序且不重复取出$k(1≤k≤n)​$个元素,称为$n​$个不同元素中取出$k​$个元素的一个无重组合,简称k-组合,所有这样的排列个数记为$C^{k}_{n}​$

$$C^{k}_{n} = \frac{A^k_n}{A^k_k}=\frac{n!}{k!(n-k)!}$$
$$C^k_n=C_{n-1}^{k-1}+C_{n-1}^{k}$$(递推算法,杨辉三角)

2 重复组合
从$n$个不同元素中无序但可重复取出$k(1≤k≤n)$个元素,称为$n$个不同元素中取出$k$个元素的一个重复组合,简称k-可重组合
重复组合个数为
$$C^{k}_{n+k-1}=\frac{(n+k-1)!}{k!(n-1)!}$$

3 组合数性质
$C^k_n = C^{n-k}_n$
$C^k_n = C^{k-1}_{n-1} + C^{k}_{n-1}$
$C^k_n = C^{k-1}_{n-1} \times n \div k$
常见题型:

------ 本文结束 ------