排列数（以及排列数公式的推导过程）

小甲鱼

排列数（以及排列数公式的推导过程）

对于 4 位数密码，由 0~9 的数字组成，因此每一位都有 10 种选择，请问有多少种可能的排列？

这是咱们在 这 10 道关于排列数的难题，在生活中我们时常会遇到，你都能解答出来吗？ 中的一道题目，

你能算出来答案是多少吗？



答案是 10000

想要解答这个问题，就需要用到排列数的概念啦~

什么~~~

你不知道排列数也能算出答案？

那不妨试试这道题：

在一家餐厅里，厨师长考虑将 10 道菜品放入包含 3 道菜的套餐中，需要计算所有可能的菜单排列（菜品顺序在菜单中很重要，所以 A、B、C 与 C、B、A 是不同的套餐），请问共有多少种不同的菜单排列？

答案是 720

如果不知道结果是怎么算出来的，那就让我们开始今天的数学之旅吧~




排列数的概念

排列数（Permutation）是组合数学中的其中一个概念，

它表示从 n 个不同元素中取出 m 个元素（m ≤ n）进行有序排列的所有可能性。

注意：在排列数中，元素的顺序是需要考虑在内的（也就是说即使元素相同，但排列顺序不同，也会被视为是不同的排列）。

举个简单的例子，假设我们有三个不同颜色的小球：



当我们从中拿出 1 颗小球时，那么可能是拿到 A，也可能是拿到 B，当然 C 也是有可能被拿到的，所以有 3 种不同的组合（此时排列数为 3）

当我们从中拿出 2 颗小球时，那么所有存在的可能性是： AB、BA、AC、CA、BC，一共有 6 种不同的组合（此时排列数为 6）

当我们从中拿出 3 颗小球时，那么所有存在的可能性是：ABC、ACB、BAC、BCA、CAB、CBA，一共也是有 6 种不同的组合（此时排列数也为 6）

上面这种是穷举法~

也就是暴力解决问题的方法~

一般当我们面对一个未知的事物，

自身所拥有的能力无法予以实现时，

通常我们就会诉诸于暴力来解决问题

OK，其实我们有更 “聪明” 的解决方案~

使用排列数公式：



表示从 n 个不同元素中取出 m 个元素（m ≤ n）进行有序排列的所有可能性。


阶乘!

大家看到排列数公式了，这里面的感叹号并不是 “哇塞” 的意思，它其实是阶乘的数学表示方式~

n! 表示n的阶乘，表示从 1 乘到 n 的结果。

例如：

0! = 1

1! = 1

2! = 2 × 1

3! = 3 × 2 × 1

4! = 4 × 3 × 2 × 1

5! = 5 × 4 × 3 × 2 × 1 = 120

...

当我们从中拿出 1 颗小球时，n = 3、m = 1，代入公式的计算过程是：



当我们从中拿出 2 颗小球时，n = 3、m = 2，代入公式的计算过程是：



当我们从中拿出 3 颗小球时，n = 3、m = 3，代入公式的计算过程是：



注1：如果对于 0! = 1 的结果有疑惑的鱼油，可以看一下这篇文章 -> 传送门

注2：本文所有的感叹号（!）均表示某个数的阶乘，为了防止大家误读，小甲鱼会使用波浪号来代表小甲鱼很惊讶~


排列数公式的推导过程

接下来我们讲解排列数公式 P(n, m) = n! / (n-m)! 的推导过程。

还是刚刚 3 颗小球的例子，

第一种情况，从 3 颗小球中拿出 1 颗，那么我们有 3 种选择：



第二种情况，从 3 颗小球中拿出 2 颗，第一个位置仍然有 3 种选择，但第二个位置就只有 2 种选择了（因为第一个位置拿走了一颗小球）：



对于这种情况，那么总共的选择数量就是 3 × 2 = 6

第三种情况，同样的道理，如果要从 3 颗小球中拿出 3 颗，那么就是这个样子：



总共的选择数量就是 3 × 2 × 1 = 6

那这个跟公式推导有什么关系呢？

P(n, m) 表示从 n 个元素中拿出 m 个元素，一共有多少种不同的选择。

从第三种情况来看，n = 3、m = 3，那么公式就是 P(n, m) = n!

但是这个公式只能解决满选满配的情况，

如果是从 n 个元素中拿出部分元素 m（即 m < n），这个公式就不能用了~

我们需要设计一个通用的公式才行~

考虑第二种情况，n = 3、m = 2，那么公式 P(n, m) = n × (n-1) = 3 × 2

相当于少了一位，对吧？

是不是就相当于：



再考虑第一种情况，n = 3、m = 1，那么公式 P(n, m) = n = 3

相当于少了两位，对吧？

那我们是不是可以得到公式：



OK，现在思路逐渐清晰起来了~

P(3, 3) 刚刚我们已经推论过了，就是 3!

现在重点是下面除数是什么？

你看，少了两位就是 1（因为总共只剩下一个位置），少了一位就是 2 × 1（因为总共剩下两个位置）

所以除数其实就是 (n - m)!

那么合起来就是我们公式啦：



搞定~

不二如是

学会「排列数」鱼油将收获：

• 排列数可以用来计算组合数，组合数是指从n个元素中取出m(m≤n)个元素的所有排列方式的数量，因此排列数可以用来计算组合数。
• 排列数在密码学中有重要的应用。在密码学中，分组密码和凯撒密码都需要用到排列数，比如分组密码中的移位密码和凯撒密码中的轮替密码都需要用到排列数的相关知识。
• 排列数可以用来求最长公共子序列（LCS），最长公共子序列是指在两个序列中，共有m+1个元素，其中一个序列的所有元素都是另一个序列的m+1个元素中的一部分，且这些元素按照一定的顺序排列。求最长公共子序列的过程就是求两个序列的排列数的过程。
• 排列数还可以用来检测数据的离散程度。比如，在区间[0, 1)中，可以将数据按照升序排列，然后统计数据的排列数，如果排列数的值很大，那么就可以认为这个区间中的数据是比较离散的。
• 排列数在计算机科学中也有应用。比如，在计算机程序中，可以使用排列数来生成电路，从而实现逻辑门电路的功能。
  

因此，排列数在各个领域都有广泛的应用，可以帮助人们更好地理解和应用数学知识，同时也可以让计算机更好地实现功能。

鱼C-小师妹

非常清晰

鱼小二

斯国一

爱吃梨的猩猩

比我数学老师说的还好

lonely_xiaoying

推导过程看起来好厉害的样子

shibaideman

很详细，感谢小甲鱼

zhuyanan

发现排列数和随机数中random.sample(population, k)有一些关联   排列数抽取小球放回 可以计算有多少种结果，而彩票采用的sample ()函数是抽取小球不放回  完成是结果  一个是计算抽取放回有多少种结果   一个是抽取不放回最后抽取的结果。

鸡你实在太没

很详细

shane9611

推导过程简单易懂，学到了～（没想到在这里还能学数学哈哈）

xyt210819

我上学的时候数学没学好，研究了好一会，还是没搞懂，我还得好好在研究研究，不过已经讲的很详细了，感谢小甲鱼

面对巨人

讲的很详细

凌凌祺

赞同！赞同！支持

凌凌祺

要学数学啦

tsElim

高中数学里的排列组合