组合数学学习

简介

被数竞dalao虐惨了QAQ,好好学组合数学
<巨坑待填>

第一章 什么是组合数学

  • 第一个栗子: 棋盘的完美覆盖

考虑一张棋盘,假设有一些形状相同的1*2的多米诺骨牌,是否能在没有两张牌重叠,且在每张牌覆盖两个方块的条件下覆盖棋盘上的所有方格

对于完美覆盖是否存在,我们可以将棋盘用橙色绿色来交替染色,如果两种颜色染的数量不相同,则不存在完美覆盖

将多米诺骨牌覆盖两种颜色扩展到b种颜色,即采用1*b的骨牌进行覆盖,有以下结论:

m*n棋盘有b格牌的完美覆盖当且仅当b是m的一个因子或者是n的一个因子
如果完美覆盖中所有b格牌都是水平放置或者所有b格牌都是垂直放置,则称这样的完美b格牌覆盖是平凡的,于是m*n棋盘有b格牌覆盖的完美覆盖当且仅当它有平凡覆盖

  • 第二个栗子: 幻方

n阶幻方中所有整数的和是

$1\ +\ 2\ +\ 3\ +\ …\ +\ n^2\ =\ (\frac{n^2\ *\ (n^2\ +\ 1)}{2})$

la Loubère构造法(n为奇数)

先把1放在第一行的中间,之后的整数按照它们的自然顺序放置在从左下方到右上方的一条对角线上,做如下修正:
(1)当到达第一行时,下一个整数的放置位置使: 它所处的行是最后一行,所处的列是紧跟着前一个整数所处列的后面一列
(2)当到达最右边的一列时,下一个整数的放置位置是: 它所处的列是最左边的列(即第一列),它所处的行是紧跟着前一个整数所处行的下一行
(3)当达到一个已经填上数的方格或者已经达到幻方的右上角时,下一个整数放置的位置是填写上一个数的方格的直接下方

简而言之,对于当前的格子(x, y),下一个数字放置的位置就是当前格子的右下方(x + 1, y + 1),如果超出范围就重新回到最左边或者最上边,如果(x + 1, y + 1)格子已经被填就填在当前格子的正下方(x + 1, y),超出范围同上处理

以上是一个根据la Loubère构造法构造的一个五阶幻方

  • 第三个栗子:四色问题

仅用四种颜色便可以给每一张平面地图着色

  • 第四个栗子:36军官问题

看不懂QAQ(待填坑)

  • 第五个栗子:最短路径问题

假装跑个dijkstra(等学了组合数学中图那套理论再回来看)

  • 第六个栗子:相互重叠的圆

考虑平面上以相互重叠的n个圆$\gamma_1,\gamma_2$,…,$\gamma_n$。
将互相重叠定义为每一对圆相交于两个不同点

如此构造的区域的数量$h_n = n^2 - n + 2$

  • 第七个栗子:Nim游戏
文章目录
  1. 1. 简介
  2. 2. 第一章 什么是组合数学
    1. 2.1. 考虑一张棋盘,假设有一些形状相同的1*2的多米诺骨牌,是否能在没有两张牌重叠,且在每张牌覆盖两个方块的条件下覆盖棋盘上的所有方格
    2. 2.2. 将多米诺骨牌覆盖两种颜色扩展到b种颜色,即采用1*b的骨牌进行覆盖,有以下结论:
    3. 2.3. n阶幻方中所有整数的和是
    4. 2.4. la Loubère构造法(n为奇数)
,