一、引论，《组合数学(第4版)》卢开澄 卢华明

零、前言

发现自己数数题做的很烂，重新学一遍组合数学吧。

参考卢开澄 卢华明 编著的《组合数学(第4版)》，只打算学前四章。

---

通过几个经典问题来了解组合数学所研究的内容。

一、幻方问题

据说大禹治水之前，河里冒出来一只乌龟，龟背上是一个3*3的矩阵，每个格子里面有若干点，行和列和对角线和都相等且为15。然后大禹就以15为周期来治水了。

对于一个nxn的矩阵，满足行和，列和，主副对角线和都相等，那么这个矩阵就是一个n阶幻方。

最早研究幻方的是南宋的杨辉（杨辉三角那个），他罗列了3x3、4x4、5x5甚至10x10的幻方。

定义：行/列整数和为该幻方的幻和。

n 阶幻方的幻和为 (n^2 + 1) * n / 2

并非任意阶幻方都有解法：

2阶幻方就不存在：

会推出某两个元素相等，但是a b c d 互不相同。

大约30年前，德国数学家L · Bieberbach证明：

对于任意大于等于 3 的数 n，都存在一个 n 阶的幻方阵。

杨辉提出了一种三阶幻方的构造方法：

• 123、456、789 斜着摆三列，得到一个菱形
• 交换菱形对角元素，挤压成一个正方形，就是一个三阶幻方

但是对于更高阶该如何构造呢？

法国一位数学家研究了奇数阶幻方的一般化构造方法：

• 记第 i 行 第 j 列 方格坐标为 (i, j)，0 索引
• 初始将 1 放在第 0 行的中间 (0, n / 2)
• 对于 当前要放置的棋子，上一枚棋子的坐标为 (x, y)
• 我们尝试放在 ((x - 1) % n, (y + 1 % n))
  • 如果已经被占用，则放在 ((x + 1) % n, y)
• 证明略

事实上，我们可以将幻方分成三类：

• 奇数阶幻方
• 4m 阶幻方
• 4m + 2 阶幻方

每一类都有对应的构造算法。

然而我们发现杨辉构造的三阶幻方和奇数阶构造算法得到的幻方不同，但是把幻方上下翻转就相同了。

这让我们思考，对于n阶幻方有多少种构造方法？

三阶幻方，如果认为翻转旋转一样的话，只有一种。

四阶幻方，如果认为翻转旋转一样的话，有880种，否则有7040.

五阶已经有 2亿七千多万个了。

六阶数学家大概确定了其数量落在某个范围，七阶已经无从得知了……

可见，计数问题是组合数学中的一大难题。

算竞中经常遇到这样一类构造题：行列乘积、gcd、异或等限制来构造矩阵，这其实都是幻方的变形。

二、羊皮纸卷

阿基米德在羊皮纸上的论文流落到寺庙，僧人清洗后重新抄写经文。

2003年，科学家通过X光照射，发现羊皮纸经文下面的阿基米德关于十四巧板的论文。

一位数学家以此为题，设置100美元奖项，谁先解出来给谁。

然后计算机学家借助计算机设计算法解出来是17152种，后来数学家利用排列组合的方式，也得到了正解。阿基米德无意间开创了西方世界的组合数学的篇章。

1666年，莱布尼茨研究概率学时，生造了**组合数学（Combinatorics）**这个单词。

三、手机密码安全吗

平时在学校基本都是翘课，有一次遇到学习通4位密码签到，我一看乐了，整个程序暴力枚举，几乎一瞬间就签上到了。

为什么这么快呢？

4位密码，每位10种可能，也就10000种，计算机基本几毫秒就能枚举完所有可能。

很多人手机都有3 * 3 的手势密码，其实手势密码可以看作是从一个格子出发得到的一条路径，我们怎么计数呢？

正难则反，总情况 - 不合法路径。

不合法的定义：如果选择的两个点连成的线段，穿越了第三个点，如果这第三个点，之前没有被连过，则不合法；反之，则合法

通过计算机程序得到一共有 389112 种方案。

可见，如果手机没有输入次数限制的话，一部手机很快就能被破解。

计数问题是一类很常见的问题，但是并不简单，如何做到不重不漏，是一个难点。

四、世界杯引出的问题

n 支球队参加比赛，一共需要多少场复赛？

比较笨的方法：局面抽象成节点，代表当前剩下的队伍集合，挑出两个队伍比赛，扔掉一个败者，得到新的节点，最后节点的数目就是总比赛场数。

但事实上，每进行一场比赛都会产生一个败者，一个胜者，我们最后只有一个冠军，所以要进行n - 1场比赛。

可见同样是计数问题，不同方法的效率是天差地别的。

五、哥尼斯堡七桥问题

即欧拉路径问题：欧拉图，欧拉通路，欧拉回路，Hierholzer算法详解-CSDN博客

沿着桥走，每个桥恰好走一次有多少种走法？

我们能直接取排列数作为答案吗？

显然不能，太多非法解了。

不过我们可以借助定理 + 计算机枚举来求解。

通过定理，我们保证枚举方案的合法性，可见有技巧的枚举可以更加精巧简洁。