一篇关于《数学密码学导论》第五章的review

未完待续。

1.组合数学

Abstract

分步用乘法，分类用加法。

1.0.基本计数原理

Example

Bob去一家餐馆吃饭，那里有两种前菜：鸡蛋卷和锅贴；以及20种主菜。Bob计划下单一种前菜和一种主菜，问题是：

Bob总共能下多少种可能的单？

很明显这个问题能被转化成计数一个2维向量 (x,y) 的所有可能取值，其中 x 的取值要么是0，要么是1。而 y的取值有不同的20种。

一个很无脑的解决这类问题的办法是穷举：

(0,0),(0,1),…,(0,19),

(1,0),(1,1),…,(1,19)

显然答案是40

更有效率的办法就是用基本计数原理来算：

2*20 = 40

这类问题可以推广到n维

1.1.(全)排列

Example

现在有一个数列包含10个不同的数字

S = {0,1,2,3,4,5,6,7,8,9}

把它们打乱，问题是：

总共有多少种排列方式?

显然是

$10! = 10*9*8...2*1 = 3628800$

可以把这个问题转化为计数一个10维向量 (a,b,…,j) 的所有可能取值

其中a的取值有10种，b的取值是除a以外剩下的9种……

所以运用基本计数原理，一共有

$S_{10}^{10} = 10*9*8...2*1 = 10! = 3628800$ 种

就算不是全排列，计算方式也一样。

比方说10个不同的元素但只要选取其中5个元素进行排列(构造一个5维向量)

答案就是 $S_{10}^{5} = 10*9*8*7*6$

即 $S_N^n = (N-0)*(N-1)*...*(N-n+1)$

(在本文中我用 $S_N^n$ 表示从N个不同的元素中选取其中的n个进行排列)

现在考虑一个数列中某些元素相同的情况：

S = {A,A,A,B,B}

有多少种不同的排列方式？

基本的思路是先计算全排列，再将重复计算的消去。

$S_5^5 = 5! = 120$

注意到，对于其中任意一种排列方式，调换两个B的顺序对结果没有影响。

现在仅考虑到2个B之间（相对）的排列，也就是

$S_2^2 = 2! = 2$ 种排列方式

这2种（相对）排列方式并没有区别，因此我们可以从 $S_5^5$ 中消去它

同理对于3个A，我们需要消去 $S_3^3 = 3! = 6$

最终答案是：

$\frac{S_5^5}{S_3^3*S_2^2} = 10$

注意到这里做了两次除法，而除法不太符合我的数学直觉，以下是我能给出的解释（以下内容脱离IMC范围，可略过）：

想要去重，符合直觉的做法是做减法，本质上是加上重复部分的加法逆元，再加1

（是否重复，很明显需要分类，所以这里用加法）

但这里A和B会共同影响最终的排列，我相信这么复杂的情况减法（本质是加法）不能胜任。

值得庆幸的是，我们有乘法。

思考一个简化的例子：

S = {A,A,A}

有多少种不同的排列方式？很明显是1种。

这是一个映射过程（我不了解映射，欢迎捉虫）：

我们的目的是把“重复部分”子集映射为{1}

$S_3^3 \mapsto 1$

如果你对数论或抽象代数敏感的话，很容易就会想到，1是乘法单位元，想要构造满足这样一个映射的式子，乘以乘法逆元就行。

具体式子是:

$f(S) = S*S^{-1}$

Input:S

Output: {1}

不难证明

$f(A*B) = A*B*A^{-1}*B^{-1}$

问题来了，怎么找乘法逆元？

这里我们只需要除以它本身（xgcd no need）

所以答案就呼之欲出了

先算全排列，这是一个包含”重复部分“子集的全集

然后把“重复部分”子集映射为{1}，就是答案

1.2.组合

简而言之，组合就是没有顺序要求的排列

Example

五个人(Alice,Bob,Carl,Dave,Eve)去一家餐馆吃饭，那里提供20种菜，他们决定每人点一份不重复的菜，问题是：

总共能下多少种不同的单？

如果沿用之前的公式，似乎答案是：

Alice先点，有20种选择，Bob再点，有剩下的19种选择……

$S_{20}^5 = 20*19*18*17*16 = 1860480$

但很显然，点单的顺序不应该影响最终的结果，比方说Alice点了炒饭而Bob点了蛋卷，与Alice点蛋卷而Bob点炒饭的结果是一样的。但在算排列的时候，很明显我们把这两种情况看作了不一样的而计算了多次。

那么，该如何计算组合呢?

基本的思路是先计算排列，再把顺序这个影响因子消去。

我们先来看看某一单（用五维向量表示），看看顺序对其的影响：

对于这个向量:{0,1,2,3,4},会因为数字排列顺序的不同产生多少种不同的向量呢?

这其实是一个排列的问题，问题可以转化为：

求集合 S = {0,1,2,3,4}的全排列。

答案很简单：5! = 120

回归到最开始的问题，不难发现，每一种菜单，都因为顺序问题而多算了119次，也就是说，

E被映射成了S，其中 #E = 1 ， #S = 120

(我们用 #S 表示 S 这个集合中元素的总数)

要去重，很简单，乘一下它的逆元就行了，所以最终答案：

$\binom{20}{5} = \frac{20*19*18*17*16}{5!} = 15504$

将其一般化，

$\binom{n}{r} = \frac{(n-0)*(n-1)*...*(n-r+1)}{r!}$

同时

$\binom{n}{r} = \frac{n!}{r!(n-r)!}$

我更偏好于用第一个公式来算组合问题，因为它更符合我的直觉。

1.3.二项式定理

为了更好地理解二项式定理，我们现在想象这样一个场景:

一个黑箱中有无数个黑球和无数个白球，现在从中取n个球，会有多少种情况？

不妨设 n = 4 来看看会发生什么

黑球	0	1	2	3	4
白球	4	3	2	1	0

很显然，当取到的黑球个数是0时，白球个数肯定是4，以此类推……

所以一共有5种情况

但我们不应满足于此，不妨预先思考下与概率论有关的问题：

这4种情况出现的概率一样吗？如果不一样，分别是多少？

不一样。朴素的数学直觉告诉我们，(2,2)出现的概率肯定最高，(3,1)和(1,3)次之，最后是(4,0)和(0,4).

这个问题的具体求解方法先按下不表，我们先将其转化为二项式的问题：

$(x+y)^4 = ax^4 + bxy^3 + cx^2y^2 + dx^3y + ey^4$

问题是:

$a,b,c,d,e$ 分别是多少？

我们当然可以将等式左边的括号一个个拆开来解决这个问题，但除此之外，有没有更普适的方法呢?

这其实是组合问题,只不过这里要算5次罢了

以a为例：

从(x,y)这个集合中选4次，选到的4次都是x，会有多少种情况?

无非是：第1次选到x，第二次选到x，第三次选到x，第4次选到x

$a = \binom{4}{4} = 1$

同理

$b = \binom{4}{1}$

$c = \binom{4}{2}$

$d = \binom{4}{3}$

$e = \binom{4}{0}$

所以，二项式定理的原理其实很简单，公式我从来没背过（高中时）