排列组合
排列就是指从给定个数的元素中取出指定个数的元素进行排序;组合则是指从给定个数的元素中仅仅取出指定个数的元素,不考虑排序。--------OI Wiki
乘法原理和加法原理
加法原理,就好比一个工作,有 \(n\) 个解决的方案,第 \(i\) 项方案有 \(a_{i}\) 种不同的实现方式,所以这个工作有 \(a_{1}+a_{2}+a_{3}+\ldots+a_{n}\) 种方式来解决。
乘法原理,就好比一个工作,有 \(n\) 个步骤,第 \(i\) 步有 \(a_{i}\) 种方法来完成,所以这个工作的方式有 \(a_{1}\times a_{2}\times a_{3}\times \ldots \times a_{n}\) 种方式来解决。
排列数
给定 \(n\) 个数,从中选取 \(m\) 个数形成一个排列,可能的排列的数量,用 \(A_{n}^{m}\) 来表示(给定的数都为正整数)。
排列的计算公式:
\[A_{n}^{m}=n\times (n-1)\times (n-2)\times \ldots \times (n-m+1)=\frac{n!}{(n-m)!},n,m\in \mathbb{N^{*}},m\le n \]其实就是分子分母同乘一个 \((n-m)!\)。
其中 \(n!=1\times 2\times 3\times \ldots \times n\)。
全排列就是当 \(n=m\) 的时候的一种特殊情况,此时 \(A_{n}^{n}=n!\)。
组合数
区别就是,排列数是要求顺序的,而组合数是从 \(n\) 个元素里面选取 \(m\) 个数组成一个集合,问有多少种可能,通常用 \(C_{n}^{m}\) 来表示。
组合数计算公式:
\[C_{n}^{m}=\frac{n!}{m!(n-m)!} \]可以发现只比排列的公式分母多了一个 \(m!\),因为不考虑顺序,所以可以想到,挑出来的 \(m\) 个元素组成的集合,里面的排列数是 \(m!\),而这里面的元素组成的集合都是相同的,也就是这 \(m\) 个数本来应该算一个,但是排列里面是算了 \(m!\),所以排列的公式除以 \(m!\) 即为我们要求的答案。
现在人们习惯用 \(\binom{n}{m}\) 表示 \(n\) 个元素里面选 \(m\) 个,但是我个人觉得不如用 \(C_{n}^{m}\) 直观,但我们还是要了解这个表示方式。
标签:排列,入门,组合,数论,元素,个数,times,数学,ldots From: https://www.cnblogs.com/Multitree/p/17416800.html