加载中...

狭义的组合数学主要研究满足一定条件的组态(也称组合模型)的存在、计数以及构造等方面的问题。组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化(最佳组合)等。

本文是学堂在线《组合数学》课程的相关笔记。反正寒假还有两三周,想学些有趣的东西,于是来摸一摸。

不定期更新,也可能想起来就看一课,也可能就打游戏咕咕咕去了(

漫谈组合数学

本章是一些引入性话题的探讨,并不涉及过于严谨的证明.

幻方

[定义 幻方] 将 $1, 2, 3, \cdots, N^2$ 这些数字放入 $N \times N$ 的方格中,使得方格的每一行,每一列及两个对角线上的数字和相同,这样的方格称为 $N$​ 阶幻方

[定义 幻方的幻和] $N$ 阶幻方每一行或每一列的和,称为该幻方的幻和 $s$。

[定理 N 阶幻方的幻和] 若 $N$​​ 阶幻方存在,则其幻和 $s_N = \dfrac {N(N^2+1)} 2$​​.

证明:由于 $\sum\limits _{i=1}^{N^2}i=\dfrac {N^2(N^2+1)}{2}=N \cdot s_N$​,于是 $s_N = \dfrac {N(N^2+1)} 2$​. $\blacksquare$​

[定理] $2$ 阶幻方是不存在的.

证明:使用反证法,假设存在这样的 $2$ 阶幻方 $\begin{bmatrix}a & b \\ c & d \end{bmatrix}$,其中四个变量两两不等且 $\{a,b,c,d\} = \{1,2,3,4\}$,根据约束条件这四个变量两两相加为 $s_2 = 5$,该方程组无解,矛盾. $\blacksquare$​

[定理 幻方的存在性] 对于任意 $N \ge 3$,$N$ 阶幻方均存在。

证明:可以分 $N=2k+1, N=4k,N=4k+2$​​​ 三种情况进行讨论. 对于每一种情况均有相应的构造算法. 参考资料

[幻方的计数性] 如果两个幻方经过有限次翻转和旋转可以形成同样的排列,那么我们就认为这两个幻方是相同的. 那么对于 $N$​​ 阶幻方,定义其数目 $d_N$。可知 $d_2 = 0, d_3 = 1$。

苦难的羊皮纸卷

[阿基米德和他的十四巧板]

img

这个东西原名叫 Stomachion,阿基米德想知道这 14 块图形拼成一个正方形一共有多少种拼法。

2003 年 Bill Cutler 解答了这个问题,他算出一共有 17152 种拼法,其中有些是另一些的旋转或者镜像,再把这些合并之后,最终一共是 536 种不同的拼法。

你的手机密码安全吗

对比 iPhone 的四位 PIN 码(计数:$10^4$​ 钟)和 Android 的手势密码的个数。

如果选择的两个点连成的线段穿过了第三个点,而这第三个点之前没有被连过,那么则这种连接方式不合法。

如果如此计数,计 $s_N$ 为连接 $N$ 个点可以有的手势密码个数,那么 $s_4=1624, s_5=7152$​。

暴力枚举与抽象转换

[一一对应] 如果 224 个国家来打锦标赛,那么一共需要进行 223 场比赛。这是因为每场比赛会且仅会淘汰一只队伍,一旦建立如此一一对应关系即可得到答案。

[七桥问题与欧拉路] 欧拉在解决七桥问题的同时提出了欧拉路的定义及欧拉道路的存在性定理。

小结

组合数学是研究计数的问题,要达到的目的是无重复,无遗漏。计数需要足够有效的抽象,还需要高效的工具—— 计算机。