数学排列组合

本文主要是介绍数学排列组合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

我突然想发一篇文章(别问我为什么[doge])

排列组合大家都听过吧,今天的主角就是排列组合。

废话不多说,直接开始

先来看几道题目：

$T_1$ :由1，2，3，4组成不同的三位数有几种?

$T_2$ :有四个人，每两个人都要握手一次，要握几次手？

排列组合公式部分

排列部分

第一道是排列问题，其实是想让你求1234四个数中选三个进行排列，有几种排列?

题目解答

我们先来思考一下第一个数字选什么，有几种可能？显然，第一位有4种可能，因为四个数字都没有被选过且都可以选择。

第二位有 $\left ( 4-1 \right )$ 种可能，因为第一位选了一个数字，所以只有3种可能。

第三位有 $\left ( \left ( 4-1 \right )-1 \right )$ 种可能，第一和第二位选了两个数字之后只剩下了2个数字。

总共有 $\left ( 4*3*2 \right )$ 种可能。

至此，整道题目就做完了。

推出排列公式

我们不妨推想一下：排列又没有公式呢？如果有，那是什么呢？

如果是从n个选项里选择m个进行排列，一般情况下第一位有n种可能性，第二位有m种可能性，直到第m位有 $\left ( n-m+1 \right )$ 种可能性。总共有 $n\left ( n -1\right )\left ( n -2\right )...(n-m+1)$ 种可能性

我们把这个公式进行化简，先把它写成 $\frac{n\left ( n-1 \right )\left ( n-2 \right )...\left ( n-m+1 \right )\left ( n-m \right )\left ( n-m-1 \right )\left ( n-m- 2\right )...*1}{\left ( n-m \right )\left ( n-m-1 \right )...*1}$ 的形式，

可以发现，分子是 $n$ 的阶乘，分母是 $\left ( n-m \right )$ 的阶乘，所以这个式子可以变为 ${A_{n}}^{m} = \frac{n!}{\left ( n-m \right )!}$ 。

其中， ${A_{n}}^{m}$ 代表的是从n个数字中选择n个进行排列的总数。

所以第一道题的答案就出来了：

$Q_{1}$ : ${A_{4}}^{3} = \frac{4!}{\left ( 4-3 \right )!} = \frac{24}{1} = 24$

组合部分

第二道是组合问题，其实是想让你求四个人中选两个进行组合，有几种组合?

题目解答&推出公式

我们来想一下，排列和组合的区别是什么？其实排列注重顺序，而组合不管顺序。

观察可以发现排列数是组合数的两倍

为什么呢？

实际上，如果有n个数，抽出m个进行组合，组合数 * m个数的排列方案数 = 排列数

比如4个数抽3个，则 ${A_{4}}^{3} = {C_{4}}^{3} *{A_{3}}^{3}$

其中 ${C_{4}}^{3}$ 代表的是从n个数字中选择n个进行组合的总数。

原理：排列有多种方案，其中的一些方案是重复的，而组合中这些方案就变成一种方案了

那如何知道重叠的数量呢？推算呗！

~~呜呜呜，手都要废了~~

推算可得出，在n个数选m个数中，组合数* $m!$ =排列数

再联系排列的公式 ${A_{n}}^{m} = \frac{n!}{\left ( n-m \right )!}$ 可以算出 ${C_{n}}^{m} = \frac{{A_{n}}^{m}}{m!} = \frac{\frac{n!}{\left ( n-m \right )!}}{m!} =\frac{n!}{n!\left ( n-m \right )!}$

最终的公式为 ${C_{n}}^{m} = \frac{n!}{m!\left ( n-m \right )!}$

排列组合技巧部分

技巧一：整体捆绑法

我们来思考这样一道题：n名同学站成一排,m名同学要站在一起，有几种排列？

这就要用到整体捆绑法了。m名同学要站在一起，则可以将其变成一个人，有 ${A_{\left ( n-m+1 \right )}}^{\left ( n-m+1 \right )}$ 种排列。但是，这m名同学的顺序也是会变的，所以要乘上 ${A_{m}}^{m}$

公式就是 ${A_{\left ( n-m+1 \right )}}^{\left ( n-m+1 \right )}*{A_{m}}^{m}$

技巧二：选空插入法

还是来思考一道题：n名同学站在一起,其中m名同学不站在一起，有几种排列？

面对与上一题截然不同的题目要如何解决呢？这就要用到选空插入法了。

我们将其他的人先排序，就是 ${A_{\left( n-m\right )}}^{\left(n-m\right)}$ ,而其余的人呢？这就要用一种巧妙的思路了，

如下，设有七个人，其中两个人不站在一起，则将其余五个人的排列一下，再将那两个人插入空隙中，有 $\left ( 5+1 \right )$ 个空位，所以那两个人的所有排列就是 ${A_{\left ( 5+1 \right )}}^{\left(2 \right )}$ ,推导成通用公式是 ${A_{\left ( n-m \right )}}^{\left ( n-m \right )}*{A_{\left(n-m+1\right)}}^{m}$