第1章 基本计数技术
　　众所周知， 组合数学的研究对象是有限或可数的离散结构， 其研究目标之一就是在给定的准则下对结构进行计数和枚举. 为此， 组合数学中有许多技术和方法用于这两个目的. 单就计数来说， 就有许多非常精巧的计数方法， 但是排列与组合的计数是最直接和最基本的， 也是应用最为广泛的. 例如， 在古典概率论领域里的概率计算主要就是排列与组合的计算. 本章主要介绍一些基本的计数原理以及排列与组合的计数和枚举， 尽管可能有相当大的一部分内容读者已经很熟悉， 我们仍然予以完整介绍. 鉴于本书涉及的许多计数问题均与图有关， 因此我们将在介绍这些基本的计数技术之前， 用一节的篇幅介绍图论中关于图的一些基本概念， 以方便读者理解与图相关的计数问题. 建议读者有选择地阅读本章内容， 特别需要关注的是一些问题的叙述方式及所使用的符号， 它们也将会频繁地出现在本书的其余部分.
　　1.1 图的基本概念
　　图论中涉及许多有关图的概念， 所以我们这里并不打算一次性地将所有概念呈现出来， 一是内容太多， 二是没有必要. 因为我们的目的仅仅是服务于将图作为计数对象的需要， 并不是完整介绍图论的内容， 所以我们采用按需的策略， 先介绍一些最基本的概念， 然后在需要的时候再介绍相关内容.
　　1.1.1 图的定义
　　一个图G由集合V及其二元子集E构成， 其中集合V称为顶点集， V中的元素称为顶点; 集合E称为边集， E中的元素称为边. 因此， 一个图G常用二元序偶 (V，E) 表示. 对于没有显式给出顶点集和边集的图G， 常用V (G) 表示图G的顶点集， E(G) 表示图G的边集. 如果图G的顶点集V是有限集， 则称G是有限图， 并称顶点数jV j是图G的阶 (jV j表示集合V中的元素个数， 下同)， 而称边数jEj为图G的大小. 如果jV j=n， jEj=m， 则也称图G是一个 (n，m) 图. 如果V是无限集， 则称G为无限图. 如果jEj=0， 则称G为零图; 如果jV j=0， 则称G为空图. 两个图G和H相等， 记为G=H， 当且仅当V (G)=V (H)， E(G)=E(H).
　　如果图G=(V，E) 的边集E中每条边e都有一个实数W(e) 与之关联， 则实数W(e) 一般称为边e的权， 并称图G为赋权图， 记为G=(V，E，W); 赋权图也称为网络. 如果边集E中所有边均有方向， 则称G是有向图; 如果E中一部分边有方向， 另一部分边没有方向， 则称G是部分有向图或混合图; 如果E中所有边均没有方向， 则称G是无向图. 对于有向边e， 记为e=(u， v)， 其中u， v 2 V ; 如果e是无向边， 则记为e=fu， vg， u， v 2 V . 无论边e是有向边 (u， v) 还是无向边fu， vg， 都称边e关联顶点u和顶点v， 也称顶点u和v关联边e. 如果顶点u和v关联同一条边e， 则称顶点u和v是相邻的. 如果两条边e1 和e2关联到同一个顶点v， 则称边e1 和e2 是相邻的. 如果边e关联到同一个顶点v， 即e=(v， v) 或e=fv， vg， 则称边e是一个自环. 如果有两条或两条以上的边关联到同一对顶点， 则称这样的边为重边. 没有重边和自环的图称为简单图， 否则称为重图. 如果没有特别说明， 我们所讨论的图都是有限的简单无向图. 在不至于混淆的情况下， 为了简便， 我们将边e=fu， vg或e=(u， v) 简记为uv.
　　设G=(V，E) 是无向图， 对于v 2 V ， 与顶点v邻接的顶点集合称为顶点v的邻域， 记为N(v); 有时我们也记为NG(v)， 以强调是图G中的顶点. 有时也用N[v]和NG[v] 来表示包含顶点v自身的邻域， 即N[v]=N(v) [ fvg， NG[v]=NG(v) [fvg. 顶点v所关联的边数称为顶点v的度， 记为deg(v)， 即deg(v)=jN(v)j. 如果， vng， 则称fdeg(vi)gni=1 为图G的度序列. 可通过选择顶点的编号， 使得度序列呈递增或递减的序列. 对于有向图G， 从顶点v引出的边数称为顶点v的出度， 记为deg.(v); 而进入顶点v的边数称为顶点v的入度， 一般记为deg+(v)， 并以入度deg+(v) 和出度deg.(v) 之和作为顶点v的度， 即deg(v)=deg+(v) + deg.(v). 图G中所有顶点度的最小值记为 δ(G)， 最大值则记为 Δ(G). 度为零的顶点称为孤立顶点. 零图中的每个顶点都是孤立顶点. 对于某个正整数k， 如果 δ(G)=Δ(G)=k， 即图G中每个顶点的度均为k， 则称图G是k正则图.
　　对于简单图， 无论是有向图还是无向图， 其中的每条边对顶点度的贡献都是 2. 因此， 下面的结论是显然的， 并且一般将其称为图论定理.
　　定理 1.1 设G=(V，E) 是一个简单图 (有向或无向)， 那么有
　　这个定理有时也称为握手定理， 意思是指在任何会议上所有人的握手次数之和为偶数， 也意味着任何图中度为奇数 (奇度顶点) 的顶点数为偶数. 对于一个 (n，m) 图G， 根据握手定理可得
　　1.1.2 图的连通性
　　设G=(V，E) 是一个简单无向图， 且jV j=n， 如果V中的任何两个顶点都有一条边关联， 则称G是一个n阶完全图， 一般记为Kn; n阶零图记为Nn. 在简单图G中， 始于顶点v0 终于vk的顶点与边的交错序列， 其中的边ei (1 . i . k) 关联顶点vi.1 与vi， 则称Wk为一条从v0 到vk的道路， 简记为v0 vk道路， 其中k称为道路的长度， 即道路的长度就是道路中包含的边的条数. 显然， 一条v0 至vk长度为k的v0 vk道路， 也是一条vk至v0 长度为k的vk v0 道路. 如果道路Wk中v0=vk， 则称道路Wk为回路. 如果道路Wk中的诸顶点彼此不同 (因而诸边必然不同)， 则该道路为一条简单道路; 长度为k 1 的简单道路记为Pk. 如果Pk+1 中的顶点v0=vk， 则称简单道路Pk+1为一个k阶环， 一般记为Ck; 如果k为奇数， 则称Ck为奇环; 否则称为偶环. 实际上， 环就是简单回路. 如果简单道路Pk中的顶点集， vk.1g=V ， 则 称简单道路Pk为图G中的一条Hamilton道路; 如果Hamilton道路Pk中的v0=vk.1， 则称Pk为Hamilton回路. 如果道路Wk中的边彼此不同， 且这些边构成的集合， ekg=E， 则称Wk为Euler道路; 如果Euler道路Wk中的v0=vk， 则称Euler道路Wk为Euler回路. 图 1.1 展示了几个特殊图K6， C6， P6 以及N10.
　　图1.1 特殊图K6， C6， P6 以及N10
　　设G=(V，E) 是一个图， 如果对于V中任何两个顶点u和v， 均存在一条始于u终于v的u v道路， 则称图G是连通的; 否则称G是非连通的. 如果图G是一个连通图， 且jE(G)j=jV (G)j 1， 则称图G是一棵树. 容易看出， 树是一个具有最少边数的连通图， 即如果从树G中去掉任何一条边e(记为G e)， 则G e不再是一个连通图. 反过来， 如果向树G中增加任何一条边e(记为G+e)， 则G+e中必存在环或回路. 一般在绘制树图时， 习惯将树中的一个顶点v安排在最上面， 并称其为树根; 而将所有与v相邻的顶点安排在v的下面， 并称其为树根v的孩子或后继， 相应地称树根为这些孩子的父亲或前驱; 类似地， 每个孩子也是其后继顶点的前驱， 因此每个孩子及其后继顶点也是一棵树， 称其为树根v的子树. 因为树具有天然的递归结构， 许多文献就采用递归的方式来定义树. 树中除树根顶点v之外满足deg(u)=1 的顶点u称为树叶. 如果树根顶点v满足deg(v)=1， 则称这棵树是一棵人工树， 即人工树的树根只有一棵子树. 如果树中除树叶外每个顶点至多有k个子树， 则称树是一棵k叉树; 如果树中除树叶外每个顶点恰有k个子树， 则称树是一棵完全k叉树. 如果人工树的树根顶点v的子树是一棵完全k叉树， 则称其为人工完全k叉树. 如果区分子树的顺序， 即不同的子树顺序表示不同的树， 则称树是有序树 (有序树也称为平面树)， 否则称其为无序树.
　　图 1.2 所示的两棵树， 其树根顶点均为 6. 如果将它们看成是有序树， 则是两棵不同的有序树; 如果看成是无序树， 则这两棵树是同一棵树.
　　图 1.2 有序树和无序树
　　如果图H满足V (H) V (G)， E(H) E(G)， 则称H是G的子图， 一般记为H G. 如果H G， 且V (H) V (G) 或E(H) E(G)， 则称H是G的真子图， 记为H G. 如果H是G的一个完全子图， 则称H是G中的一个团; G中最大团的阶数称为G的团数， 记为 ω(G).
　　设H G， 对于 8 u， v 2 V (H)， 如果fu， vg 2 E(G)， 那么fu， vg 2 E(H)，则称H是由V (H) 导出的子图， 并将其记为G[V (H)]. 如果H G， 且V (H) =V (G)， 则称H是G的生成子图， 记为H . G; 如果生成子图H是一棵树， 则称H是图G的生成树. 设图G是非连通图， H是G的连通子图， 如果对任意的边e 2 E(G) E(H)， 图H + e是非连通的， 则称图H是图G的一个连通分支; 图G中连通分支的个数记为k(G).
　　下面的定理给出了图连通的充分条件.
　　定理 1.2 设图G=(V，E) 是简单无向图， 且jV j=n. 如果对于V中任意的两个不邻接顶点u， v均满足
　　则图G一定是连通的.
　　证明 显然， 我们只需证明 8 u， v 2 V ， 存在一条u v道路即可. 事实上， 如果 ， 结论自然成立. 如果u与v不邻接， 则由于，所以必存在一顶点w 2 V使得uw 2 E， wv 2 E， 由此即得一条u v道路. 因为否则就有， 此时必有， 矛盾.
　　注意定理 1.2中的条件只是一个充分条件而非必要条件， 因为当n . 6 时， Cn是连通图， 但对 8 u， v 2 V (Cn) 均有而当n . 4时， 连通图Pn的始点u与终点v满足.
　　如果图G满足jV (G)j=n， Kn是以V (G) 作为顶点集的完全图， 如果同样以V (G) 作为顶点集的图H满足
　　则称图H为图G的补图， 并将H记为G. 显然， Kn的补图Kn是n阶零图Nn. 如果G是连通的， 则G可能是连通的， 也可能是非连通的. 例如， 图 1.3 中的图G1 与G2 是连通的， 但其补图G1 是连通的， 而补图G2 却是非连通的. 但容易证明下面的结论成立.
　　图1.3 互补图的连通性
　　定理 1.3 设图G是非连通的， 则其补图G一定是连通的.
　　设简单图G满足V (G)=U [ V ， U \ V=.， 如果对于 8 fu， vg 2 E(G) 都有u 2 U， v 2 V ， 则称图G是一个二部图; 如果二部图G的边集E(G) 满足: 对 8 u 2 U， v 2 V都有fu， vg 2 E(G)， 则称二部图G是一个完全二部图. 对于完全二部图G， 如果jUj=n， jV j=m， 则一般将G记为Kn，m， 其中当n=1时K1，m称为星形图; n阶星形图一般记为Sn. 例如， 图 1.3 中的G2 就是星形图S4. 类似地， 可以定义多部图. 对于k . 2， 设图G=(V，E) 的顶点集V满足
　　如果 8 uv 2 E， 存在i， j (i

目录
前言
符号说明
第1章 基本计数技术 1
1.1 图的基本概念 1
1.1.1 图的定义 1
1.1.2 图的连通性 3
1.1.3 图的同构 6
1.2 基本计数原理 7
1.2.1 分类计数原理 7
1.2.2 分步计数原理 10
1.2.3 对应计数原理 11
1.2.4 殊途同归原理 13
1.3 排列的计数 14
1.3.1 排列 14
1.3.2 重复排列 15
1.3.3 重集的排列 16
1.3.4 圆排列初步 20
1.4 组合的计数 20
1.4.1 组合 21
1.4.2 重复组合 21
1.4.3 重集的组合 23
1.4.4 不相邻的组合 24
1.5 组合数的性质 25
1.6 q多项式系数 31
1.7 排列的生成算法 37
1.7.1 字典序法 37
1.7.2 换位生成算法 40
1.7.3 逆序生成算法 42
1.8 组合的生成算法 44
1.8.1 基于二进制的算法 44
1.8.2 字典序法 46
1.8.3 旋转门算法 48
1.9 映射与排列的表示 51
1.9.1 映射的表示与计数 51
1.9.2 排列的表示与计数 55
1.9.3 排列的降序集 63
1.9.4 排列的树表示 64
1.9.5 排列的矩阵表示 67
习题 1 68
第2章 母函数及其应用 75
2.1 普通型母函数 75
2.2 指数型母函数 87
2.3 母函数的合成 99
2.4 多元母函数 112
2.5 整数的拆分 115
2.5.1 整数拆分的概念 116
2.5.2 无序拆分的表示 118
2.5.3 无序拆分与拆分数 119
2.5.4 各部分互异的拆分 124
2.5.5 受限的拆分 126
2.5.6 拆分数 p(n) 的性质 130
2.5.7 整数的完备拆分 139
习题 2 144
第 3 章 递推关系 148
3.1 递推关系的概念 148
3.2 线性常系数递推关系 151
3.3 一般递推关系 167
习题 3 176
第4章 特殊计数序列 180
4.1 Fibonacci 序列 180
4.2 Catalan 序列 182
4.3 Schr.der 序列 193
4.4 Motzkin 序列 203
4.5 Stirling 序列 207
4.6 一般反演序列 217
习题 4 218
第5章 容斥原理 226
5.1 容斥原理 226
5.2 符号形式 236
5.3 禁排问题 245
5.3.1 棋盘的概念 245
5.3.2 棋盘多项式 248
5.3.3 Ferrers 棋盘 256
习题 5 258
第 6 章 M.bius 反演及应用 261
6.1 问题引入 261
6.2 偏序集 263
6.3 偏序集的构造 284
6.4 关联代数 290
6.5 M.bius 反演 311
6.6 M.bius 反演的应用 316
6.6.1 Bn 上的应用 316
6.6.2 Dn 上的应用 321
6.6.3 Πn 上的应用 324
6.6.4 Fnq上的应用 327
习题 6 331
第7章 鸽巢原理 334
7.1 鸽巢原理：简单形式 334
7.2 鸽巢原理：一般形式 338
7.3 Ramsey 问题 340
7.4 Ramsey 类定理 347
习题 7 351
第8章 Pólya 计数理论 353
8.1 问题引入 353
8.2 关系、群及其性质 354
8.2.1 等价关系 355
8.2.2 群的概念和性质 355
8.2.3 子群及其判定 358
8.2.4 Lagrange 定理 360
8.2.5 群的同态与同构 362
8.3 置换群及其性质 363
8.4 Burnside 引理 370
8.5 Pólya 定理 377
8.6 置换群的循环指数 385
8.7 Pólya 定理的母函数形式 397
8.8 Pólya 定理的扩展 409
8.8.1 直和上的扩展 409
8.8.2 Cartes 积上的扩展 413
8.8.3 子集集上的扩展 415
8.8.4 de Bruijn 定理 419
习题 8 440
习题答案或提示 443
参考文献 459