方法复杂，不唯一。 • 奇数阶幻方的构造较简单，偶数阶较复杂。
幻方体
• n阶幻方体(magic cube)是以下述方式由整数1,2, …,n3构
造一个n×n×n立方阵列，其在下述每一条直线上的n个元 素的和s都是相同的： • (i) 平行于立方体一条边的直线； • (ii) 每个截面上的两条对角线； • (iii) 四条空间对角线。 • 数s叫做幻方体的幻和。 • 不存在2阶幻方体 • 也不存在3阶幻方体 • 证明不存在4阶幻方体要困难的多。 • 一个8阶的幻方体在Cardner的一篇论文中给出。
Nim取子游戏
• Nim取子游戏是由两个人面对若干堆硬币（或石子）进行 的游戏。设有k≥1堆硬币，各堆分别含有n1，n2，…，nk 枚硬币。游戏的目的是选择最后剩下的硬币。游戏规则如 下：
• 1. 两个游戏人交替进行游戏（游戏人I：第一个取子者； 游戏人II：第二个取子者）；
• 2. 当轮到每个游戏人取子时，选择这些堆中的一堆，并 从所选的堆中取走至少一枚硬币（游戏人可以取走他所选 堆中的全部硬币）；
有m1种不同的方法，在第二类办法中有m2种不同的方法，…，在第n类 办法中有mn种不同的方法，那么完成这件事共有N=m1+m2+m3+…+mn种不 同方法。
• 乘法原理做一件事，完成它需要分成n个步骤，做第一步有m1种
不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同 的方法，那么完成这件事共有N=m1×m2×…×mn种不同的方法。
含很多有趣的例子。 • 问题：用n2个整数1,2,…,n2构造一个n×n矩阵，
使每行、每列、对角线元素之和均相等。 • 这个相等的和叫做幻和。
幻方的问题
• 对任意的正整数n，n阶幻方存在吗？ • 对于某个正整数n，如果n阶幻方存在，有多少不同的形式？ • 构造存在的n阶幻方。
幻方
• 一阶幻方 • 二阶幻方不存在 • 三阶幻方 • 四阶幻方有880个 • 结论：对任意n≥1，n≠2，均可构造一个n阶幻方。但构造
• 主要内容：把有限集合的元素按一定的规则进行安排。 • 这种安排被考究地称为组态（Configuration）。
解决的问题
• 组态的存在性 • 组态的枚举、分类和计数 • 组态的构造 • 组态的优化
幻方
• 幻方是最古老最流行的一个数学游戏之一。 • 在中世纪时期曾存在与幻方相关的玄想，人们将
幻方佩戴身上辟邪。 • 本杰明·富兰克林就是一个幻方迷，他的论文中包
a
ASn aA
例题
• 设A,B为有限集，A = m, B = n。 • 从A到B的映射有多少个？ • 若m=n，则从A到B的双射有多少个？ • 若m≤n，则从A到B的单射有多少个？ • 若m≥n，则从A到B的满射有多少个？ • 集合B上的幂等映射有多少个？ • 集合B上的部分映射有多少个？ • 空映射
• 减法原理 • 除法原理
例题
• 137名运动员打乒乓球，单淘汰赛，问决出 冠军需要打多少场比赛？
• 方法一： • 方法二：
例题
• n元集合的子集有多少个？ • 加法原理 • 乘法原理 • 所有n长的0,1序列有多少个？
例题
• 求n元集合的含某固定元的子集的个数？ • 设Sn={1,2,…,n}，求
映射的个数
n元集上的幂等映射的个数 n元集上的部分映射的个数
n
C
k n
k
n
ห้องสมุดไป่ตู้

k
k 1
n
Cnk nk (1 n)n
k 0
例题
• 问题一：对三角形的三个顶点u,v,w染以红、蓝两 种颜色，求不同的染色方案数。
• 问题二：求集合{u,v,w}到集合{r,b}的映射的数目。
例题
• 问题1：求n元集合上有多少个不同的自反关系？
博弈论、线性规划以及许多其它领域都有联系。驳 杂 • 组合数学与计算机的相互促进关系。算法 速度
洛书、河图
• 洛书、河图是以不同形状、个数的黑白点排列的图案，并 有许多神秘的解释。
研究内容
• 组合数学与很多数学分支相交叉，因此很难对它下一个正 式的定义。
• 大体上说，组合数学是研究离散结构的存在、计数、分析 和优化等问题的一门学科。
组合数学 Combinatorics
教材
课程安排
• 组合数学简介 • 排列组合公式 • 母函数 • 递推关系 • 容斥原理 • 抽屉原理 • Polya计数
组合数学简介
• 组合数学也称为组合分析或组合学，按研究的对象 归于离散数学家族。
• 早在中国古代的洛书、河图中就有组合数学的思想。 • 组合数学的历史渊源扎根于数学娱乐和游戏中。 • 现代组合数学在纯粹和应用科学上都有重要的价值。 • 组合数学与抽象代数、拓扑学、数学基础、图论、
• 3.当所有的堆都变成空堆时，最后取子的游戏人即为胜者。
• 对应的组合问题是，确定游戏人I获胜还是游戏人II获胜， 以及游戏人应该如何取子才能保证获胜（获胜策略）。
Nim取子游戏
• 一堆硬币的情况 • 两堆硬币的情况
两堆硬币数相同 平衡 两堆硬币数不同 不平衡 • 结论： 平衡游戏，II按照I取子数量在另一堆中取子即可获胜； 不平衡游戏，I从大堆中取走硬币使两堆数量相等，后I每 次取子数量与II相同，I即可获胜。 • 用二进制表示 • k堆情形：平衡与不平衡 • 结论：游戏人II能够在平衡游戏中获胜，游戏人I能够在非 平衡取子游戏中获胜。
集合论
• 集合中元素个数的定义（集合的势） • 一一对应的思想 • 有限集 • 无限集 • 可数集(可列集)
常见数集的势
• 正偶数集与正整数集 • 两个可数集的并仍为可数集 • 可数个可数集的并仍为可数集 • 自然数集与有理数集 • 实数确实比自然数多
四个基本的计数原理
• 加法原理 做一件事，完成它可以有n类办法，在第一类办法中
• 问题2：求n元集合上有多少个不同的对称关系？
棋盘的覆盖问题
• 用1×2格的骨牌覆盖8×8棋盘。 • (1) 能否在棋盘上放置32个骨牌使之完全覆盖该棋盘？ • (2) 若存在，则有多少种不同的完全覆盖？ • (3) 去掉了两个对角处格子的残缺棋盘，问能否用31枚骨
牌恰将其覆盖？
棋盘的覆盖问题
问题：证明用 形可以完全覆盖剪去任一小方格后得 到的(2n×2n-1)形棋盘。