标签：... frac 组合 元素 基础 数学 取出 计算公式

排列数

定义

从 \(n\) 个不同元素中任取 \(m(n,m\in\mathbb{N}, m\le n)\) 个元素按照一定顺序排成一列，叫做从 \(n\) 个不同元素中取出 \(m\) 个元素的一个排列；从 \(n\) 个不同元素中取出 \(m\) 个元素的所有排列的个数，叫做从 \(n\) 个不同元素中取出 \(m\) 个元素的排列数，记作 \(A_n^m\)。

计算公式

排列数的计算公式如下：

\[A_n^m=n(n-1)(n-2)...(n-m+1)=\frac{n!}{(n-m)!} \]

其中 \(n!=\prod_{i=1}^{n}i\)。

组合数

从 \(n\) 个不同元素中任取 \(m(n,m\in\mathbb{N}, m\le n)\) 个元素组成一个集合，叫做从 \(n\) 个不同元素中取出 \(m\) 个元素的一个组合；从 \(n\) 个不同元素中取出 \(m\) 个元素的所有组合的个数，叫做从 \(n\) 个不同元素中取出 \(m\) 个元素的组合数，记作 \(C_n^m\)。

计算公式

组合数的计算公式如下：

\[C_n^m=\frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!} \]

其中，\(n!=\prod_{i=1}^{n}i\)。

对称性

\[C_n^m=C_n^{n-m} \]

递推公式

\[C_n^m=C_{n-1}^{m-1}+C_{n-1}^m \]

三种实现方法

1.递推公式/杨辉三角
根据组合数的递推公式 \(C_n^m=C_{n-1}^{m-1}+C_{n-1}^m\)，用二维数组存储如下所示：

1
1	1
1	2	1
1	3	3	1
1	4	6	4	1
1	...	...	...	...	1

其中，\(f[n][m]\) 表示 \(C_n^m\)。
此方法的时间复杂度和空间复杂度均为 \(O(n^2)\)，但其只需进行加法运算。

2.计算所有 \(n!\) 及其乘法逆元 \(n!^{-1}\)

标签：...,frac,组合,元素,基础,数学,取出,计算公式
From： https://www.cnblogs.com/catting123/p/18356899