组合数学基础 / 排列组合

QAQ_juruo · 2024-08-31 09:54:36 · 算法·理论

\text{0x01 }\small\texttt{基本概念}

排列组合的问题是研究给定要求的排列和组合可能出现的情况总数。

排列：指从若干元素中取出其中一部分元素进行排序；

组合：指从若干元素中仅取出一部分元素。

\text{0x02 }\small\texttt{基本原理}

此原理主要是为了应对各种题型的方法。

\small\texttt{加法原理}

指一个任务有 n 个不同的方法，定义 m_i(1\le i \le n) 表示第 i 种方法的情况，那么整个任务的情况总数为 m_1+m_2+m_3+...+m_n，即 \sum\limits^{n}_{i=1}m_i。

\small\texttt{乘法原理}

指一个任务需要 n 个步骤，定义 m_i(1\le i \le n) 表示第 i 个步骤的情况，那么整个任务的情况总数为 m_1\times m_2\times m_3\times ...\times m_n，即 \prod\limits^{n}_{i=1}m_i。

\text{0x03 }\texttt{\small排列组合数}

\small\texttt{排列数}

一个排列数 A^m_n 表示从 n 个元素中取出 m(m\le n) 个元素并进行排列的个数。

那么它的结果如何计算呢？举个例子：

• 你现在有 5 个数：

  1,2,3,4,5

  现在你想知道取 m(n\le5) 个数排列有多少种情况。

• 第 1 步：你可以选 5 个数，也就是说，这一步有 5 个情况。

• 第 2 步：由于上一步选出了一个数，还剩 4 个数，这一步有 4 个情况。

• 第 3 步：上一步再次选出了一个数，还剩 3 个数，有 3 个情况。

以此类推，直到第 m 步，还剩 5-m+1 个数，有 5-m+1 个情况。

也就是说，根据乘法原理，选 m 个数会有 5\times4\times...\times 5-m+1 种情况。

推广一下，从 n 个数选 m 个数会有

种情况。

特别地，n=m 时 A^n_m=A^n_n=n!。

\small\texttt{组合数}

先咕咕咕。