当前位置:首页 >> 数学 >>

组合数学讲义(1.0版)


1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19.

p12 例 9(填空) p17 2.生成组合,递归调用算法 p19 定理 2(填空) p20 例 3(填空) p22 性质 2 解释组合意义 p25 (4)解释组合意义 p28 例 5(填空) p29 (3) 空盒放法( )种 p32 定理 1: 第二类 stirling (证明) p34 例 1 (填空)列式 p36 定理 2(3)(填空或大题)证明 p44 例 5 列出式子即可 p49 4.2.5 定理(填空) p51 例 4 求解问题 p56 例 2 写出递归关系式(改题目) p64 catalan 写前几项 {1,1,2,5,14,42}(填空) p75 定理 1 (填空)如例 1 p80 例 2 (证明) 通过定理求解:一个矩形染色 p86 例如:构建 3 阶完全的正交拉丁方簇





第 1 章 绪 论 .................................................................................................................................. 1 1.1 组合数学的起源.................................................................................................................. 1 1.2 组合数学的研究内容.......................................................................................................... 3 1.3 组合数学的应用.................................................................................................................. 5 实验项目——构造幻方............................................................................................................... 5 第 2 章 排列与组合 .......................................................................................................................... 7 2.1 加法原理与乘法原理.......................................................................................................... 7 2.1.1 加法原理................................................................................................................... 7 2.1.2 乘法原理................................................................................................................... 8 2.1.3 应用举例................................................................................................................... 8 2.2 排列与组合........................................................................................................................ 10 2.2.1 集合的排列............................................................................................................. 10 2.2.2 集合的组合............................................................................................................. 12 2.2.3 排列和组合的模型................................................................................................. 13 2.3 排列与组合的生成算法.................................................................................................... 14 2.3.1 生成排列的算法..................................................................................................... 14 2.3.2 生成组合的算法..................................................................................................... 16
I

2.4 多重集合的排列与组合.................................................................................................... 17 2.4.1 多重集合的排列..................................................................................................... 17 2.4.2 多重集合的组合..................................................................................................... 18 2.4.3 排列和组合的模型................................................................................................. 20 第 3 章 二项式定理与多项式定理 ................................................................................................. 21 3.1 二项式定理........................................................................................................................ 21 3.1.1 二项式定理及其证明............................................................................................. 21 3.1.2 二项式系数的基本性质......................................................................................... 22 3.1.3 组合恒等式............................................................................................................. 24 3.2 多项式定理........................................................................................................................ 27 3.3 Stirling 数(司特林数) ................................................................................................... 29 3.4 集合的分划........................................................................................................................ 31 3.4.1 集合分划的定义..................................................................................................... 31 3.4.2 第 2 类 stirling 数的性质 ....................................................................................... 32 3.5 正整数的分拆.................................................................................................................... 34 3.5.1 有序分拆................................................................................................................. 34 3.5.2 无序分拆................................................................................................................. 35 3.5.3 分拆的 Ferrers 图(费若斯图) ........................................................................... 37 3.6 综合应用——球盒分配问题............................................................................................ 39 第 4 章 容斥原理与鸽笼原理......................................................................................................... 41 4.1 容斥原理 ........................................................................................................................... 41 4.1.1 间接计数法............................................................................................................. 41 4.1.2 容斥原理的三种形式............................................................................................. 43 4.2 容斥原理的应用................................................................................................................ 46 4.2.1 有限重集合的 r 组合 ............................................................................................. 46 4.2.2 有禁止位置的错排问题......................................................................................... 46 4.2.3 有禁止模式的错排问题......................................................................................... 47 4.2.4 不相邻的排列......................................................................................................... 48 4.2.5 不相邻的组合......................................................................................................... 49 4.3 鸽笼原理 ........................................................................................................................... 49 4.4 Ramsey 问题与 Ramsey 数 ............................................................................................... 52 4.4.1 Ramsey 问题 ........................................................................................................... 52 4.4.2 Ramsey 数 ............................................................................................................... 53 第 5 章 递推关系与母函数............................................................................................................... 55 5.1 递推关系 ........................................................................................................................... 55 5.2 母函数 ............................................................................................................................... 57 5.2.1 母函数的定义......................................................................................................... 57 5.2.3 利用母函数求解递归关系式 ................................................................................. 57 5.2.2 母函数的性质......................................................................................................... 59 5.3 Fibonacci 序列 ................................................................................................................... 60 5.3.1 Fibonacci 序列 ........................................................................................................ 60
II

5.3.2 Fibonacci 数的性质 ................................................................................................ 62 5.4 Catalan 序列 ...................................................................................................................... 63 第 6 章 Polya 计数理论 .................................................................................................................. 69 6.1 群 ....................................................................................................................................... 69 6.1.1 群 ............................................................................................................................ 69 6.1.2 群的基本性质......................................................................................................... 70 6.1.3 子群、循环群、交换群......................................................................................... 71 6.2 置换群 ............................................................................................................................... 71 6.2.1 置换群的定义......................................................................................................... 72 6.2.2 置换的轮换之积表示............................................................................................. 74 6.3 Burnside 引理 ................................................................................................................... 77 6.3.1 共轭类..................................................................................................................... 77 6.3.2 k 不动置换类 .......................................................................................................... 78 6.3.3 等价类..................................................................................................................... 79 6.3.4 Burnside 引理 ......................................................................................................... 80 6.4 Polya 定理 ......................................................................................................................... 81 6.4.1 Polya 定理的一般形式........................................................................................... 81 6.4.2 母函数型的 Polya 定理.......................................................................................... 82 第 7 章 组合设计 ............................................................................................................................ 84 7.1 拉丁方与正交拉丁方........................................................................................................ 84 7.1.1 拉丁方..................................................................................................................... 84 7.1.2 正交拉丁方............................................................................................................. 84 7.1.3 正交拉丁方的性质................................................................................................. 85 7.2 正交拉丁方的构造............................................................................................................ 85 7.2.1 域的概念................................................................................................................. 85 7.2.2 用有限域构造完全的正交拉丁方族 ..................................................................... 86 7.2.3 由低阶的正交拉丁方构造高阶的正交拉丁方 ..................................................... 87 7.3 正交拉丁方的应用举例.................................................................................................... 88 7.4 平衡不完全区组设计........................................................................................................ 89 7.4.1 平衡不完全区组设计的定义 ................................................................................. 89 7.4.2 Steiner 三元系(斯梯纳三连系)......................................................................... 90

III

1

组合数学讲义

第1章

绪论

第1章





组合数学是一个历史悠久的数学分支,可追溯到远古时代,18 世纪,组合数学得到较深 入的研究,20 世纪,计算机的诞生使组合数学得以蓬勃发展。组合数学中的许多问题具有理 论、实际、兴趣相结合的特征,求解问题时能促使人冷静思索,开拓思路,并寻求机敏精巧的 方法。所以,学习组合数学能提高人的思维能力、推断能力和分析问题的能力。

1.1

组合数学的起源

组合数学起源于人类早期的数学游戏,最早见于公元前 2200 年的“洛书” ,公元前 11 世 纪《易经》中的八卦最早体现了排列的思想。17 世纪到 18 世纪,Leibniz、Jacob 和 Euler 等数 学家建立了组合数学的基本原理。 1. 洛水神龟献奇图 关于大禹治水,大家最为熟悉的是三过家门而不入,其实还有很多美丽动人的传说。传说 大禹在治理黄河的时候,黄河龙马献给大禹一幅“河图” ,在治理洛水的时候,洛水神龟献给 大禹一本“洛书” ,前者是青色的,后者是红色的。 “洛书”中有一幅奇怪的图,如图 1.1(a)所 示,图中空心表示奇数实心表示偶数,这和古时的阴阳学有关。在中国古代, “河图”和“洛 书”被称为九宫图,而“洛书”用今天的数学符号翻译出来就是一个 3 阶幻方,如图 1.1(b)所 示。

4 9 2 3 5 7 8 1 6
(a) 洛书 图 1.1 (b) 对应的 3 阶幻方 洛书及对应的幻方

1

2

组合数学讲义

第1章

绪论

幻方有很多奇怪的现象,不同的排列会有相同的结果,例如: 列:276 + 951 + 438 = 672 + 159 + 834 = 1665 2762 + 9512 + 4382 = 6722 + 1592 + 8342 = 1172421 行:492 + 357 + 816 = 294 + 753 + 618 = 1665 4922 + 3572 + 8162 = 2942 + 7532 + 6182 = 1035369 主对角线:654 + 798 + 213 = 456 + 897 + 312 = 1665 6542 + 7982 + 2132 = 4562 + 8972 + 3122 = 1109889 副对角线:258 + 714 + 693 = 852 + 417 + 396 = 1665 2582 + 7142 + 6932 = 8522 + 4172 + 3962 = 1056609 2. 八卦 八卦由爻组成,爻分阴爻(用“--”表示)和阳爻(用“—”表示) ,三个爻的八种排列 组成了八卦: 乾、 坤、 震、 巽、 坎、 离、 艮、 兑。用 1 表示阳爻, 用 0 表示阴爻,则八卦可以用二进制的 0 和 1 的组合来表示,因此,二进制也起源于八卦。 3. 《组合的艺术》 1666 年,年仅 20 岁的德国数学家莱布尼兹(Leibniz G.W)编著的《组合的艺术》 (De Art Combinatoria)一书问世,书中首次使用了“组合学” (Combinatorics)一词。 《组合的艺术》一书是组合数学领域的第一本专著,它的出版是组合数学史上的里程碑。 在此后的三百多年的时间里,组合数学得到了快速发展,其主要原因归结为: (1)组合数学理论的发展 17 世纪以后,一系列组合数学理论纷纷被建立起来,关于母函数、鸽笼原理、容斥原理 等组合数学的理论的建立, 使这门学科的研究范畴不再仅仅局限于数学游戏, 而是扩展到组合 计数、组合设计等组合数学的分支。 19 世纪,Dirichlet P. G. 提出了鸽笼原理; 1928 年,英国数学家 Ramsey 提出并证明了一个关于集合论的 Ramsey 定理; 1935 年,Whitney 推广了图和矩阵的概念,引入了拟阵; 1937 年,Polya 将群的理论引入组合数学中,给出了一种普适的计数方法——Polya 定理; 如今,组合数学已成为数学中发展最为迅速的分支之一。 (2)数学其他分支的发展对组合数学的促进 诸如概率论、群论等数学知识被引入组合数学中,扩大了组合数学研究的深度和广度。 (3)其他学科的需要 组合数学的发展不仅来源于本学科内理论的建立,而且来源于其他学科对组合数学的需 求,这种需求是组合数学发展的外在推动力。例如,物理学、化学和生物学中的二聚物、晶体 结构、DNA 序列等诸多问题,实际上都可抽象为组合数学模型,并用组合数学的方法对其进 行分析。 (4)计算机的广泛应用对组合数学的影响 组合数学是近年来最活跃、 最迷人的数学分支, 也是计算机科学与技术专业的重要理论基 础之一。计算机学科的网络优化、编码理论、密码学等许多领域都涉及组合数学问题。组合数 学是算法分析的数学基础,若没有组合数学的基础,就难以深入研究和分析有关算法。

2

3

组合数学讲义

第1章

绪论

1.2

组合数学的研究内容

组合数学内容丰富,涉及广泛,主要包括组合计数、组合设计、组合算法、编码理论、 图论、线性规划等内容,已经发展成熟的部分,如编码理论、图论、线性规划等,则逐步从组 合数学中分离出去。 组合数学主要研究事物在给定模式下的计数、分类、性质、构造等,其中最主要的内容 是对离散对象计数。 首先引入组态的概念。组态(也称配置)是指若干个对象按照某种约束条件组成的状态。 概括起来,组合数学研究以下四大类问题。 1. 组态的存在性 所谓组态的存在性,是指满足某种条件的组态是否存在。在这类问题的研究中,我们只 关心满足某种条件的组态是否存在,而不关心具体的组态是什么。 例 1 鸽笼原理:如果把 n + 1 只鸽子放入 n 只鸽笼中,那么至少有一个鸽笼中包含两只或 更多的鸽子。 结论是显然成立的,如若不然,每个鸽笼中至多有一只鸽子,那么 n 只鸽笼中至多有 n 只鸽子,与假设矛盾。 在鸽笼原理中,只关心某只鸽笼中包含两只获更多鸽子的组态是否存在,而不关心具体 哪只鸽笼有多少个鸽子。 可以利用鸽笼原理、Ramsey 定理等求解组态的存在性问题。 2 组态的计数 所谓组态的计数,是指计算满足某种条件的排列或组合的总数。在这类问题的研究中, 我们只关心满足某种条件组态的计数,而不关心具体的组态是什么。 例 2 《易经》——八卦 《易经》大约写于公元前 11 世纪,相传是由伏羲、文王和孔丘创作, 《易经》不仅在中国 古典文学史上占有重要地位,还是世界公认的第一本讨论排列的书籍。 八卦由阳爻“—”和阴爻“--”作为基本元素,两爻合“两仪” ,两仪成“四象” ,四象 成八卦,即每次取两个,共有四种不同的排列,称为“四象” ,每次取三个,共有八中不同的 排列,称为“八卦” 。八卦常用来代表八种不同的 北 事物,如东、东南、南、西南、西、西北、北、东 西北 东北 北等八个方位,或乾(天) 、坤(地) 、巽(风) 、 乾 震(雷) 、坎(水) 、离(火) 、艮(山) 、兑(泽) 巽 兑 八种自然现象。八个方位和八卦对应起来,常画在 东 西 坎 离 罗盘的周围,如图 1.2 所示,也就是将八卦两两相 震 艮 重,得到 64 种形式,即六十四卦。两仪、四象、 坤 八卦、六十四卦,从数学的角度来考察,是阴爻和 西南 东南 阳爻两个基本元素的无限重复排列的情况,可用 N 南 = Kr 来计算,其中 N 为排列总数,K 为元素总数, 图 1.2 八卦与罗盘 r 为参加排列的元素个数。
3

4

组合数学讲义
1

第1章

绪论

当 r = 1 时,N = 2 = 2,为两仪; 当 r = 2 时,N = 22 = 4,为四象; 当 r = 3 时,N = 23 = 8,为八卦; 当 r = 6 时,N = 26 = 64,为六十四卦。 可以利用容斥原理、二项式定理、多项式定理、Polya 定理等求解组态的计数问题。 3 构造性问题 构造性问题研究的是:一个组合数学问题,如果已经判定其解是存在的,那么如何将解 构造出来呢? 例 3 n 阶幻方(也称魔方阵、纵横图) :将 1~n2 共 n2 个自然数排成纵横共有 n 个数的 正方形,使每行、每列、两条主对角线的 n 个数之和相等,这个和称为幻和(也称幻方常数) 。 已经证明,幻和 S ?

1 n(n 2 ? 1) 。 2 3 阶幻方的幻和为 15,共有如下 8 个等式成立:

1+5+9=15;1+6+8=15;2+4+9=15;2+5+8=15; 2+6+7=15;3+4+8=15;3+5+7=15;4+5+6=15; 考察上式发现,1、3、7、9 各出现 2 次,2、4、6、8 各出现 3 次,5 出现 4 次,因此,5 一定位于中心,1、3、7、9 位于边上,2、4、6、8 位于角上,即三阶幻方只有一个基本形式, 通过将其旋转与反射,可得到 8 种变形,但他们是同构的,如图 1.3 所示。 6 1 8 7 5 3 2 9 4 8 1 6 3 5 7 4 9 2 8 3 4 1 5 9 6 7 2 6 7 2 1 5 9 8 3 4 2 7 6 9 5 1 4 3 8 2 9 4 7 5 3 6 1 8 4 3 8 9 5 1 2 7 6 4 9 2 3 5 7 8 1 6

图 1.3 3 阶幻方的 8 种同构形式

4 阶幻方共有 880 个基本形式,通过方阵的旋转与反射,共有 7040 个不同形式。 5 阶幻方的确切数量现无人能够给出。1973 年,理查德?汉洛泼尔(Richard Schroeppel) 开发了一个程序,在 PDP-10 计算机上运行了 100 个小时后得出结论,五阶幻方的基本形式有 275 305 224 个,但没有给出证明。 4 组合算法 组合算法用来求解组合问题,组合问题通常是最优化问题,即寻找一个组合对象(比如一 个排列、一个组合或一个子集) ,这个对象能够满足特定的约束条件,并使某个目标函数取得 极值:价值最大或者成本最小。有许多最优化问题至今不知道获得最优解的办法是什么,通常 的办法是给出次优解,这类问题的求解运用的往往是组合学思想以及组合学算法。例如,最短 路径问题、TSP 问题、付款问题、铺砖问题,等等。
4

5

组合数学讲义

第1章

绪论

例 5 付款问题: 假定 POS 机中有 n 张面值为 pi(1≤i≤n)的货币, 用集合 P={p1, p2, ?, pn} 表示,如果 POS 机需支付的现金为 A,那么,它必须从 P 中选取一个最小子集 S,使得

pi ? S ,

?p
i ?1

m

i

? A (m ?| S |)

(式 1.1)

如果用向量 X=( x1, x2, ?, xn)表示 S 中所选取的货币,则
?1 xi ? ? ?0 pi ? S pi ? S

(式 1.2)

那么,POS 机支付的现金必须满足

?x p
i ?1 i

n

i

?A

(式 1.3)

并且

d ? min ? xi
i ?1

n

(式 1.4)

在上述付款问题中,集合 P 是该问题的输入,满足式 1.1 的解称为可行解,式 1.2 是解的 表现形式,因为向量 X 中有 n 个元素,每个元素的取值为 0 或 1,所以,可以有 2n 个不同的 向量,所有这些向量的全体构成该问题的解空间,式 1.3 是该问题的约束条件,式 1.4 是该问 题的目标函数,使式 1.4 取得极小值的解称为该问题的最优解。

1.3

组合数学的应用

实验项目——构造幻方
实验要求: ⑴ 设计数据结构; ⑵ 设计算法完成任意 n 阶幻方的填数; ⑶ 分析算法的时间复杂度。 实验提示: 解决幻方问题的方法很多,下面介绍一种被称为“左上斜行法”的填数方法,具体填数过 程如下: ⑴ 由 1 开始填数,将 1 放在第 0 行的中间位置; ⑵ 将幻方想象成上下、左右相接,每次往左上角走一步,会有下列情况: · 左上角超出上边边界,则在最下边相对应的位置填入下一个数字; · 左上角超出左边边界,则在最右边相对应的位置填入下一个数字; · 如果按上述方法找到的位置已填入数据,则在同一列下一行填入下一个数字。

5

6

组合数学讲义

第1章

绪论

幻方算法 Square void Square(int a[ ][ ], int n) { p=0; q=(n-1)/2; a[0][q]=1; //在第 0 行的中间位置填 1 for (i=2; i<=n*n, i++) { p=(p-1+n) % n; //求 i 所在行号 q=(q-1+n) % n; //求 i 所在列号 if (a[p][q]>0) p=(p+1) % n; //如果位置(p, q)已经有数,填入同一列下一行 a[p][q]=i; } }

6

组合数学讲义

第2章

排列与组合

第2章

排列与组合

组合数学最主要的研究内容就是对离散对象的计数(即组合计数) ,组合计数的中心问题 是求满足某些条件的组态总数。排列与组合是组合计数的基础。如果考虑的对象与顺序有关, 则称之为排列问题,如果考虑的对象与顺序无关,则称之为组合问题。 排列和组合是人们普遍遇到的、并已被广泛使用的基本概念,例如,集合站队、买彩票、 比赛日程安排等。 除了这种具有普遍意义的排列和组合之外, 还有可重复元素的排列和组合问 题、不相邻的组合问题,等等。

2.1

加法原理与乘法原理

加法原理和乘法原理是组合计数时经常用到的两个基本原理。

2.1.1 加法原理
加法原理 假设事件 A 有 m 种选取方式,事件 B 有 n 种选取方式,则选 A 或 B 共有 m + n 种方式。 例 1 事件 A 是大于 0 小于 10 的偶数,即 A = {2, 4, 6, 8};事件 B 是大于 0 小于 10 的奇 数,即 B = {1, 3, 5, 7, 9}。则具有性质 A 的事件数 m = 4,具有性质 B 的事件数 n = 5,具有性 质 A 或性质 B 的事件数即为大于 0 小于 10 的正整数有 4 + 5 = 9 个。 用集合论的语言描述加法原理: 定理 1 设 A 和 B 为有限集合,且 A ? B ? ? ,则 A ? B ? A ? B 。 证明过程——作业。 推论 设有 n 个有限集合 S1, S2, ?, Sn 满足 Si ? S j ? ? (1 ? i ? j ? n) ,则

S1 ? S 2?? ? Sn ? ? Si
i ?1

n

7

组合数学讲义

第2章

排列与组合

例 2 在所有的 6 位二进制数中,至少有连续 4 位是 1 的有多少个? 解:把所有满足条件的二进制数分成如下三类: ① 恰有连续 4 位是 1:可能是 X01111,011110,11110X,其中 X 取 0 或 1,故共有 5 个; ② 恰有连续 5 位是 1:011111,111110,共有 2 个; ③ 恰有连续 6 位是 1:111111,只有 1 种可能。 由加法原理知,共有 5 + 2 + 1 = 8 个满足条件的 6 位二进制数。 ※ 当某一计数问题可以分组考虑时,可运用加法原理。

2.1.2 乘法原理
乘法原理 假设事件 A 有 m 种选取方式,事件 B 有 n 种选取方式,则选 A 及 B 共有 m × n 种方式。 例 3 长度为 n 的 0、1 符号串可表示为 a=a1a2?an,由于 ai(i = 1, 2, ?, n)只能取 0 或 1,由乘法原理,该符号串的个数为 2n。例如 n = 3,有 {000, 001, 010, 011, 100, 101, 110, 111} 用集合论的语言描述乘法原理: 定理 2 设 A 和 B 为有限集合,且 A ? B ? ? ,则 A ? B ? A ? B 。 证明过程——作业。 推论 设有 n 个有限集合 S1, S2, ?, Sn 满足 Si ? S j ? ? (1 ? i ? j ? n) ,则

S1 ? S2 ? ?? Sn ? ? Si
i ?1

n

例 4 n = 73 × 2× 4,求能除尽 n 的整数个数。 11 13 解:显然,能除尽 n 的整数是:

7 l1 ?11l2 ?13l3

(0≤l1≤3,0≤l2≤2,0≤l3≤4)

根据乘法原理,能除尽 n 的整数是:4× 5=60。 3× ※当某一计数问题可以分步考虑时,可运用乘法原理。

2.1.3 应用举例
加法原理与乘法原理是组合计数时经常用到的两个基本法则。 加法原理和乘法原理常常结 合使用,可以解决很多组合计数问题。

8

组合数学讲义

第2章

排列与组合

例 5 比 5400 大的 4 位数中,数字 2 和 9 不出现,且各位数字不同的数有多少个? 解:满足条件的 4 位数可以分为 4 类: (1)千位比 5 大的满足条件的整数有 3 × 7 × 5 × 6 个; (2)千位是 5,百位比 4 大的满足条件的整数有 3 ×6 ×5 个; (3)前 2 位是 54,十位比 0 大且满足条件的整数有 5 × 5 个; (4)前 3 位是 540,个位比 0 大且满足条件的整数有 5 个。 故共有 3 × 7 × 6 × 5 + 3 ×6 × 5 + 5 × 5 ×5 + 5 = 750 个满足条件的整数。 例 6 由 26 个英文字母构成长度为 5 的字符串,要求(1)5 个元音 a, e, i, o, u 不能相邻; (2)其余 21 个辅音不能 3 个相邻; (3)相邻的辅音不能相同。求这样的字符串有多少个? 解:用 α 表示元音集合,表示 β 辅音集合,根据要求,满足条件的字符串可表示为如图 2.1 的结构。 αβαβα αβα α αβ αββ αββα αβαβ αβαββ αββαβ β ββ ββα ββαβ ββαββ
图 2.1 满足要求的字符串结构分析

βαβα βα βαβ βαββ

βαβαβ βαββα ββαβα

根据乘法原理有: (1)αβαβα 型:n1 = 5×21×5×21×5 = 55125 (2)αβαββ 型:n2 = 5×21×5×21×20 = 220500 (3)αββαβ 型:n3 = 5×21×20×5×21 = 220500 (4)βαβαβ 型:n4 = 21×5×21×5×21 = 231525 (5)βαββα 型:n5 = 21×5×21×20×5 = 220500 (6)ββαβα 型:n6 = 21×20×5×21×5 = 220500 (7)ββαββ 型:n7 = 21×20×5×21×20 = 882000 根据加法原理有: n = n1 + n2 + n3 + n4 + n5 + n6 + n7 = 55125 + 220500 + 220500 + 231525 + 220500 + 220500 + 882000 = 2 050 650 例 7 求 n 元布尔函数 f (x1, 2, x ?, n) x 的数目, 其中布尔函数是指含有与 (∧) 或 、 (∨) 、 - 非( )等基本布尔运算的函数。 解:设有 n 个布尔变元 x1,x2,?,xn,其中 xi∈ {0,1},I =1,2,?,n,根据乘法原理 n n (x1,x2,?,xn)共有 2 种不同指派,令 2 种不同指派为

a1 , a2 , ?, a2n
对每个指派,布尔函数取值为{0,1},故不同的布尔函数的数目为:
22 ? 2 ? 2 ??? 2
9
n

组合数学讲义

第2章

排列与组合

例如:n = 2,(x1,x2)有(0,0)、(0,1)、(1,0)、(1,1)共 4 种指派,则 f (x1,x2)有 24 = 16 种可能,即相同的(x1,x2)指派而函数值不全相同,则表示为不同的布尔函数,如表 2.1 所示。
表 2.1 2 元的布尔函数 f (x1,x2,?,xn)

(x1,x2) 0 0 1 1 0 1 0 1 f i= (x1, 2) x 0 0 0 1 1 0 1 1 f i=

f1 0 0 0 0 0

f2 0 0 0 1
x1 ? x2

f3 0 0 1 0
x1 ? x2

f4 0 0 1 1 x1 f11 1 0 1 0
x2

f5 0 1 0 0
x1 ? x2

f6 0 1 0 1 x2 f12 1 0 1 1
x1 ? x 2

f7 0 1 1 0
( x1 ? x 2 ) ? ( x1 ? x 2 )

f8 0 1 1 1
x1 ? x 2

f9 1 0 0 0
x1 ? x2

f10 1 0 0 1
( x1 ? x 2 ) ? ( x1 ? x 2 )

f13 1 1 0 0
x1

f14 1 1 0 1
x1 ? x2

f15 1 1 1 0
x1 ? x 2

f16 1 1 1 1 1

2.2
2.2.1 集合的排列

排列与组合

定义 1 排列:从 n 个不同的元素中,有次序地选取 r 个元素,称为从 n 中取 r 个的排列,其排列数记为 P(n, r)或 Pnr 。当 r = n 时,称此排列为全排列。 例 1 设 S = {a,b,c},从 S 中有次序地选取 2 个元素为: ab, ac, bc, ba, aa, cb 所以 P(3,2) = 6。

? P ( n, r ) ? 0 ? 显然,有 ? P (n,1) ? n ? P(n, n) ? n! ?

r?n n ?1 n ?1

定理 1 对于满足 r≤n 的正整数 n 和 r,有
P (n, r ) ? n(n ? 1) ?? (n ? r ? 1) ? n! (n ? r )!

证明略。
10

组合数学讲义

第2章

排列与组合

例 2 有 4 盏颜色不同的信号灯,把它们按不同的次序全部挂在灯杆上表示信号,共有多 少种不同的信号?每次使用 1 盏、2 盏、3 盏或 4 盏灯按一定的次序挂在灯杆上表示信号,共 有多少种不同的信号? 解:①P(4, 4) = 24 ②P(4, 1) + P(4, 2) + P(4, 3) + P(4, 4) = 64 例 3 有男运动员 7 名,女运动员 3 名,列队进场,要求头尾两名运动员必须是男运动 员,且女运动员不相邻,问有多少种方案? 解:男运动员先进行全排列,然后女运动员往里插入,设 7 名男运动员的一个排列: m1, m2, m3, m4, m5, m6, m7 女运动员可以插入的位置为 0,示意图如下: m1 0 m 2 0 m3 0 m4 0 m5 0 m6 0 m 7 则第 1 名女运动员有 6 种选择, 2 名有 5 种选择, 3 名有 4 种选择, 第 第 故方案数为 7!× 5× 6× 4 = 604800(或 7!× P(6, 3)) 。 例 4 将{a, b, c, d, e, f}进行排列,问: (1)使得字母 b 在字母 e 的左邻的排列有多少种? (2)使得字母 b 在字母 e 的左边的排列有多少种? 解: (1)字母 b 在字母 e 的左邻,可以把 be 看作一个字母,不妨设为 E,则原问题就变 成求集合{a, E, c, d, f}的全排列数,共有 5!种。 (2)将集合{a, b, c, d, e, f}的全排列数为 6!,这些全排列可以分成两类: ① A ={字母 b 在字母 e 的左边};② B ={字母 b 在字母 e 的右边}。 显然有 A∩B =Φ 。 定义映射 f:A→B,使 f (?b?e?) = f (?e?b?)。 即 f 将 A 中任一排列的 b 和 e 互换, 其余字母保持位置不变, 得到 B 中的一个排列, 显然, f 是一一映射,所以,| A | = | B | = 6!/2。 前面讨论的排列是在直线上进行的, 称为线性排列, 若在圆周上进行排列, 则称为圆排列。 定义 2 圆排列:从 n 个不同元素中取出 r 个元素,仅按元素间的相对位置而不 分首尾地围成一圈,这种排列称为圆(环状)排列。 例 5 由 R,W,L,G,,Y 五色扇形组成的圆盘,问可以有多少种不同的圆盘? 解:只要各种颜色的相对位置不变,就是同一个圆盘,例如图 2.1 R 所示圆盘,线性排列 RLYGW,LYGWR,YGWRL,GWRLY,WRLYG L W 表示的都是这个圆盘, 可以看出, 这五色扇形的圆排列数 N = 5!/5 = 4!。 现在推广到 r 圆排列。在 1 个 r 圆排列的任意两个相邻元素之间 Y G 都有一个位置,共有 r 个位置,从这 r 个位置处将圆排列断开,并拉直 图 2.3 圆排列示例 成线性排列,可以得到 r 个不同的 r 排列,因此,有下面的定理成立。 定理 2 n 个元素的 r 圆排列数为: 排列数为(n-1)!。
11

P ( n, r ) n! ? ,特别地,n 个元素的 n 圆 r r ( n ? r )!

组合数学讲义

第2章

排列与组合

例 6 n 对夫妻围一圆桌而坐,求每对夫妻相邻而坐的方案数。 解:夫妻相邻而坐,可以将一对夫妻看成一个整体,其圆排列数为(n-1)!,由于每对夫妻 可以交换位置,故所求方案数为(n-1)!×2n。 例 7 有 4 个中国人和 4 个美国人围桌而坐, 要求同一国的人不相邻, 求共有多少种坐法? 解:先让 4 个中国人隔位坐下,属于圆排列问题,共有 P(4,4)/4 = 3!= 6 种坐法,然后 4 个美国人插空而坐,这实际上是 4 个人的全排列问题,因为这 4 个人已经让中国人隔开了, 共有 4!种坐法,运用乘法原理,共有 3! × = 144 种坐法。 4!

2.2.2 集合的组合
定义 1 组合:从 n 个不同元素中选取 r 个元素而不考虑其次序时,称为从 n 中 取 r 个的组合,其组合数记为 Cn ,C(n,r) 或 ? ? 。 ?r ? ? ?
r

?n?

例8

50 名同学相互握手,共握手多少次?
P(50,2) ? 1225次。 2

解:握手问题属于组合问题,共有 C (50,2) ?

?C ( n, r ) ? 0 ? 显然,有 ?C ( n,1) ? n ?C ( n, n) ? 1 ?

r?n n ?? 1 n ?? 1
P(n, r ) n! 。 ? r! r!(n ? r )!

定理 1 对于满足 r≤n 的正整数 n 和 r,有 C(n, r ) ?

解释:对于一个从 n 个元素中选取 r 个元素的每一个组合,都可以对这 r 个元素进行全排 列,可以得到 P(r, r) = r!个 r 排列,即 P(n, r) = C(n, r) × r!。 证明略。 例 9 现有 100 件产品,其中有两件是次品,如果从中任意抽出 3 件,则抽出的产品中至 少有 1 件次品的概率是多少? 解:从 100 件产品中任意抽出 3 件,共有 C(100, 3)种方案; 抽出的产品中至少有 1 件次品,有两种情况: (1)只有 1 件次品,共有 C(98, 2)×C(2, 1)种方案; (2)有 2 件次品,共有 C(98, 1)×C(2, 2)种方案。 则所求概率为:
C (98,2) ? C (2,1) ? C (98,1) ? C (2,2) ? 100% ? 5.94% C (100,3)

例 10 某火车站有 6 个入口,每个入口每次只能进一个人,则 9 个人共有多少种进站方
12

组合数学讲义

第2章

排列与组合

案? 解:因 9 个人进站时在每个入口都是有序的,则 (1)先构造 9 个人的全排列,共有 9!个; (2)选定一个全排列,加入 5 个分隔符,将其分成 6 段,则第 i 段对应着第 i 个入口的 进站方案,例如: **△*△***△*△*△* 则进站方案为:
9!?C (14,5) ? 9!? 14! ? 726,485,760 5!?9!

(△表示分隔符 *表示一个人)

例 11 在图 2.4 所示的棋盘中,若从左下角走 到右上角,并且规定只能向右或者向上走,问共有 多少种方案? 解:无论怎么走,只要向右走 4 步和向上走 3 图 2.4 棋盘及一种方案 步都可以到达右上角,用 0 代表向右走一步,用 1 代表向上走一步,则一个由 4 个 0 和 3 个 1 组成的 7 位 0、1 字符串唯一地对应着一种走法, 即 C(7,4) ?
7! ? 35 。 4!?3!

下面给出两个组合恒等式。 推论 若 0≤r≤n,则 C(n,r) = C(n,n-r)。

由定理 1 很容易得出结论, 其组合意义是: C(n, r)是 n 元集合 S 的 r 元子集的个数, C(n, n-r)是 n 元集合 S 的 n-r 元子集的个数。设 A 是集合 S 的一个 r 元子集,则 S-A 集合 S 的 n-r 元子集,而且这种对应关系是一一对应的,所以,集合 S 的 r 元子集的个数等于集合 S 的 n-r 元子集的个数。 定理 2 对任意正整数 n,有 C(n,0) + C(n,1) + C(n,2) + ? + C(n,n) = 2n。 证明:S 的 r 元子集的个数为 C(n,r),而 r 可以取 1, 2, ? , n,由加法原理,S 的所有子 集的个数为: C(n,0) + C(n,1) + C(n,2) + ? + C(n,n) 另一方面,集合 S 有 n 个元素,在构成 S 的一个子集的时候,每个元素都有在或不在该子 集两种可能,由乘法原理,共有 2n 种方式构造 S 的一个子集。 综上,定理成立。其组合意义是:n 元集合的所有子集个数为 2n。

2.2.3 排列和组合的模型
从 n 中取 r 个排列的模型可以看作是 r 个有区别的盒子,从 n 个有区别的球中取 r 个球放 进 r 个盒子,每个盒子有一个球且无一空盒,如图 2.5 所示。

13

组合数学讲义

第2章

排列与组合

A = { a1 , a2 , a3 , ?? ,

an }

n 个球

(1) (2)

??

(r)
图 2.5

r 个盒子
排列的模型

球:有区别 盒子:有区别 每盒一球 没有空盒

取 1 个球放进第 1 个盒子有 n 种选择,从剩下的 n-1 个球中取 1 个球放进第 2 个盒子有 n-1 种选择,??,依此类推,最后向第 r 个盒子放球时还剩下 n-r +1 个球,有 n-r + 1 种选 择,由乘法原理有: P(n,r) = n(n-1) ??(n-r + 1) =
n! ( n ? r )!

从 n 中取 r 个组合的模型可以看作是 r 个无区别的盒子,从 n 个有区别的球中取 r 个球放 进 r 个盒子,每个盒子有一个球且无一空盒,如图 2.6 所示。 A = { a1 , a2 , a3 , ?? , an } n 个球 球:有区别 盒子:没有区别 每盒一球 没有空盒

??
图 2.5

r 个盒子
组合的模型

排列与组合的区别在于盒子,排列的盒子是有区别的,组合的盒子是没有区别的,共 r 个无区别的盒子,放进 r 个盒子的球的全排列为 r!,这就是组合的重复度,故
C (n, r ) ? P(n, r ) r!

2.3

排列与组合的生成算法

在许多问题中,需要生成元素的特定排列与组合,当被排列和组合的元素个数较少时,可 以罗列出其全部状态,当元素个数较多时,就比较困难了,因此,需要研究排列和组合的生成 算法,由计算机自动生成。

2.3.1 生成排列的算法
1. 插入法 插入法生成排列的基本思想是:假设已经生成了所有(n-1)! 个排列,则可以把 n 插入到 n-1 个元素的每一种排列中的 n 个位置,而得到 n! 个排列。
14

组合数学讲义

第2章

排列与组合

例 1 生成 3 个元素的所有排列的过程如下: 生成{1}的排列:1 生成{1, 2}的排列:12 21 生成{1, 2, 3}的排列:123 132 312 213 231 321 注意到:生成{1, 2, ?, n}的排列是在{1, 2, ?, n-1}排列的基础上,将 n 插入在某一个排 列的 n 个位置。算法如下: 1. 生成初始排列{1}; 2. for(i = 2; i <= n; i++) for(j = 1; j <= (i-1)!; j++) for(k = i; k >= 1; k--) 将 i 插入到第 j 个排列中的第 k 个位置; 显然,算法的时间复杂度为:O(n!)。算法的优点是简单,缺点是生成在 n 个元素的全排 列时需要保留 n-1 个元素的全排列,需要的辅助存储空间较多。 2. 字典序法 这是一种以字典顺序排列的方法,其基本思想如下:对 n 个元素建立深度为 n 的字典树, 从树根到树叶的标号顺序对应一个排列,从左至右依次对应 n!个排列。 例 2 如图 2.7 所示,高度为 4 的字典树,按从树根到叶子的路径得到每一个排列,从左 到右依次为:1234, 1243, 1324, 1342, 1423, 1432, ??, 4321。观察字典树,发现由前一个排列 p1 p2 p3 p4 得到下一个排列的规律,具体算法如下: 1. 求满足关系式 pj-1<pj 的最大值 i ; 即 i = max{j |pj-1<pj } //ep:p1p2p3p4 = 3421, 则 i = 2 2. 求关系式 pi-1<pk 的最大值 k,设为 h ; 即 h=max{k |pi-1<pk} //ep: p1p2p3p4 = 3421,则 h =2 3. 将 pi-1 与 pk 互换得到 p'1p'2p'3 ? p'n //ep: p1p2p3p4 = 3421, 将 p1 与 p2 互换得到 4321 4. 令 p'1p'2p'3 ? p'n 中的 p'i p'i+1 ? p'n 顺序逆转得到下一个排列 即得到 p'1 ? p'i-1 p'n ? p'i //ep: p1p2p3p4 = 3421, p1p2 互换后得到 4321, p'2p'3p'4 逆转得 4123

1 2 2 4 3

4

3 2 4 2

3 4

3

4

3 4 2

3

2

图 2.7 15

字典树及对应的排列

组合数学讲义

第2章

排列与组合

从排列 12?n 开始重复上述过程,直到 n(n-1)?1 结束,即直到不存在 pj-1<pj。 例如:p1 p2 p3 p4 =1234,i=4, h=4,p3 p4 交换得到 1243,将 p'1 p'2 p'3 p'4 =1243 中的 p'4 逆转 得到排列 1243; p1 p2 p3 p4 =1243,i=3, h=4,p2 p4 交换得到 1342,将 p'1 p'2 p'3 p'4 =1342 中的 p'3 p'4 逆转 得到排列 1324; p1 p2 p3 p4 =1324,i=4, h=4,p3p4 交换得到 1342,将 p'1 p'2 p'3 p'4 =1423 中的 p'4 逆转得 到排列 1342; p1 p2 p3 p4 =1342,i=3, h=3,p2p3 交换得到 1432,将 p'1 p'2 p'3 p'4 =1432 中的 p'3 p'4 逆转 得到排列 1423; p1 p2 p3 p4 =1423,i=4, h=4,p3p4 交换得到 1432,将 p'1 p'2 p'3 p'4 =1432 中的 p'4 逆转得 到排列 1432; 依次类推。完整的算法请同学们写出来。 3. 换位法(也称 Johnson-Trotter 算法) 换位法适用于 n 较小的情况,其基本思想是:给排列中得每个分量 k 赋予一个方向,如果 分量 k 的箭头指向一个相邻的较小元素,则称分量 k 是可移动的。算法如下: 1. 将第一个排列初始化得 1 2? n 2. while 排列中存在一个可移动的整数 2.1 求最大的移动整数 k ; 2.2 把 k 和它箭头指向相邻整数交换, 得到一个排列; 2.3 掉转所有大于 k 的整数的方向;

??

?

例3

换位法生成 3 个元素的排列的过程。

? ?? 1 23

? ?? 1 32

? ?? 3 12

?? ? 32 1

?? ? 23 1

??? 21 3

注意:最大数 n 的活动规律总是从一端到另一端,调转方向时,从次大数 n-1 开始移动, 并且 n-1 与 n 的活动规律相似。

2.3.2 生成组合的算法
1. 生成子集 基本思想是:n 个元素的集合 A = {a1, a2, a3, ? , an}的所有 2n 个子集与长度为 n 的所有 2n 个比特串 B = {b1, b2, b3, ? , bn}之间具有如下一一对应关系: 若 ai ? B,则 bi = 1 若 ai ? B,则 bi = 0 例如:比特串: 000 子 集: { } 001 010 100 { a1} { a2} { a3} 101 110 011 111 {a1, a2} {a1, a2} {a1, a3} {a1, a2, a3}
16

组合数学讲义

第2章

排列与组合

具体算法如下: 1. 初始化一个长度为 n 的比特串 s = 00?0 并将对应的子集输出; 2. for(i =1; i <2n; i++) 2.1 s ++; 2.2 将 s 对应的子集输出; 2. 生成组合 首先寻找 C(n, r)的生成规律,例如 C(5, 3) = 10,具体生成过程如下: 123, 124, 125, 134, 135, 145, 234, 235, 245, 345 观察发现: (1)最后一位数最大的可达 n,倒数第二位最大可达 n-1,?,即倒数第 k 位(k ? r)最 大可达 n-k+1,?。设 n 个元素{1, 2, ?, n}的 r 组合用 a1 a2 a3 ? ar 表示,则有 a1 ≤ a2 ≤ a3 ≤ ? ≤ ar

?ar ? n ? ?ar ?1 ? n ? 1 ? ai ? n ? r ? i(i ? 1,2,?, r ) 且? ??? ?a1 ? n ? r ? 1 ?
(2)当存在 aj<n-r + j 时,其下标最大者设为 i,即 i = max{j | aj<n-r + j},执行下列操作: ai←ai + 1;ai+1←ai + 1;ai+2←ai+1 + 1;?;ar←ar-1 + 1。 例如:在组合 145 中,a2 和 a3 已达最大值,而 a1<n-r+j = 5-2+1 = 3,执行 a1= a1 + 1=2, a2 = 2 + 1 = 3,a3 = 3 + 1 = 4,得到一个新的组合 234 综上,从 n 个元素中取 r 个进行组合,从第一个组合 12?r 开始,依次生成下一个组合, 直到最后一个组合(n-r+1)……(n-1)n,具体算法如下: 1. 求满足 aj<n-r + j 的最大下标 i ; 即 i=max{j | aj<n-r + j } 2. ai←ai + 1; 3. for(j = i+1; j<=r; j++) aj←aj-1 + 1;

2.4
2.4.1 多重集合的排列

多重集合的排列与组合

在前面的讨论中,假设集合中没有重复元素,这样的集合称为单重集合,如果集合中有重 复元素,则称为多重集合。例如:
17

组合数学讲义

第2章

排列与组合

M = {a, a, a, b, c, c, d, d, d, d} 通常表示为: M = {3·a, 1·b , 2·c , 4·d} 一般地,n 元多重集合表示为: M = {k1·a1, k2·a2, ?, kn·an} 其中:ai(i = 1, 2, ?, n)表示元素的种类,ki(i = 1, 2, ?, n)表示元素 ai 的个数。 定理 1 多重集合 M = {∞·a1, ∞·a2, ?, ∞·an }的 r 排列数为 n r。 证明:在构造的 M 的一个 r 排列时,第一项有 n 种选择,第二项有 n 种选择,??, 第 r 项有 n 种选择,故 M 的 r 排列数为 n r。 注意前提:M 中的每一个元素都是无限重的,或每个元素的个数至少为 r。 定理 2 多重集合 M = { k1·a1, k2·a2, ?, kn·an}的全排列数为:
(k1 ? k 2 ? ? ? k n )! k1 ! k 2 !? k n !

证明:先把 M 中的所有的 k1 + k2 + ? + kn 个元素看成是互不相同的,则它的全排列数为 (k1 + k2 + ? + kn)!。但是这里 ki!个 ai 是相同的,所以 ki!个 ai 的位置相同并且同其他元素排列 也相同的排列是同一个,故 M 的全排列数为:
(k1 ? k 2 ? ? ? k n )! k1 ! k 2 !? k n !

例 1 某火车站有 6 个入口, 每个入口每次只能进一个人, 9 个人共有多少种进站方案? 则 解:设 9 个人分别为 a1, a2, ?, a9,分隔符为△,则集合 M = {a1, a2, ?, a9, 5·△}的每个 全排列对应着一种进站方案,共有
14! ? 726,485,760种进站方案。 1!?1!???1!?5!

2.4.2 多重集合的组合
多重集合 M 的 r 组合是指从 M 中无序地取出 r 个元素。 定理 1 多重集合 M = {∞·a1, ∞·a2, ?, ∞·an}的 r 组合数为 C(n + r - 1, r), 通常记为
n 。 r

证明 1:设多重集合 M 的某个 r 组合为: {x1·a1, x2·a2, ?, xn·an}
18

(式 1)

组合数学讲义

第2章

排列与组合

则有: x1 + x2 + ? + xn = r (式 2)

其中,x1 , x2 , ? , xn 为非负整数,即 xi≥0。 给定方程的一个解对应 M 的一个 r 组合, 从而 M 的 r 组合与方程的解构成一一对应关系, 于是将求 M 的 r 组合数问题转化为求方程的解的个数。 方程 x1 + x2 + ? + xn = r 的一个非负整数解可以表示为长为 n + r - 1 的 0、1 序列: 1??1 0 1??1 0??0 1??1 x1 个 x2 个 xn 个

其中 0 的个数为 n-1 个,1 的个数为 r 个,该 0、1 序列是集合{(n-1)·0, r·1}的一个全 排列,其个数为
( n ? r ? 1)! ? n ? r ? 1? ?。 ?? ? ( n ? 1)!?r! ? r ? ?

证明 2:证明集合 M = {∞·a1, ∞·a2, ?, ∞·an}的允许重复的 r 组合等价于某集合 M' = {1, 2, ??, n + r -1}的不允许重复的 r 的组合。 先证?:不失一般性,假定 n 个元素为 1, 2, ??, n,即 M' = {∞·1, ∞·2, ?,∞·n} M 中取 r 的组合为: 1≤ a1≤ a2≤ a3≤?≤ ar ≤n (由于允许重复,所以满足小于等于) 定义映射:{a1, a2, ?, ar}→{a1, a2 + 1, a3 + 2, ?, ar + r-1} 则 1< a1< a2 + 1< a3 + 2< ? < ar + r-1<n+ r -1 即{a1, a2 + 1, a3 + 2, ?, ar + r-1}为集合{1, 2, 3, ??, n + r -1}的不允许重复的 r 的组合。 再证?:设{1, 2, ??, n + r – 1}中不重复的 r 组合为{b1, b2, ??, br},满足: 1< b1< b2< ?< br <n + r – 1 (因为是单重集合,所以只满足小于)

令 a1 = b1,a2 = b2-1,a3 = b3-2,??,ar = br – r +1 则 1≤a1≤ a2≤ ?≤ ar = br – r +1≤n + r – 1– r +1 = n 即{a1, a2, ?, ar}为{1, 2, ??, n }中允许重复的 r 组合。 定理 2 多重集合 M = {∞·a1, ∞·a2, ?, ∞·an},要求 a1, a2, ?, an 至少出现 ? r ?1? 一次的 r 组合数为 ? ? n ? 1? 。 ? ? ? 证明:设多重集合 M 的某个 r 组合为: {x1·a1, x2·a2, ?, xn·an}
19

组合数学讲义

第2章

排列与组合

则有: x1 + x2 + ? + xn = r 且 xi≥1(i =1, 2, ?, n) 令 yi = xi-1,则 y1 + y2 + ? + yn = r-n 且 yi≥0(i =1, 2, ?, n) 由定理 1 知,满足条件的组合数为:

? (r ? n) ? (n ? 1) ? ? r ? 1 ? ? r ? 1 ? ? ??? ?r ? n ? ? r ? n ? ? ? k ? 1? ? ? ? ? ? ? ? ? ?

2.4.3 排列和组合的模型
例 2 把 r 只相同的球放到 n 个不同的盒子里, 每个盒子至少包含 q 只球, 问有多少种放法? 解:相当于求如下方程的解: x1 + x2 + ? + xn = r (xi≥q) 令 = xi-q,则 yi≥0 且方程 y1 + y2 + ? + yn = r – nq (式 4)
? r ? nq ? n ? 1? ?。 ? ? r ? nq ?

(式 3)

的解与式 3 的解一一对应,而方程 4 的非负整数解为: ? ? 例 3 问 ( x ? y ? z) 4 的展开式共有多少项?

解: ( x ? y ? z) 4 ? ( x ? y ? z) ? ( x ? y ? z) ? ( x ? y ? z) ? ( x ? y ? z) 展开式相当于从 4 个因子中每个括号里取一项相乘,可看作是 4 个无标志的球,放进 3 个有区别的盒子(x,y,z)中,一个盒子可以多于一个球且可以有空盒子,比如 x2yz 可以看 作 x 盒中有 2 个球 y 盒中有 1 个球 z 盒中有 1 个球。所以,问题等价于从 3 个元素中取 4 个作 允许重复的组合,其组合数为:
3 ? C(k + r - 1, r) = C(3 + 4 - 1, 4) = C(6, 4) = 15 4

其组合意义是:把 k 个相同的球放入 r 个有区别的盒子中,允许有空盒的放法是: C(k + r - 1, r)。

20

组合数学讲义

第3章

二项式定理与多项式定理

第 3 章 二项式定理与多项式定理
本章以排列和组合的概念为出发点, 通过介绍二项式定理与多项式定理, 讨论二项式系数 及多项式系数的性质及其组合意义,在此基础上讨论集合的分划和整数的分拆。

3.1
3.1.1 二项式定理及其证明

二项式定理

二项式定理 设 n 为正整数,则对任意的 x 和 y,有
n ?n? ?n? ?n? ? n ? n?1 n r n?r ( x ? y ) n ? y n ? ? ? xy n?1 ? ? ? x 2 y n?2 ? ? ? ? ?1 ? ?2? ? n ? 1? x y ? x ? r?0 ? r ? x y ? ? ? ? ? ? ? ? ? ? ? ? ?n? 其中, ? ? 称为二项式系数。 ?r ? ? ?

例 1 首先看两个常用的特例: (1) ( x ? y) 2 ? x 2 ? 2 xy ? y 2 (2) ( x ? y)3 ? x 3 ? 3xy 2 ? 3x 2 y ? y 3 证明:将 ( x ? y) n ? ( x ? y)( x ? y) ? ( x ? y) 展开直到没有括号,展开后,每个因子均可取 x 或 y,因而总共有 2n 项,并且可以写成 xryn-r(0≤r≤n)的形式,因为可以在(x+y)因子中选出 x 和 y 的总个数为 n 个,若从这 n 个因子中取 r 个 x,则在剩余的 n-r 个因子中取 y,得到 xryn-r 项,而 xryn-r 的系数为 n 个因子的 r 组合数,即为 ? ? 。 ? ? 需要强调的是,由 ? ? 的组合意义决定了 n, r 均为非负整数,但从 ? ? 的显示表示 ?r ? ?r ? ? ? ? ?
? n ? n(n ? 1)?(n ? r ? 1) ?n? ? ?? 可以看出, r 为非负整数 n 为实数时,? ? 只有解析意义而没有组合 当 ?r ? ?r ? r! ? ? ? ? ?n? ?n?
?n? ?r ?

意义。

21

组合数学讲义

第3章

二项式定理与多项式定理

3.1.2 二项式系数的基本性质
当 n 和 r 均为非负整数,且 n≥r 时,二项式系数 ? ? 满足如下基本性质。 ? ?
?n? ?r ?

?n? ?n ? 性质 1 对称性: ? ? ? ? ?r ? ?n ? r? ? ? ? ? ?
? n ? ? n ? 1? ? n ? 1? 性质 2 递推性(肩性) :当 n≥r≥1 时, ? ? ? ? ? r ? ? r ? ? ? r ?1? ? ? ? ? ? ? ? ? ?

证明:

n! ? n ? = p(n, r ) = ? ? ?r ? r! r!(n ? r )! ? ?

? n ? 1? ? n ? 1? (n ? 1)! (n ? 1)! ? ? r ? + ? r ? 1 ? = {n ? 1 ? r )!r! + (r ? 1)!(n ? r )! ? ? ? ? ? ? ?
= 其组合意义为:
?n? 设 n 元集合 A = {a1, a2, ?, an-1} + {an},则集合 A 的 r 元子集 ? ? 可以分为两类: ?r ? ? ?

(n ? 1)!(n ? r ? r ) n! = r!(n ? r )! r!(n ? r )!

① r 元子集含 an: 集合{a1, a2, ?, an}的 r 元子集即是集合{a1, a2, ?, an-1}的 r-1 元子集, 共有 ? ?

? n ? 1? ? 个; ? ? r ?1?

② r 元子集不含 an: 集合{a1, a2, ?, an}的 r 元子集即是集合{a1, a2, ?, an-1}的 r 元子集, 共有 ? ?

? n ? 1? ? 个。 ? ?r ?

? n ? ? n ? 1? ? n ? 1? 由加法原理,得: ? ? ? ? ? r ? ? r ? ? ? r ?1? 。 ? ? ? ? ? ? ? ? ?

例 2 设 A = {1, 2, 3, 4},则
?{1,2,3,4}? ?{1,2,3}? ?{1,2,3}? ?{4}? ? ??? ??? ??? ? ?2 ? ?2 ? ?1 ? ?1 ? ? ? ? ? ? ? ? ?



22

组合数学讲义

第3章

二项式定理与多项式定理

?{1,2,3,4}? ? ? ? {{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}} ?2 ? ? ? ?{1,2,3}? ? ? ? {{1,2}, {1,3}, {2,3}} ?2 ? ? ? ?{1,2,3}? ?{4}? ? ? ? ? ? ? {{1,4}, {2,4}, {3,4}} ?1 ? ?1 ? ? ? ? ?

(对应第②类)

(对应第①类)

性质 3 单峰性: ① n 为偶数时: ? ? < ? ? < ? < n > ? > ? ? 0 ? ?1 ? ? n ?1? > ? n ? ; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

?n? ?n?

?n ? ? ? ?2?

?n

? ?n?

② n 为奇数时: ? ? < ? ? < ? < ? n ? 1 ? = ? n ? 1 ? > ? > ? ? 0 ? ?1 ? ? n ?1? > ? n ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

?n? ?n?

?n

? ?n

?

?n

? ?n?

? 2 ? ? 2 ?

证明:考虑连续两个二项式系数之比:

?n? n! ? ? ?k ? n ? k ?1 k!(n ? k )! ? ? = = n! k ?n ? ? ? k ? 1? (k ? 1)!(n ? k ? 1)! ? ? ?
(1)当 n 为偶数时,则 ·若 k ?
n 为正整数,则 2

n n n ,则 n ? k ? 1 ? n ? ? 1 ? ? k ,所以 2 2 2

?n ? ?n? ? ? > ? ? k ?1? 。 ? ?k ? ? ? ? ?

·若 k ?

n n n ? 1 ,则 n ? k ? 1 ? n ? ( ? 1) ? 1 ? ? k ,所以 2 2 2
n ?1 n ?1 和 为整数,则 2 2
n

?n ? ?n? ? ? < ? ? k ?1? 。 ? ?k ? ? ? ? ?

(2)当 n 为奇数时,则 ·若 k ?

? ? ? ? n ?1 ,则 n ? k ? 1 ? 2k ? k ? k ,所以 ? n ? 1 ? ? ? n ? 1 ? 。 ? ? ? ? 2 ? ? ? ? n ? 2 ? ? 2 ?

·若 k ?

?n? ?n ? n ?1 n ?1 n ?1 ?1 ? ? k ,所以 ? ? ? ? ,则 n ? k ? 1 ? n ? ? k ? ? k ? 1? 。 ? 2 2 2 ? ? ? ?

23

组合数学讲义

第3章

二项式定理与多项式定理

·若 k ?

?n? ?n ? n ?1 n ?1 n ?1 ,则 n ? k ? 1 ? n ? ?1 ? ? 2 ? k ,所以 ? ? ? ? ? k ? ? k ? 1? 。 ? 2 2 2 ? ? ? ?

二项式系数的基本性质与杨辉三角形(又称 Pascal 三角形)相对应。
?0? ? ? ?0? ? ?

1 1 1 1 1 4 3 6 2 3 4 1 1 1 1
?4? ? ? ?0? ? ? ?3? ? ? ?0? ? ? ?2? ? ? ?0? ? ?

?1 ? ? ? ?0? ? ?

?2? ? ? ?1 ? ? ?

?1? ? ? ?1? ? ?

?2? ? ? ?2? ? ?
? 3? ? ? ? 3? ? ?

杨辉三角形

?4? ? ? ?1 ? ? ?

? 3? ? ? ?1 ? ? ?

?4? ? ? ?2? ? ?

?3? ? ? ?2? ? ?

?4? ? ? ?3? ? ?

?4? ? ? ?4? ? ?

对称性: ? ? = ? ? , ? ? = ? ? ; ? 0 ? ? 3 ? ?1 ? ? 2 ? ? ? ? ? ? ? ? ? 肩性: ? ? = 3, ? ? = 1, ? ? = 2 ? ? ? = ? ? + ? ? ; ? 2? ?1 ? ? 2? ? 2 ? ?1 ? ? 2? ? ? ? ? ? ? ? ? ? ? ? ? 单峰性: ? ? = 1 < ? ? = 3 = ? ? > ? ? = 1; ? 0? ?1 ? ? 2? ? 3? ? ? ? ? ? ? ? ?

?3 ? ? 3?

? 3? ?3 ?

?3?

? 2?

? 2?

?3?

? 2? ? 2?

?3?

? 3?

?3?

? 3?

? 4? ? ? =1< ?0? ? ?

? 4? ? ? =4< ?1 ? ? ?

? 4? ? ? =6> ? 2? ? ?

? 4? ? ? =4> ?3? ? ?

? 4? ? ? =1 ? 4? ? ?

3.1.3 组合恒等式
(1) ? ? + ? ? + ?? + ? ? = 2n ? 0 ? ?1 ? ?n? ? ? ? ? ? ? 证明:在二项式定理中令 x = y = 1 即可,其组合意义是二项式系数之和为 2n。 (2) ? ? + ? ? + ? ? + ?? = ? ? + ? ? + ? ? + ?? ?0? ?2? ?4? ?1 ? ? 3 ? ? 5 ? ? ? ? ? ? ? ? ? ? ? ? ? 证明:在二项式定理中令 x = -1,y = 1(或 x = 1,y = -1)即可,其组合意义是:在 n 元集合中取 r 组合,r 为奇数的组合数目等于 r 为偶数的组合数目(包括 0 组合)

?n? ?n?

?n?

?n? ?n? ?n?

?n? ?n? ?n?

24

组合数学讲义

第3章

二项式定理与多项式定理

(3)1× ? ? +2× ? ? + ?? + n× ? ? = n×2n-1 ? ? ? ? ? ?
n

?n? ?1 ?

?n? ?2?

?n? ?n?

n i 证明:对等式 (1 ? x) ? ? x ,两边在 x = 1 处求导,得结论。 i ?0

(4) ? ? + ? ? + ?? + ? ? = ? ? ?k ? ?k ? ? k ? ? k ? 1? ? ? ? ? ? ? ? ?

? 0 ? ?1 ?

? n ? ? n ? 1?

? n ? 1? 证明:其组合意义是:? ? k ? 1? 是 n + 1 元集合 A = {a1,…an,an+1}的 k + 1 元子集的个数, ? ? ?
这些子集可以分为如下 n + 1 类: 第 1 类:k + 1 元子集中含 an+1,这相当于 A-{ an+1}的 k 元子集再加上 an+1 构成 A 的 k + 1

?n? 元子集,共有 ? ? 个; ?k ? ? ?
第 2 类:k + 1 元子集中不含 an+1 但含 an,这相当于 A-{an, an+1}的 k 元子集再加上 an 构成

n ? 1? A 的 k + 1 元子集,共有 ? ? ?; ?k ? ? ?
?? 第 n + 1 类: + 1 元子集中不含 a2, ??, an, an+1 但含 a1, k 这相当于 A-{a1, a2, ??, an, an+1} 的 k 元子集再加上 a1 构成 A 的 k + 1 元子集,共有 ? ? 个。 ? ?

?0? ?k ?

由加法原理,知 ? ?

? n ? 1 ? ? 0 ? ?1 ? ?n? ? = ? ? + ? ? + ?? + ? ? 。 ? ?k ? ?k ? ?k ? ? k ? 1? ? ? ? ? ? ?
? n ? 1? ? 4 ? ? = ? ? ,即 n = 3,k = 1,则 ? ? ? ? k ? 1? ? 2 ?
——① ——② ——③

例 3 A = {1,2,3,4}, ? ?

?4? ? ? ={ {1,4}, {2,4}, {3,4}, ?2? ? ?

{1,3}, {2,3}, {1,2} }

? n ? ? {1,2,3} ? ? = {{1}, {2}, {3}} + {4} = {{1, 4}, {2, 4}, {3,4}} 而① = ? ? ? ? ? k ? ?1 ? ? ? ? ?

? n ? 1? ?{1,2}? ? ={{1}, {2}} + {3} = {{1, 3}, {2, 3}} ② = ? ? k ? ? ?1 ? ? ? ? ? ? ?
25

组合数学讲义

第3章

二项式定理与多项式定理

?1 ? ?{1}? ③ = ? ? ? ? ? = {{1}} + {2} = {{1, 2}} ? k ? ?1 ? ? ? ? ?

? 0 ? ?{} ? ④ = ? ? ? ? ? ? {} ? {1} ? {} ? k ? ?1 ? ? ? ? ?
(5) ? ? ? = ? ? ? ? ? ? i ?0 ? i ? ?n ? 证明:考虑二项式 ( x ? y)
2 n ? 2n ?
n

?n?

2

? 2n ?

2n

? ( x ? y) n ( x ? y) n 的展开式:

n ?n? n ?n? i 2 n ?i ? ? ? ?x i y n?i ? ? ? ?x i y n?i ? ? ?x y ? ? ? ? ? ? i ?0? i ? i ?0? i ? i ?0? i ?

等式左边 xnyn 的系数为 ? ?

? 2n ? ? ,等式右边 xnyn 项为 ? ?n ?

? n ? n ? n ? n ? n ? n?1 ? n ? n?1 ?n? n ? n? n ? ? y ? ? ? x ? ? ? xy ? ? ?0? ?n? ?1 ? ? n ? 1? x y ? ? ? ? n ? x ? ? 0 ? y ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
则等式右边 xnyn 的系数为 ? ? ? 。 ? ?
?n? i ?0 ? i ?
n 2

?n? ? 2n ? 因此, ? ? ? ? ? ? 。 ?i ? ?n ? i ?0? ? ? ?
n

2

更一般地,有如下 vadermonde 恒等式: (6)

??i ?

? m ?? n ? ? m ? n ? ?? ? ?? r ? i ? = ? r ? ? ? i ?0 ? ?? ? ? ?
r

证明:考虑二项式 ( x ? y)
m?n ? m ? i ?0

m?n

? ( x ? y) m ( x ? y) n 的展开式:

?? ?

?i

n ? i m ? n ?i m ? m ? i m ?i n ? n ? i n ?i ?x y ? ? ? ?x y ? ? ? ?x y ? ? ? ? ? i ? 0? i ? i ? 0? i ? ?
?m ? n? ? ,等式右边 xrym+n-r 项为 ? r ? ?

等式左边 xrym+n-r 的系数为 ? ?

? m ? m ? n ? r n?r ? m ? m?1 ? n ? r ?1 n?r ?1 ?m? ?n ? r ?m n?r ? m ? ? y ? ? ?x y ? ? ? xy ?? ? ? ? ? ?xm ? ? y ?0 ? ?r ? ?1 ? ? r ? 1? x y ? ?m? ? r ? m ?x ? ? ? ? ? ? ? ? ? ? ? ? ?

26

组合数学讲义

第3章

二项式定理与多项式定理

则等式右边 xrym+n-r 的系数为

??i ?

? m ?? n ? ?? ?? r ? i ? ? i ?0 ? ?? ?
r

即:

??i ?

? m ?? n ? ? m ? n ? ?? ? ?? r ? i ? = ? r ? ? ? i ?0 ? ?? ? ? ?
r

?m ? n? ?种 例如: 假设从 m 名男生 n 名女生共 m + n 名学生中选出 r 名学生做代表, 显然有 ? ?r ? ? ?

选法。另一方面,可以选男 0 女 r、男 1 女 r-1、??、男 r 女 0,根据乘法原理和加法原理,
? m ?? n ? ? m ?? n ? ? m ?? n ? 共有 ? ?? ? ? ? ?? ? 0 ?? r ? ?1 ?? r ? 1? ? ? ? ? r ?? 0 ? 种选法。显然,这两种选取方法的计数结果相等,即有: ? ? ?? ? ? ?? ? ? ?? ? ? ?? ?

??i ?
(7)

? m ?? n ? ? m ? n ? ?? ? ?? r ? i ? = ? r ? ? ? i ?0 ? ?? ? ? ?
r m

??i ?

? m ?? n ? ? m ? n ? ?? ?? r ? i ? = ? m ? r ? ? ? ? i ?0 ? ?? ? ? ?
m ? m ?? n ? m ? m ?? n ? ? m? ? m ? ? ,则 ? ? ?? ? = ?? ?? ? ? =? ? ? ?? ? ? ?? ? ? ? i ?0 ? i ?? r ? i ? i ?0 ? m ? i ?? r ? i ? ?i ? ? m ? i ?

证明:因为 ? ?

令 j=m- i,则: ? ?

? m ?? n ? ? m ?? n ?? ? ? ? ?? ?? ? ? ?? ? m ? i ?? r ? i ? ? j ?? m ? r ?

? ? j? ?
? m ? m ?? n ? ? ? ? ?? j ? j ?0? j ?? m ? r ? ? ? ?? ? ?m ? n? ??? ? j? ?m ? r ? ? ? ?

由 vadermonde 恒等式得:
? m ?? n i ?0 ? j ?? m ? r ?

? ? ?? ? ??

m

m ? m ?? n ? ? ? ? ? ?? ? j ? m? j ?0 ? j ?? m ? r ? ? ??

0 ? m ?? n ? ? ? ? ? ?? ? j ? j ?m ? j ?? m ? r ? ? ??

3.2

多项式定理

把二项式 ( x ? y) n 推广到 r 项式 ( x1 ? x2 ? ? xr ) n ,得到多项式定理。 多项式定理 设 n, r 为正整数,则
?n ? n1 n2 nr ( x1 ? x2 ? ? ? xr ) n ? ? ? ? n , n , ?, n ?x1 x2 ? xr ? r? ? 1 2

?n ? n! 其中 ? ? n , n ,?, n ? ? n !n !?n ! 称为多项式系数,∑是对所有满足 n1 + n2 + ? + ? r? 1 2 r ? 1 2
nr= n 的非负整数序列 n1, n2 , ?, nr 求和。
27

组合数学讲义

第3章

二项式定理与多项式定理

n 证明: ( x1 ? x2 ? ? ? xr ) ? ( x1 ? x2 ? ? ? xr )( x1 ? x2 ? ? ? xr )?( x1 ? x2 ? ? ? xr ) 共 n 个因子,

将其展开直到没有括号。展开后,因为每个因子中都可以取 x1 x2 ? xr 中的任一个,所以展开 式共有 rn 项,且每项都可以写成 x1 1 x2 2 ? xr r 的形式,要得到此项,应该在 n 个因子中取 n1 个 x1,共有 ? ? 种取法, 在剩下的 n- n1 个因子中取 n2 个 x2,共有 ? ? ? ?
?n ? ? n1 ? ? n ? n1 ? ? 种取法,??, ? ? n2 ?
n n n

? n ? (n1 ? n2 ? ? ? nr ?1 ) ? ? 种取法, 最后在 nr = n-(n1 + n2 + ? + nr-1)个因子中取 nr 个 xr,共有 ? ?n ? ? r ?

由乘法原理知, x1 1 x2 2 ? xr r 的系数为:

n

n

n

? n ?? n ? n1 ? ? n ? (n1 ? n2 ? ? ? nr ?1 ) ? n! ??? ?? ? ?? ? n ?? n ? ?n ? n !n !?n ! r ? 1 ?? 2 ? ? r ? 1 2
例 4 用多项式定理展开 ( x1 ? x 2 ? x3 ) 4 解: ( x1 ? x2 ? x3 ) 4 ? ? ? ?
?4 ? r1 r2 r3 ?x1 x2 x3 ? ? r1r2 r3 ?

= x14 + x24 + x34 + 4x13x2 + 4x13x3 + 4x23x3 + 4x23x1 + 4x33x1 + 4x33x2 + 6x12x22 + 6x12x32 + 6x22x32 + 12x1x22x3 + 12x12x2x3 + 12x1x2x32 例 5 确定 ( x1 ? x2 ? x3 ? x4 ? x5 )10 的展开式中 x13 x2 x34 x52 的系数。
?10?? 7 ?? 6 ?? 2 ? ?10 ? 解: ? ?? ?? ?? ? ? ? ? 3 ??1 ?? 4 ?? 2 ? ? 3,1,4,2 ? ? ? ?? ?? ?? ? ? ?

10! 7! 6! 2! 10! ? ? ? ? 3!7! 1!6! 4!2! 2!0! 3!1!4!2! = 12600 ?
n ? n ? r ? 1? ?: ?? ?r ? r ? ? n (1)n 元多重集合的 r 组合数为 ; r

以下问题的计数均为

(2)方程 x1 + x2 + ? + xn = r(n, r 为正整数)的非负整数解的个数为 ? ?

? n ? r ? 1? ?; ? ?r ?

28

组合数学讲义

第3章

二项式定理与多项式定理

(3)r 个相同的球放入 n 个有区别的盒子中,允许有空盒的放法有 ? ?
? n ? r ? 1? ?。 ? ? n ? r ?1 ? ? r ?1? ?? 以下问题的计数均为 ? r ? n ? ? ? n ? 1?,其中m ? r ? n 。 ? ? ? m ? ? ? ?

? n ? r ? 1? ? 种; ? ?r ?

(4) ( x1 ? x2 ? ? xn ) 展开式的项数为 ? ?r ?
r

先推导

n ? r ?1 ? ? r ?1? ??? ?: ?? m ? r ? n ? ? n ? 1? ? ? ? ? n n ? n ? (r ? n) ? 1? ? r ? 1 ? ? r ? 1 ? ? r ?1? ??? ? ?? ?r ? n ? ? r ? n ? ? ? (r ? 1) ? (r ? n) ? ? ? n ? 1? ? ? ? ? ? m r?n ? ? ? ? ? ? ? ? n n ? ; r?n m ? r ?1? ?; ? ? n ? 1? ? r ?1? ? 种; ? ? n ? 1? ? r ?1? ?。 ? ? n ? 1?

(1)n 元多重集合的 r-n 组合数是

(2)方程 x1 + x2 + ? + xn = r(n, r 为正整数)的正整数解的个数为 ? ?

(3)r 个相同的球放入 n 个有区别的盒子中,不允许有空盒的放法有 ? ?
r

r r r (4) ( x1 ? x2 ? ? xn ) 展开式中含 x11 x22 ? xnn 且 ri≥1(1≤i≤n)的项数为 ? ?

3.3

Stirling 数(司特林数)

定义 1 第 1 类 Stirling 数:n 个相同的球放进 r 个有区别的盒子且允许有空盒, 即 r 个盒子的球数依次为 n1, n2,?, nr,且 n1 + n2 + ? + nr = n(ni≥0,1≤i≤r) , 其方案数称为第 1 类 Stirling 数。 例1 n 个相同的球放进 2 个有区别的盒子,若第 1 个盒子放进 k 个球,则第 2 个盒子放

进的球数为 n-k 个, 即方案数正好是 ( x ? y) n 中 xkyn-k 项的系数 ? ? , ? ? ? k ? 则总方案数为 ? 0 ? + ?1 ? ? ? ? ? ? ? ? ? + ? + ? ? =2n。 ?n? ? ? 将上面的讨论推广,n 个相同的球放进 r 个有区别的盒子,若第 1 个盒子放 n1 个球,其方

?n?

?n?

?n?

?n?

? n ? n1 ? ?n ? ? ,??, 案数为 ? ? ,从余下的(n-n1)个球中取出 n2 个放进第 2 个盒子,其方案数为 ? ?n ? ?n ? ? 1? ? 2 ? ? n ?? n ? n1 ?? n ? n1 ? n2 ? ? nr ?1 ? ?? ? ,即为 ( x1 ? x2 ? ? ? xr ) n 的多项式系 由乘法原理得,其方案数为: ? ?? ? n ?? n ?? n ? ? 1 ?? 2 ?? r ?
数,因此总方案数为:
29

组合数学讲义

第3章

二项式定理与多项式定理

?n ? n ? ? n ,n , ? , n ? ? r ? n1 ? n 2 ??? n r ? n? 1 2 r?

?

? n ? r ? 1? n ?, 定理 1 ( x1 ? x2 ? ? ? xr ) n 展开式的项数为 ? ?n ? 这些项的系数之和等于 r 。 ? ?
定义 2 第 2 类 Stirling 数: 个相同的球放进 r 个有区别的盒子且不允许有空盒, n 即 r 个盒子的球数依次为 n1, n2,?, nr,且 n1 + n2 + ? + nr = n(ni≥1,1≤i≤r) , 其方案数称为第 2 类 Stirling 数。 例 2 n 个相同的球放进 2 个有区别的盒子,若第 1 个盒子放进 k 个球,则第二个盒子 放进的球数为 n-k 个,由于要求两个盒子都不能为空,其方案数正好是 ( x ? y) n 中 xkyn-k 项的系
n 数 ? ? (k>0 且 n-k>0) ,则总方案数为 ? ? + ? + ? ? n ?1? =2 -2。 ? ?1 ? ?k ? ? ? ? ? ? ?

?n?

?n?

?n

?

定理 2

r 元多重集合{∞·a1, ∞·a2, ?, ∞·ar}上限定 ai(1≤i≤r)的重数

为 ni(1≤ni≤n)的 n 排列数为: ? ?

?n ? ? ,其中 n1 + n2 + ? + nr = n。 ? ? n1 ,n 2 , ?, nr ?

例 3 将 5 个不同的球{a,b,c,d,e}放进 3 个不同的盒子中,使得第 1 个盒子放 2 个, 第 2 个盒子放 2 个,第 3 个盒子放 1 个,其可能的放法有多少种? 解:由题意得 n = 5,m = 3,n1 = 2,n2 = 2,n3 = 1,则
?5 ? 5! 5* 4 *3* 2 ? ? 30 ? 2,2,1? ? 2!?2!?1! ? ? 2*2 ? ?

例如:{ab / cd / e},{ab / ce / d},{ab / de / c},??。 以下问题的计数均为 rn: (1)n 个有区别的球放入 r 个有区别的盒子中,允许有空盒的放法有 rn 种(属于多重集 合的排列问题) ; (2)n 个不同的球放入 r 个有区别的盒子中,第 i 个盒子放 ni(1≤i≤r)个球的放法总 数(即取遍 n1 + n2 + ? + nr= n)为:

?n ? n ? ? n ,n , ? , n ? ? r ; ? n1 ? n 2 ??? n r ? n? 1 2 r?

?

(3)多项式 ( x1 ? x2 ? ? xr ) 的展开式中全部系数之和为:
n

30

组合数学讲义

第3章

二项式定理与多项式定理

?n ? n ? ? n ,n , ? , n ? ? r ? n1 ? n 2 ??? n r ? n? 1 2 r?

?

(4)r 元多重集合{∞·a1, ∞·a2, ?, ∞·ar}上限定 ai(1≤i≤r)的重数为 ni(1≤ni ≤n)的 n 排列数为:

?n ? n ? ? n ,n , ? , n ? ? r 。 ? n1 ? n 2 ??? n r ? n? 1 2 r?

?

3.4

集合的分划

加法原理应用的前提是:将集合分解为不相交的子集。

3.4.1 集合分划的定义
定义 1 设 A1,A2,…,Ak 是 A 的 k 个子集,若满足: (1)Ai ≠Φ(1≤ i ≤ k) (2)Ai∩Aj = Φ(1≤ i≠j ≤ k) (3)A = A1∪A2∪…∪Ak 则称{A1,A2,…,Ak}是 A 的一个 k 分划,并记为:A=A1∪A2∪…∪Ak。 理解:n 元集合 ?? n 个不同的球; k 个子集 ?? k 个相同的盒子,即无序; Ai 非空 ?? 不允许有空盒。 例 1 集合 A={1,2,3,4}有 7 个 2 分划,分别是: {1,2,3,4} = {1}∪{2, 3, 4} = {2}∪{1, 3, 4} = {3}∪{1, 2, 4} = {4}∪{1, 2, 3} = {1, 2}∪{3, 4} = {1, 3}∪{2, 4} = {1, 4}∪{2, 3} 定义 2 一个 n 元集合的全部 k 分划的个数为第 2 类 stirling 数,记作 S(n, k)。 由 S(n, k)的定义易知: S(n,1) = 1 S(n,n) = 1 S(n,k) = 0 (k > n)
31

组合数学讲义

第3章

二项式定理与多项式定理

定理 1

第二类 stirling 数 S(n, k)满足如下递归关系: S(n + 1, k) = S(n, k - 1) + k×S(n, k) (1≤k≤n)

证明:这个证明方法也是构造集合 A 的所有 k 分划的方法。 S(n + 1, k) 是集合 A = {a1, a2,?, an, an+1 } 的 k 分划的个数,这些 k 分划可以分成两类: (1) n+1}是 A 的 k 分划中的一块, {a 这时, 只需对集合 A-{an+1}进行 k-1 分划, 再加上{an+1} 这块,就构成了 A 的 k 分划,因此,这类分划有 S(n, k - 1) 个。 (2){an+1}不是 A 的 k 分划中的一块,这时,先构造集合 A-{an+1}的 k 分划,共有 S(n, k) 个,然后,对 A-{an+1}的每个 k 分划,分别将 an+1 加到 k 个块中,从而构成 A 的 k 分划,由乘 法原理,A 的此类 k 分划共有 k×S(n, k)。 例 2 A = {1,2,3,4}的 3 分划可以分成两类; (1){4}是 A 的 3 分划中的一块,此时,对{1,2,3}进行 2 分划,有: {1,2,3} = {1}∪{2,3} = {2}∪{1,3} = {3}∪{2,1} 则含有{4}的 3 分划共有 3 个,分别为: {1,2,3,4} = {1}∪{2,3}∪{4} = {2}∪{1,3}∪{4} = {3}∪{2,1}∪{4} (2){4}不是 A 的 3 分划中单独的一块,此时,对{1,2,3}进行 3 分划,有: {1,2,3} = {1}∪{2}∪{3} 将{4}加到{1,2,3}的 3 分划中的每一块,则含有{4}的 3 分划共有 3 个,分别为: {1,2,3,4} = {1,4}∪{2}∪{3} = {1}∪{2,4}∪{3} = {1}∪{2}∪{3,4}

3.4.2 第 2 类 stirling 数的性质
第 2 类 stirling 数满足如下基本性质: 性质 1 S(n, 2) = 2n-1 -1 性质 1 的组合意义是:S(n, 2) 是 n 元集合 A={a1,a2,…,an}的 2 分划数,具体分划放 法是,先取出 a1,则对于 A-a1={a2,a3,…,an}的每个元素 ai (2≤i≤n)都有两种选择: (1)ai 与 a1 在同一块中; (2)ai 与 a1 不在同一块中。 不同的选择构成了集合 A 的不同的 2 分划,但要排除 a2,a3,…,an 都与 a1 在同一块中 的情况,此时不构成集合 A 的 2 分划,因此,S(n, 2) = 2n-1 -1。 例 3 A = {1,2,3},则 S(n, 2) = 2n-1 -1 = 3,具体的 2 分划为: A = {1}∪{2,3} = {1,2}∪{3} = {1,3}∪{2} A = {1,2,3,4},则 S(n, 2) = 2n-1 -1 = 7,具体的 2 分划为: A = {1}∪ {2,3,4} = {1,2}∪ {3,4} = {1,3}∪ {2,4} = {1,4}∪ {2,3} = {1,2,3}∪ = {1,2,4}∪ = {1,3,4}∪ {4} {3} {2}
32

组合数学讲义

第3章

二项式定理与多项式定理

性质 2

S(n, n - 1) = ? ? ? ?

?n? ?2?

性质 2 的组合意义是:S(n, n - 1)是 n 元集合 A = {a1,a2,…,an}的 n-1 分划数,由于分 划中的 n-1 块均非空,则 n-1 块中必有 1 块有 2 个元素,其余各块都恰有一个元素。所以,只 要确定了有 2 个元素的块,整个 n-1 分划就确定了,因此,S(n, n - 1)就是在 n 元素中取 2 个元 素的方法数 ? ? 。 ? ?
n ?n ? S(n + 1, k) = ? ? ?S ( m, k ? 1) ? ? m ? k ?1 ? m ?

?n? ?2?

性质 3

证明:S(n + 1, k) 是集合 A = {a1,a2,…,an,an+1}的 k 分划数,对于 A 的一个 k 分划, 设包含 an+1 的块为 B(即 an+1∈ 但 B≠{an+1}) B ,则其余的 k -1 块构成了 A-B 的一个 k -1 分 划;反过来,给定 A 的一个包含 an+1 的集合 B,若|A-B|≥k -1,则 A-B 的 k -1 分划再加上 B 就构成了 A 的一个 k 分划。 可以如下构造 A 的 k 分划: (1)先取 A 的一个不含 an+1 的子集 C,使|C|≥k -1; (2)作出 C 的一个 k -1 分划; (3)再拼上 A-C = B 就构成了 A 的一个 k 分划,而 m=|C|可以取 k -1, k,?, n。 对于确定的 m,从 A 中取 C 的方案有 ? ? 由加法原理和乘法原理,有
n ?n ? S(n + 1, k) = ? ? ?S ( m, k ? 1) ? ? m ? k ?1 ? m ?

?n ? ? ,确定了 C 之后,C 的 k -1 分划为 S(n, k - 1), ? ? m?

例4

A = {1, 2, 3, 4}(n=3, k=2) ,
3 ?3 ? 3 ? 3 ? ? 3? ? 3 ? ? 3? S (4,2) ? ? ? ?S (m,1) ? ? ? ? ? ? ? ? ? ? ? ? ? ? 7 ? m? ? ? ? ? ? ? ? ? m?1 ? ? m?1 ? m ? ?1 ? ? 2 ? ? 3 ?

A 的 2 分划为: A = {1}∪ {2,3,4} = {1,2}∪ {3,4} = {1,3}∪ {2,4} = {2,3}∪ {1,4} = {1,2,3}∪ = {1,2,4}∪ = {1,3,4}∪ {4} {3} {2}
? 3? ? ? ? 1 ,设 C = {1, 2, 3},则 A-C = B = {4},即 ? 3? ? ?

S(3, 1) ={1, 2, 3}∪ {4}
?3 ? ? ? ? 3 , C = {1, 2}, A-C = B = {3, 4}; C = {1, 3}, A-C = B = {2, 4}; 设 则 设 则 ? 2? ? ?
33

组合数学讲义

第3章

二项式定理与多项式定理

设 C = {2, 3},则 A-C = B ={1, 4},即 S(2, 1) = {1, 2}∪ 4} = {1, 3}∪ 4} = {2, 3}∪ 4} {3, {2, {1,
? 3? ? ? ? 3 , C = {1}, A-C = B = {2, 3, 4}; C = {2}, A-C = B = {1, 3, 4}; 设 则 设 则 ?1 ? ? ?

设 C = {3},则 A-C = B = {1, 2, 4},即 S(1, 1) = {1}∪ 3, 4} = {2}∪ 3, 4} = {3}∪ 2, 4} {2, {1, {1,

3.5

正整数的分拆

定义 1 正整数 n 的一个 k 分拆是把 n 表示成 k 个正整数的和,即 n = n1 + n2 + ? + nk (k≥1) (式 1)

其中 ni(ni > 0,1≤i≤k)称为该分拆的分部量,n 的 k 分拆的个数称为 n 的 k 分 拆数,n 的所有分拆的个数(即 k 取遍所有可能的值)称为 n 的分拆数。

3.5.1 有序分拆
在定义 1 中,如果式 1 是有序的,即式 1 右边的和式不仅与各项的 ni 有关,而且与 ni 的 次序有关,不同的次序被看作是的分拆,则称为有序分拆。 正整数 n 的有序 k 分拆的个数为 ? ?

定理 1

? n ? 1? ?。 ? ? k ? 1?

证明:正整数 n 分成 k 个分部量的一个有序分拆为: n = n1 + n2 + ? + nk 等价于方程: x1 + x2 + ? + xk=n 的正整数解(n1, n2, n3, ?, nk) ,其解的个数为 ? ?

? n ? 1? ?。 ? ? k ? 1?

例 1 5 的 3 分拆个数为 ? ?

? 5 ? 1? ? 4 ? ? 4! ? 6 ?=? ? ? ? 3 ? 1? ? 2 ? 2!*2! ? ?

5=1+1+3=1+2+2=1+3+1=2+1+2=2+2+1=3+1+1 下述定理给出了几种不同限定条件下的有序分拆数,证明留给学生。
34

组合数学讲义

第3章

二项式定理与多项式定理

定理 2

正整数 n 的有序 k 分拆,要求第 i 个分部量大于等于 pi,其个数为:
k ? ? ? n ? k ? ? p i ? 1? 。 i ?1 ? ? ,其中(1≤i≤k) ? k ?1 ? ? ?

例 2 9 的有序 3 分拆,要求所有分部量都大于等于 2,其个数为:

? 9 ? 3 ? 6 ? 1? ? 5 ? ? ? = ? ? =10 ?3 ?1 ? ? 2? ? ? ? ?
9=2+2+5=2+3+4=2+4+3=2+5+2 =3+2+4=3+3+3=3+4+2 =4+2+3=4+3+2 =5+2+2 定理 3 正整数 2n 分拆成 k 个分部,各分部量都是正偶数的有序分拆个数为:

? n ? 1? ? ? k ? 1? ? ? ?
例 3 n = 4,则 8 的 3 分拆的各有序分部量都是正偶数的分拆个数为: ? ? =3。 ? ? 8=2+2+4=2+4+2=4+2+2 定理 4 正整数 n 分拆成 k 个分部,若 n 与 k 同为奇数或同为偶数,则 n 的各分

?3? ? 2?

?n?k ? ? 1? ? 部量都是奇数的有序分拆数为: ? 2 ? ? k ?1 ? ? ? ?5?3 ? 3 ? 1? ? ? ? 例 4 5 分拆成 3 个分部且各分部量都是奇数的有序分拆数为: ? ? ? 2 ? = ? 2 ? =3。 ?3 ?1 ? ? ? ? ?
5=1+1+3=1+3+1=3+1+1

3.5.2 无序分拆
在定义 1 中,如果式 1 是无序的,即对 ni 任意换位后的分拆都视为同一种分拆,则称为 无序分拆,简称分拆。 由于在 n 的 k 分拆中,各分部量的次序无关紧要,一般按降序排列,即: n = n1 + n2 + ? + nk (n1≥n2≥?≥ nk)
35

组合数学讲义

第3章

二项式定理与多项式定理

如果在 n 的 k 分拆中有 ki 个分部量为 i(1≤i≤n) ,则该分拆记为: n = k1× + k2× + ? + kn× 1 2 n 有时也记为:

n ? 1k1 2 k2 ? n kn (ki≥0)
用 B(n,k)表示 n 的 k 分拆的个数,用 B(n)表示 n 的所有分拆的个数,则显然有: B(n,k) = 0 B(n) = ? B(n, k ) B(n,2) = ?n 2? 前两个式子是显然成立的,下面讨论第 3 个式子。 设 n 的 2 分拆为:n = n1 + n2(n1≥n2) ,因为 n1≥n2,所以 n2 恰能取 1, 2, ?, 任一个,故 B(n,2) = ?n 2? 。 例 5 B(5,2) = 3 + 2 = 4 + 1,而 ?5 2? =2。 定理 1 n 的最小分部量为 1 的 k 分拆数等于 n-1 的 k-1 分拆数。
k ?1 n

(k > n) (1≤k≤n)

?n 2? 中的

证明:设 n 的一个最小分部量为 1 的 k 分拆为: n = n1 + n2 + ? + nk-1 + 1 显然,n-1 = n1 + n2 + ? + nk-1 是 n-1 的一个 k-1 分拆,即构造了一个从 n 的最小分部量为 1 的 k 分拆到 n-1 的 k-1 分拆之间的一一对应,所以两类分拆数相等。 定理 2 n 的 k 分拆数 B(n,k)满足如下递推关系: B(n, 1) = 1 B(n, n) = 1 B(n+k, k) = B(n, 1) + B(n, 2) + ? + B(n, k)

证明:考虑 n 的至多 k 个分部的分拆,其总数为: B(n, 1) + B(n, 2) + ? + B(n, k) n 的至多 k 个分部的分拆可以表示为: n = n1 + n2 + ? + nm + 0 + ? + 0 共k项 定义映射: n+k =(n1+1) + (n2+1) + ? +(nm+ 1) + 1 + 1 + ? + 1 (1≤m≤k,n1≥n2≥n3≥……≥nm≥1)

36

组合数学讲义

第3章

二项式定理与多项式定理

满足: n1+1≥n2+1≥ ? ≥nm+1≥2 由于映射是一一映射,则 B(n+k, k) = B(n, 1) + B(n, 2) + ? + B(n, k)

3.5.3 分拆的 Ferrers 图(费若斯图)
Ferrers 图是研究分拆数性质的一种简单有效的组合手段。 例 6 15 的 4 分拆,如 15 = 5 + 5 + 3 + 2 的 Ferrers 图如下:

共轭图
180
o

对于 n 的一个 Ferrers 图,按上述规则对应于 n 的唯一一个分拆,所以,n 的分拆同它的 Ferrers 图之间是一一对应的。把一个 Ferrers 图的行变列,但其相对位置不变,这样的 Ferrers 图的称为原 Ferrers 图的共轭图,共轭 Ferrers 图对应的分拆称为原分拆的共轭分拆,若 n 的一 个分拆与其共轭分拆相同,则该分拆称为 n 的自共轭分拆。 例 7 15 = 4 + 4 + 3 + 2 + 2 是 15 = 5 + 5 + 3 + 2 的共轭分拆。 定理 1 n 的 k 分拆数等于 n 的最大分部量为 k 的分拆数。

证明:建立 n 的最大分部量为 k 的分拆到 n 的 k 分拆之间的意义映射关系,即共轭运算, 因此两者的分拆数相同。 例 8 15 = 5 + 5 + 3 + 2 的最大分部量为 5,其共轭分拆一定是一个 5 分拆,即: 15 = 4 + 4 + 3 + 2 + 2 例 9 8 的 3 分拆?? 8 的最大分部量为 3 的分拆。 8 的 3 分拆 8 的最大分部量为 3 的分拆。 8=6+1+1 8=3+1+1+1+1+1

8=5+2+1

8=3+2+1+1+1
37

组合数学讲义

第3章

二项式定理与多项式定理

8=4+3+1

8=3+2+2+1

8=4+2+2

8=3+3+1+1

8=3+3+2

8=3+3+2

定理 2 n 的自共轭分拆的个数等于 n 的各分部量都是奇数且两两不等的分拆数。 证明:建立一个 n 的各分部量为奇数且两两不等的分拆到 n 的自共轭分拆之间的一一映 射关系,设 n =(2n1+1)+(2n2+1)+ ? +(2nk+1) (其中 n1 > n2 > n3 > ? > nk > 0) 该 Ferrers 图是对称的,例如:17 = 9 + 5 + 3 =(2× 4+1)+(2× 2+1)+(2× 1+1) ,其 Ferrers 图如下:

+

+

=

对应的自共轭分拆为:17 = 5 + 4 + 4 + 3 + 1 再如:19 = 11 + 5 + 3=(2× 5+1)+(2× 2+1)+(2× 1+1) ,其 Ferrers 图如下:

+

+

=

对应的自共轭分拆为 19 = 6 + 4 + 4 + 3 + 1 + 1 所以其对应的分拆是自共轭的。 定理 3 n 的分部量两两不等的分拆数等于 n 的各个分部量都是奇数的分拆数。
38

组合数学讲义

第3章

二项式定理与多项式定理

证明:基本思想——建立两类不同分拆之间的一一对应。 n 的各分部量都是奇数的分拆: n =(2n1+1)+(2n2+1)+ ? +(2nk+1) (n1≥n2≥ ? ≥nk≥0) 其余证明步骤略。 例 12 7 = 3 + 3 + 1?? 7 = 4 + 2 + 1 11 = 5 + 5 + 1??11 = 6 + 4 + 1

3.6

综合应用——球盒分配问题

本节实际上是所学知识的综合应用。所谓球盒分配问题是把 n 个球放进 r 个盒子(假定球 在盒内是无序的),求共有多少种不同的方案? 球盒问题需要考虑以下因素: (1)n 个球是否相同? (2)r 个盒子是否有标志? (3)是否允许空盒? 则共有 23=8 种状态,下面分类讨论。 (1)把 n 个不同的球放入 r 个有区别的盒子,允许有空盒的方案数为 rn。 设 n 个不同的球构成集合 X = {x1, x2, ?, xn }, 个有区别的盒子构成集合 M = {a1, a2, ?, r ar },每个球 xi(i = 1, 2, ?, n)都可以放入 r 个不同的盒子中的任一个,即每个球都有 r 种不 同的放法,因而 n 个球共有 rn 种放法。 这个问题可以看成 r 个不同的盒子构成的多重集合{∞·a1, ∞·a2, ?, ∞·ar }的 n 排列 问题。 (2)n 个不同的球放入 r 个有区别的盒子,不允许有空盒的方案数为 r!× S(n,r)。 首先认为盒子是相同的,把 n 个不同的球构成集合 X = {x1, x2, ?, xn }分划成 r 个非空子 集 A1, A2, ?, Ar,然后将每个 Ai(1≤i≤n)放入一个盒子中,构成一个没有空盒的方案。这 里 A1, A2, ?, Ar 是集合 A 的一个 r 分划,其分划数为 S(n,r)。由于盒子是有区别的,则 r 个 盒子的不同排列其方案是不同的,因此,n 个不同的球放入 r 个有区别的盒子,不允许有空盒 的方案数为 r!× S(n,r)。 (3)n 个不同的球放入 r 个相同的盒子,不允许有空盒的方案数为 S(n,r)。 由(2)的分析可知,此类分配方案数为 S(n,r)。 (4)n 个不同的球放入 r 个相同的盒子,允许有空盒的方案数为 ? S (n, i) 。
i ?1 r

由于允许有空盒,设有 i(1≤i≤r)个盒子不空,则另外(r-i)个盒子为空,这相当于将 n 个不同的球放入 i 个相同的盒子,且不允许有空盒的一种放法,由加法原理及(3)可知,n 个不同的球放入 r 个相同的盒子,允许有空盒的方案数为 S(n,1)+ S(n,2)+ ? + S(n,m)。 (5)n 个相同的球放入 r 个相同的盒子,不允许有空盒的方案数为 B(n,r)。 这个问题相当于将整数 n 进行 r 分拆。 (6)n 个相同的球放入 r 个相同的盒子,允许有空盒的方案数为 ? B(n, i) 。
i ?1 r

39

组合数学讲义

第3章

二项式定理与多项式定理

这个问题相当于 n 用 1, 2, 3, ?, r 进行分拆的分拆数。
? n ? r ? 1? ?。 (7)n 个相同的球放入 r 个有区别的盒子,允许有空盒的方案数为 ? ?n ? ? ?

这相当于 r 个有区别的元素取 n 个作允许重复的组合,或求方程 x1 + x2 + ? + xn = r(n, r 为正整数)的非负整数解的个数。

? n ? 1? (8)n 个相同的球放入 r 个有区别的盒子,不允许有空盒的方案数为 ? ? r ?1? 。 ? ? ?
先取 r 个球每盒一个,余下的 n-r 个球放到 r 个盒子,相当于求方程 x1 + x2 + ? + xn = r (n, r 为正整数)的正整数解的个数。 球盒分配问题的结果如表 1 所示所示。
表1 球盒分配问题的方案数

序号 1 2 3 4 5 6

n 个球 不同 不同 不同 不同 相同 相同

r 个盒子 有区别 有区别 无区别 无区别 无区别 无区别

是否空盒 有空盒 无空盒 无空盒 有空盒 无空盒 有空盒

方案数 rn r!× S(n,r) S(n,r)
i ?1 r

? S (n, i)
B(n,r)

i ?1

? B(n, i)

r

7

相同

有区别

有空盒

? n ? r ? 1? ? ? ?n ? ? ?

8

相同

有区别

无空盒

? n ? 1? ? ? r ?1? ? ? ?

40

组合数学讲义

第4章

容斥原理与鸽笼原理

第4章

容斥原理与鸽笼原理

应用加法原理时, 要求所计数的集合必须能够分划成若干个两两不相交的子集, 而每个子 集又便于计数。在很多情况下,这种分划并非易事,如果所求计数的集合为彼此可能相交的子 集的并,则需要将加法原理推广。容斥原理又称包含排斥原理、交叉分类原理等,是加法原理 的一种推广形式。 鸽笼原理又称为抽屉原理、邮箱原理等,是组合学中一个最简单、最基本的原理,也是一 个极为重要的原理。

4.1

容斥原理

容斥原理是由 sylvester J.J 在 19 世纪提出的一种组合计数方法,它的基本思想并不复杂, 但应用却很广泛,除了解决计数问题外,在数论领域也有应用。容斥原理实际上是一种间接的 计数方法。

4.1.1 间接计数法
例 1 求{1, 2,?, n}的 1 不在第一个位置上的全排列的个数。 解:设 i1i2?in 是{1, 2,?, n}一个全排列,因 1 不在第一个位置上,所以 i1≠1,下面分别 用直接计数和间接计数两种方法来计算此类排列的个数。 ⑴ 直接计数:将 i1≠1 的所有全排列按照 i1 的取值分成 n-1 类:若 i1= k∈{2, 3, ?, n}, 则 i2?in 是{1,?,k-1, k+1, ?, n}的一个全排列,所以{1, 2,?, n}的使 i1=k 的全排列个数为 (n-1)!。由于 k 可取 2, 3,?, n,由乘法原理,i1≠1 的全排列数为(n-1)(n-1)!。 ⑵ 间接计数:{1, 2,?, n}的全排列数为 n!,若 i1=1,则 i2?in 是{2, 3, ?, n}的全排列, 共有(n-1)!,所以 i1≠1 的全排列数为:n!- (n-1)! = (n-1)(n-1)! S 如图 4.1 所示,间接计数方法用集合论的语言 A 描述为: 设 A ? S, A 中的元素个数等于 S 中的 则 元素个数减去 S 中不在 A 中的元素个数,即:

A ? S ? A 或 A ? S ? A
41

图 4.1

间接计数法的集合描述

组合数学讲义

第4章

容斥原理与鸽笼原理

德摩根(De Morgan)定理

若 A ? S , B ? S ,则 A ? B ? A ? B , A ? B ? A ? B 。

例 2 求不超过 20 的正整数中是 2 或 3 的倍数的数的个数。 解:不超过 20 的数中 2 的倍数有 10 个: 2,4,6,8,10,12,14,16,18,20 不超过 20 的数中 3 的倍数有 6 个: 3,6,9,12,15,18 但其中为 2 或 3 的倍数的数只有 13 个, 而不是 10 + 6 = 16 个,因为 6,12,18 同时为 2 和 3 的倍数。 如图 4.2 所示,上述计数方法用集合论的语言描述为: 设 A ? S,B ? S,则 (1)若 A∩B = Φ,则 |A∪B| = |A| + |B| (直接应用加法原理) (2)若 A∩B≠Φ,则|A∪B|=|A|+|B|-|A∩B| 因为|A∩B|重复计算了一次,所以应减掉。 设 A ? S,B ? S,C ? S,则 (1)若 A∩B∩C=Φ,则 |A∪B∪C|=|A| + |B| + |C| (2)若 A∩B≠Φ 或 A∩C≠Φ 或 C∩B≠Φ,则 |A∪B∪C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |C∩B| + |A∩B∩C| 因为|A∩B∩C|多加了两次,被减掉了 3 次。 或将|A∪B∪C|逐步展开: |A∪B∪C| = |A∪B| + |C| - |(A∪B)∩C| =|A| + |B| - |A∩B| + |C| -(|A∩C| + |B∩C|-|A∩B∩C|) =|A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C| S C S A A∩B B A A∩B∩C B

图 4.2

容斥原理的集合描述

例 3 某校某学期开设三门课:数学,物理,化学,已知修这三门课的学生人数依次为: 170,130,120,兼修数学和物理这两门课的学生为 45 人,兼修数学和化学的有 20 人,同时 修物理和化学的学生为 22 人,同时修三门课的学生有 3 人,计算在校学生有多少人? 解:设 A:修数学的学生集合 B:修物理的学生集合 C:修化学的学生集合 则 |A| = 170,|B| = 130,|C| = 120,
42

组合数学讲义

第4章

容斥原理与鸽笼原理

|A∩B| = 45,|A∩C| = 20,|B∩C| = 22, |A∩B∩C| = 3。 在校学生人数为: |A∪B∪C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C| =170+120+130-45-20-22+3=336

4.1.2 容斥原理的三种形式

定理 1 设集合 S 的子集 A1 具有性质 P1,A2 具有性质 P2,?,An 具有性质 Pn, 则集合 S 至少具有性质 P1, P2,?, Pn 之一的元素个数为: |A1∪A2∪?∪An| = (|A1|+|A2|+?+|An|) - (|A1∩A2|+|A1∩A3|+?+|A1∩An| + (|A2∩A3|+?|A2∩An|+?|An-1∩An|) + (|A1∩A2∩A3| + ? + |An-2∩An-1∩An|) ?? +(-1)n-1|A1∩A2∩?∩An|
n ?1 即| ? Ai ? ? Ai ? ? ? Ai ? A j ? ? ? ? Ai ? A j ? Ak ? ? ? (?1) Ai ? ? ? An i ?1 i ?1 i ?1 j ?i i ?1 j ?i k ? j n n n n

证明:采用数学归纳法,证明过程略。 定理 2 设集合 S 的子集 A1 具有性质 P1,A2 具有性质 P2,?,An 具有性质 Pn, 则集合 S 不具有性质 P1,P2,?,Pn 之一的元素个数为:
A1 ? A2 ? ?? An ? A1 ? A2 ? ?? An ? S ? A1 ? A2 ? ?? An

即:
i ?1

? Ai ? S ? ? Ai ? ? ? Ai ? A j ? ? ? ? Ai ? A j ? Ak ? (?1) n A1 ? A2 ? ? ? An
i ?1 i ?1 j ?i i ?1 j ?i k ? j

n

n

n

n

证明:根据德摩根(De Morgan)定理,证明过程略。 所谓容斥原理就是上述两个公式,一个是求 ? Ai ,一个是求 ? Ai 。记住公式固然重要,
i ?1 i ?1 n n

更重要的是理解容斥原理的思想,利用容斥原理的思想解决问题。 例 4 某班有 50 名学生,进行语文,数学,外语考试,有 9 人语文满分,有 12 人数学的 满分,有 14 人外语得满分,又知道,有 6 人语文、数学都得满分,有 3 人语文、外语都得满 分,有 8 人外语、数学都得满分,有 2 人这三门课都是满分。 问:① 没有一门课程得满分的有几人? ② 至少有一门课程得满分的有几人? 解:设集合 S:所有学生
43

组合数学讲义

第4章

容斥原理与鸽笼原理

A:语文得满分的学生 B:数学得满分的学生 C:外语得满分的学生 则没有一门得满分的学生为
A ? B ?C ? S ? ( A ? B ? C ) ? ( A? B ? A?C ? B ?C ) ? A? B ?C

= 50 - ( 9 + 12 + 14 ) + ( 6 + 3 + 8) – 2 = 30 则至少一门课程的满分的学生为:
A? B ?C ? ( A ? B ? C ) ? ( A? B ? A?C ? B ?C ) ? A? B ?C

= ( 9 + 12 + 14 ) - ( 6 + 3 + 8 ) – 2 = 20 例 5 求 a,b,c,d 这四个字符构成的 n 位字符串,其中 a,b,c 至少出现一次的数目? 解:a, b, c 至少出现一次的反面就是 a, b, c 都不出现。 令集合 A1:n 位符号串中不出现字符 a 的事件; A2:n 位符号串中不出现字符 b 的事件; A3:n 位符号串中不出现字符 c 的事件; S:a,b,c,d 这四个字符构成的 n 位字符串的全体。 则 |S|=4n |A1| = |A2| = |A3| = 3n |Ai∩Aj|=2n(i≠j, i = 1,2,3) |A1∩A2∩A3| = 1 则
A1 ? A2 ? A3 ? S ? ( A1 ? A1 ? A3 ) ? ( A1 ? A2 ? A1 ? A2 ? A2 ? A3 ) ? A1 ? A2 ? A3

= 4n – 3×3n + 3×2n - 1 例 6 求不超过 100 的正整数中不能被 5,6,8 中任意一个数整除的元素的个数。 解:设集合 S:不超过 100 的正整数; A:S 中能被 5 整除的数的集合; B:S 中能被 6 整除的数的集合; C:S 中能被 8 整除的数的集合。 则 |A| = ?1000? =200
? 5 ? ? ?

|B| = ?1000? =166
? 6 ? ? ?

|C| = ?1000? =125
? 8 ? ? ?

设[m, n]表示 m 和 n 的最小公倍数,则 |A∩B| = ?1000? ? ?1000? ? 33 ? ? ? ?
? [5,6] ? ? 30 ?

|A∩C|= ?1000? ? ?1000? ? 25 ? ? ? ?
? [5,8] ? ? 40 ?

|B∩C| = ?1000? ? ?1000? ? 41 ? ? ? ? ? [6,8] ? ? 24 ? 则

|A∩B∩C| = ? 1000 ? ? ?1000? ? 8 ? ? ? ?
? [5,6,8] ? ? 120 ?

44

组合数学讲义

第4章

容斥原理与鸽笼原理

A ? B ?C ? S ? ( A ? B ? C ) ? ( A? B ? A?C ? B ?C ) ? A? B ?C

= 1000 – ( 200 + 166 + 125 ) + (33 + 25 + 41 ) – 8 = 600 例 7 求不超过 120 的素数的个数。 解:由于 112=121,则不超过 120 的合数必是 2,3,5,7 的倍数,而且不超过 120 的合 数的因子只能是 2,3,5,7。 令 A1:小于等于 120 且能被 2 除尽的数; A2:小于等于 120 且能被 3 除尽的数; A3:小于等于 120 且能被 5 除尽的数; A4:小于等于 120 且能被 7 除尽的数。 S = {1,2,?,120} 则小于或等于 120 的素数既是求 A1 ? A2 ? A3 ? A4 ,所以
A1 ? A2 ? A3 ? A4 ? S ? ( A1 ? A2 ? A3 ? A4 ) ? ( A1 ? A2 ? A1 ? A3 ? A1 ? A4 ? A2 ? A3 ? A2 ? A4 ? A3 ? A4 ) ? ( A1 ? A2 ? A3 ? A1 ? A2 ? A4 ? A1 ? A3 ? A4 ? A2 ? A3 ? A4 ) ? A1 ? A2 ? A3 ? A4



|A1| = ?120 ? =60,|A2| = ?120 ? =40,|A3| = ?120 ? =24,|A4| = ?120 ? =17
? 2 ? ? ? ? 3 ? ? ? ? 5 ? ? ? ? 7 ? ? ?
? 120 ? ? 120 ? =12,|A1∩A4 |= ? 120 ? =8 ? ? 20 ,|A1∩A3| = ? ? ?[2,7] ? ? ?2,3?? ?[2,5] ? ? ?

|A1∩A2 | = ?

|A2∩A3 | = ? 120 ? =8,|A2∩A4 | = ? 120 ? =5,|A3∩A4 | = ? 120 ? =3
? [3,5] ? ? ? ?[3,7] ? ? ? ?[5,7] ? ? ?

|A1∩A2∩A3| = ? 120 ? =4,|A1∩A2∩A4| = ? 120 ? =2,
?[2,3,5] ? ? ? ? [2,3,7] ? ? ?

|A1∩A3∩A4| = ? 120 ? =1,|A2∩A3∩A4| = ? 120 ? =1
? [2,5,7] ? ? ? ?[3,5,7] ? ? ?

|A1∩A2∩A3∩A4| = ? 120 所以 A1 ? A2 ? A3 ? A4

? =0 ? [2,3,5,7] ? ? ?

= 120 – ( 60 + 40 + 24 + 17 ) + ( 20 + 12 + 8 + 8 + 5 + 3 ) – ( 4 + 2 + 1 + 1 ) – 0 = 27

45

组合数学讲义

第4章

容斥原理与鸽笼原理

4.2

容斥原理的应用

通过对下列问题的分析, 进一步加深对容斥原理的理解, 同时也扩展了容斥原理的内容和应用。

4.2.1 有限重集合的 r 组合
提出问题: 个不同元素的 r 组合数为 ? ? , n 种元素的无限重集合的组合数为 ? n ? ? 有 ? 那么,有限重集合的 r 组合数是多少? 例 1 求 S = {3·a, 4·b, 5·c}的 10 组合数。 解:令 S∞={∞·a, ∞·b, ∞·c},则 S∞的 10 组合数为 ? ?
? 3 ? 10 ? 1? ?12? ? ? ? ? ? 66 。 ? ?2 ? ?10 ? ? ? ?n? ?r ? ? n ? r ? 1? ?, ? ?r ?

设集合 A:集合 S∞的 10 组合的全体,则|A|=66,现在要求在 10 组合中的 a 的个数≤3,b 的个数≤4,c 的个数≤5 的组合数。 设 A1:10 组合中 a 的个数≥4 的集合; A2:10 组合中 b 的个数≥5 的集合; A3:10 组合中 c 的个数≥6 的集合。 则 A1 中的元素可以看作是由 S∞的 10-4 = 6 组合再拼上 4 个 a 构成。所以
? 3 ? 10 ? 4 ? 1? ? 8 ? ? ? ? ? ? 28 A1 ? ? ?10 ? 4 ? ? 2? ? ? ? ?

类似的有
? 3 ? 10 ? 5 ? 1? ? 7 ? ? 3 ? 10 ? 6 ? 1? ? 6 ? ? ? ? ? ? 21, A3 ? ? ? ? ? ? ? 15 A2 ? ? ?10 ? 5 ? ? 2? ?10 ? 6 ? ? 2? ? ? ? ? ? ? ? ? ? 3 ? 10 ? 4 ? 5 ? 1? ? 3 ? ? 3 ? 10 ? 4 ? 6 ? 1? ? 2 ? ? ? ? ? ? 3 , A1 ? A3 ? ? ? ? ? ? ?1 A1 ? A2 ? ? ?10 ? 4 ? 5 ? ?1 ? ?10 ? 4 ? 6 ? ?0? ? ? ? ? ? ? ? ? ? 3 ? 10 ? 5 ? 6 ? 1? ?1 ? ? ? ? ? ? 0 ,|A1∩A2∩A3|=0 A2 ? A3 ? ? ?10 ? 5 ? 6 ? ? ? 1? ? ? ? ?

则 A1 ? A2 ? A3 ? S ? ( A1 ? A1 ? A3 ) ? ( A1 ? A2 ? A1 ? A2 ? A2 ? A3 ) ? A1 ? A2 ? A3 = 66 - ( 28 + 21 + 15 ) + ( 3 + 1 + 0 ) - 0 =6

4.2.2 有禁止位置的错排问题
定义 集合 S = {1, 2, ?, n}的一个错排是该集合的一个满足条件的 i ≠ ri 的全排列 i1i2?in,即集合{1, 2, ?, n}的没有一个数字在它的自然顺序位置上的全排列。通 常用 Dn 表示集合 S 的错排个数。 例如:
46

组合数学讲义

第4章

容斥原理与鸽笼原理

n=1 时,集合{1}没有错排 D1=0。 n=2 时,集合{1, 2}有 1 个错排 D2=1,为 21。 n=3 时,集合{1, 2, 3}有 2 个错排 D3=2,为 231, 312。 n=4 时,集合{1, 2, 3, 4}有个 9 错排 D4=9,分别是: 2143, 2341, 2413, 3142, 3413, 3431, 4123, 4312, 4321。
1 1 1 1 定理 对于任意正整数 n,有 Dn ? n!(1 ? ? ? ? ? ? (?1) n ) 。 1! 2! 3! n!

证明:设 Ai 表示 ri = i 的全排列(i =1, 2, ?, n) ,由于 ri 已确定,所以|Ai|=(n-1)! 同理 |Ai∩Aj|=(n-2)! ?? |A1∩A2∩?∩An| = 1
Dn ? A1 ? A2 ? ? ? An ? A1 ? A2 ? ? ? An ? S ? A1 ? A2 ? ? ? An ? S ? ? Ai ? ? ? Ai ? A j ? ? ? ? Ai ? A j ? Ak ? (?1) n A1 ? A2 ? ? ? An
i ?1 i ?1 j ?i i ?1 j ?i k ? j n n n



?n? ?n? ?n? ? n!?? ?(n ? 1)!?? ?(n ? 2)!? ? ? (?1) n ? ?0! ?1 ? ?2? ?n? ? ? ? ? ? ? 1 1 1 n 1 ? n!(1 ? ? ? ? ? ? (?1) ) 1! 2! 3! n!

例 2 6 人参加会议,入场时随意的将帽子挂在衣架上,走时再顺手戴一顶走,问没一人 拿对的概率? 解:P =

1 1 1 1 1 1 D6 = 1- + - + - + ≈ 0.368 6! 1! 2! 3! 4! 5! 6!

4.2.3 有禁止模式的错排问题
定义 所谓有禁止模式的错排问题是指某些元素间的某种相对顺序不能出现的 错排问题。 例 3 在 S={4·x, 3·y, 2·z}的全排列中求不出现 xxxx, yyy, zz 排列的个数? 解:4 个连续 x 出现的排列,实际上是将 xxxx 作为一个单元参加排列,因此 设 A1:4 个 x 连续出现的排列,集合中元素个数为(4 + 3 + 2) – 4 + 1 = 6; A2:3 个 y 连续出现的排列,集合中元素个数为(4 + 3 + 2) – 3 + 1 = 7; A3:2 个 z 连续出现的排列,集合中元素个数为(4 + 3 + 2) – 2 + 1 = 8。 则:|A1|=

7! 6! =60 |A2|= =105 3!* 2! 4!* 2! 4! 5! |A1∩A2| = =12 |A1∩A3| = =20 2! 3! 3! |A1∩A2∩A3| = =6 1!
47

8! =280 3!* 4! 6! |A2∩A3| = =30 4!
|A3|=

组合数学讲义

第4章

容斥原理与鸽笼原理

而 S 的全排列数 N =

9! =1260,则 4!* 3!* 2!

A1 ? A2 ? A3 ? N ? ( A1 ? A1 ? A3 ) ? ( A1 ? A2 ? A1 ? A2 ? A2 ? A3 ) ? A1 ? A2 ? A3

=1260 – (60+105+280) + (12+20+30) – 6 =871

4.2.4 不相邻的排列
定义 集合 S = {1, 2, ?, n}的不相邻的排列是该集合上不出现 12, 23, ?, (n–1)n 这些模式的全排列。通常用 Qn 表示集合 S 的不相邻的排列个数。 例如: n = 2 时,Q2=1,21 是唯一满足要求的全排列; n = 3 时,Q3=3,213, 321, 132 是 3 个满足要求的全排列; n = 4 时,Q4=11,4132, 4213, 4321, 3142, 3241, 3214, 2143, 2413, 2431, 1324, 1342 是 11 个 满足要求的全排列。 定理:对于任意正整数 n,有:
? n ? 1? ? n ? 2? ? n ?1 Qn ? n!?? ?1 ?(n ? 1)!?? 2 ?(n ? 2)!? ? ? (?1) ? n ? 1?1! ? ? ? ? ? ? ? ? ? ? ?

证明:设 S 为{1, 2, ?, n}的全排列,则|S| = n!,定义性质集合 P={p1, p2, ?, pn},其中 Pi:出现 i(i+1)模式(1≤i≤n–1) 则 Ai:S 中满足性质 Pi 的全排列的集合 Ai 中每个排列是集合{1, 2, ?, i–1, i(i+1), i+2, ?, n}的一个全排列,则|Ai| =(n–1)!。 同理, i∩Aj 中每个排列是集合{1, 2, ?, i–1, i(i+1), i+2, ?, j(j+1), ?, n}的一个全排列,则 A |Ai∩Aj|=(n–2)!(1≤i ≠ j≤n–1) 。 一般的有: |Ai1∩Ai2∩?∩Aik|=(n–k)!(1≤Ai1 ≠ Ai2 ≠ ? ≠ Aik≤n–1) 则
? n ? 1? ? n ? 2? ? n ?1 Qn ? A1 ? A2 ? ? ? An ? n!?? ?1 ?(n ? 1)!?? 2 ?(n ? 2)!? ? ? (?1) ? n ? 1?1! ? ? ? ? ? ? ? ? ? ? ?

例 4 某班有 8 位学生排成一队,第 2 天再排队时,所有同学都不希望他前面的同学与前 一天相同,问有多少种排法? 解: 问题即是求 S = {1, 2, ?, n}的不出现 12, 23, ?, (n–1)n 这些模式的全排列的个数, 则
? 7 ? ? 6 ? ? 5 ? ? 4 ? ? 3 ? ? 2 ? ?1 ? Q8 ? 8!?? ?7!?? ?6!?? ?5!?? ?4!?? ?5!?? ?2!?? ?1! ?1 ? ? 2 ? ? 3 ? ? 4 ? ? 5 ? ? 6 ? ? 7 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

= 14664

48

组合数学讲义

第4章

容斥原理与鸽笼原理

4.2.5 不相邻的组合
定义 所谓不相邻的组合是指从 A= {1, 2, ?, n}中取 r 个不相邻的元素的组合, 即不存在相邻的两个元素 j 和 j+1 的组合。 例如:n =5,r =2,则不相邻的组合有{{1, 3},{1, 4},{1, 5},{2, 4},{2, 5},{3, 5}}(去掉相邻 的组合{1, 2}, {2, 3}, {3, 4}, {4, 5}) ,其组合数为 6。 定理 从 A= {1, 2, ?, n}中取 r 个不相邻元素的组合,其组合数为 ? ?
? n ? r ? 1? ?。 ? ?r ?

证明:设 B ={b1, b2, ?, br}是一组不相邻的组合,不失一般性,假设: 1≤b1<b2<? <br≤n 令: c1 = b1, c2 = b2-1, c3 = b3-2,?, cr = br-r+1 定义映射: B ={b1, b2, ?, br} ? C ={c1, c2, ?, cr} 则 1≤c1<c2<?<cr = br-r+1≤n-r +1 (因为有不相邻的条件) 则 C 为从{1, 2, ?, n-r +1}中取 r 个不允许重复的组合为 ? ?
? n ? r ? 1? ?。 ? ?r ?

反之,从{1, 2, ?, n-r +1}中取 r 个元素的不允许重复的组合 D = {d1, d2, ?, dr),假设: 1≤d1<d2<?<dr≤n-r +1 令: b1 = d1, b2 = d2+1, b3 = d3+2, ?, br = dr+r-1 定义映射:D = {d1, d2, ?, dr) ? B = {b1, b2, ?, br} 则 1≤b1<b2<?<br≤n 由于 bi+1-bi = (di+1+i) - (di+i-1) = di+1 - di +1>1 则{b1, b2, ?, br}为不相邻的 r 组合。 例 5 n 对夫妻问题。这是组合数学历史上的一个著名问题:有 n 对夫妻围坐在一张圆桌 旁,要求男女相间而每对夫妻不相邻,问有多少种就座方式?

4.3

鸽笼原理

鸽笼原理是一个重要而又初等的组合数学原理, 它能够解决各种有趣的问题, 常常得出一 些令人惊奇的结论。 定理 1 鸽笼原理的简单形式:如果把 n+1 个鸽子放入 n 个鸽笼,则至少有一个 鸽笼有两个或更多的鸽子。
49

组合数学讲义

第4章

容斥原理与鸽笼原理

例 1 在 1 到 2n 的正整数中任取 n+1 个,则这 n+1 个数中至少有一对数,其中一个是另 一个的倍数。 证明:设这 n+1 个数是{a1, a2,?, an, an+1},对此序列中的每一个数去掉含有 2 的因子,直 到剩下一个奇数为止。例如 68 = 2× 17, 2× 去掉 2× 只剩下 17;4 = 2× 1,去掉 2× 只剩下 1。 2 2× 2 那么,将得到一个由奇数组成的序列:{b1, b2, ?, bn, bn+1}。而 1~2n 之间只有 n 个奇数,故 序列{b1, b2, ?, bn, bn+1}中至少有两个数是相同的。 设 bi = bj = a,则 ai = 2pa;aj = 2qa。由于 ai ≠ aj,则 ai/aj = 2p-q,即其中一个是另一个的倍 数(设 ai>aj,则 ai 是 aj 的倍数) 。 ※应用鸽笼原理可以巧妙地解决看似复杂的问题,其关键是如何构造问题中的“鸽子”和“鸽 笼” 。 定理 2 鸽笼原理的加强形式: a1, a2,?, an 都是正整数, 设 如果把 a1+a2+…+an-n+1 个鸽子放入 n 个鸽笼,那么或者第 1 个鸽笼至少包含 a1 个鸽子,或者第 2 个鸽笼 至少包含 a2 个鸽子,…,或者第 n 个鸽笼至少包含 an 个鸽子。 证明:假设第 i 个鸽笼都不能含有 ai 个或更多的鸽子(i = 1, 2, ?, n) ,则所有鸽笼中的鸽子 的总数不超过(a1-1) + (a2-1) + ? + (an-1) = a1 + a2 + ? + an-n,比原鸽子数少 1。因此,结 论成立。 ※显然,如果 ai = 2(i = 1, 2, ?, n)就是鸽笼原理的简单形式。 推论 1: 若把 n(r-1) + 1 个鸽子放入 n 个鸽笼, 那么至少有一个鸽笼中有 r 个鸽子。 证明:在定理 2 中令 ai = r(i = 1, 2, ?, n) 推论 2:设 a1, a2,?, an 都是正整数,且(a1 + a2 + ? + an)/n>r-1,则 a1, a2,?, an 中至少有一个数不小于 r。 证明:反证法。设 ai = r-1,则(a1 + a2 + ? + an)/n =n(r-1)/n = r-1,因此结论成立。 推论 3:若将 m 个鸽子放入 n 个鸽笼中,则至少有一个鸽笼中有不少于 ?m / n? 个 鸽子(或 ?(m ? 1) / n? +1 个) 。 证明:如若不然,鸽笼中的鸽子数都小于 ?m / n? -1,则 n× ?m / n? -1)≤m-n<m,矛盾;或 ( 鸽笼中的鸽子数都小于 ?(m ? 1) / n? ,则 n×?(m ? 1) / n? <m,矛盾,因此结论成立。 注意到: ?(m ? 1) / n? ? 1 ? ?m / n? 。例如: ?(8 ? 1) / 2? ? 1 ? 4 ? ?8 / 2? , ?(7 ? 1) / 2? ? 1 ? 4 ? ?7 / 2? 。 推论 3 的变形:设 k 和 n 是任意正整数,若有 kn+1 个鸽子放入 n 个鸽笼中,则至少存在 一个鸽笼中有至少 k+1 个鸽子。 显然:若每个鸽笼中的鸽子数都不超过 k 个,则总的鸽子数为 nk 个。 再看推论 3:令 kn+1=m,则 ?(kn ? 1) / n? ? k ? 1 , ?(m ? 1) / n? ? 1 ? ?kn / n? ? 1 ? k ? 1 。
50

组合数学讲义

第4章

容斥原理与鸽笼原理

例 2 一个抽屉里有 20 件衬衫,其中 4 件是兰色的,7 件是灰色的,9 件是红色的,问从 中随意取多少件能保证有 4 件是同色的?抽取多少件能保证 5,6,7,8,9 件是同色的? 解:⑴ 抽取衬衫的模型如图 1 所示,将颜色作为鸽笼,衬衫作为鸽子。
兰色 灰色 红色 鸽笼

待抽取的衬衫 图1 抽取衬衫的模型

鸽子

现有 3 种颜色,即 n = 3,k + 1 = 4?k = 3,所以 kn + 1 = 3 × 3 = 10 (件)。 或应用推论 3: ?m / 3? ? 4 ,则 m = 10。 ⑵k + 1 = 5?k = 4,nk + 1 = 3 × 4 + 1 = 13。其实不然,问题的模型与鸽笼原理不尽相同。 考虑最坏情况:第 1 次取 10 件正好有 4 件是兰色的,则问题变成由灰色和红色构成同颜色的 情况,此时 n = 2, k + 1 = 5?k = 4,因此 4 + 2× + 1 = 13。 4 ⑶k + 1 = 6?k = 5,则 nk + 1 = 3× + 1 = 16,其实不然。正确的结果是: 5 4 + 2× + 1 = 15(件) 5 ⑷k + 1 = 7?k = 6,则 nk + 1 = 3× 6+1 = 19,但是不能直接应用鸽笼原理,正确的结果是: 4 + 2× + 1 = 17(件) 6 ⑸k + 1 = 8 ?k = 7,则 nk + 1 = 3× + 1 = 22,但是不能直接应用鸽笼原理,考虑到兰的和 7 灰的已经分别取尽,这时只剩下红的。所以,正确的结果是: 4 + 7 + 1× + 1 = 19(件) 7 ⑹k + 1 = 9 ?k = 8,4 + 7 + 1× + 1 = 20(件) 8 例 3 两只圆盘(大小不一样)都被均分成 200 个扇形,大盘的 200 个扇形中,任意取 100 个涂黑,另外 100 个涂白,小盘的每个扇形则任意涂黑或白,现将两个盘中心重合,转动 小盘,使小盘上每个扇形都含在大盘的扇形之内。证明:至少 100 个小盘上的扇形与大盘上的 扇形同色。 证明:小盘的扇形与大盘的扇形有 200 个重合位置。 例 4 设 A 是 m(m≥1)个正整数的集合,证明存在非空子集 B ? A,使得 B 的元素之和 能被 m 除尽。 证明:设 A = {a1, a2,?, am}, A1={a1}, A2 ={a1, a2},?, Am={a1, a2,?, am}。 令 a1 mod m = r1 (a1 + a2 ) mod m = r2 ?? (a1 + a2 + ? + am ) mod m = rm 其中 0≤ri<m(i =1, 2, ?, m) 若存在 rh = 0,则(a1 + a2 + ? + ah ) mod m = 0,即 B = {a1, a2,?, ah}; 否则,r1, r2, ?, rm 均为小于 m 的正整数,必存在 ri = rj,不妨设 i<j,则 (a1 + a2 + ? + ai ) mod m = (a1 + a2 + ? + aj) mod m
51

组合数学讲义

第4章

容斥原理与鸽笼原理

即: a1 + a2 + ? + ai = p * m + ri (式 1) a1 + a2 + ? + aj = q * m + rj (式 2) 式 1-式 2 得: ai+1 + ai+2 + ?+ aj = (q - p) * m 即 B = {ai+1, ai+2, ?, aj}的元素之和能被 m 除尽。

4.4

Ramsey 问题与 Ramsey 数

Ramsey 定理是以英国逻辑学家 Ramsey 的名字命名的。

4.4.1 Ramsey 问题
定义 Ramsey 问题: 任何 6 个人的聚会, 至少有 3 个人互相认识或 3 个人互相不 认识。 证明:将 Ramsey 问题抽象为图模型。设 6 个人为{A, B, C, D, E, F},以 6 个顶点表示, 对这 6 个顶点做完全图,互相认识的人对应顶点之间的边着红色(加粗) ,互相不认识的人对 应顶点之间的边着兰色, 则必然至少存在一个红色边的三角形或兰色边的三角形, 如图 2 所示。
A A B C C

D

E D F 图2 将 Ramsey 问题抽象为图模型 E

由于是完全图,则 A 点与其他 5 个顶点相连有 5 条边,每条边或着红色或着兰色,根据 鸽笼原理(m = 5 个鸽子,n = 2 个鸽笼) ,至少有 ?5 / 2? =3 条边着同色。不妨假定着红色,另 外 3 个顶点为 C、D、E,则 C、D、E 顶点间的连线或同色或不同色,假设三角形 CDE 的边 同色, 满足定理, 若三角形 CDE 的边不同色, 则至少有一条边为红色设为 CD, 则三角形 ACD 的边同为红色。 推论 1:对 6 个顶点的完全图 K6 任意进行红、兰两边着色,结果至少有两个同色 的三角形。

52

组合数学讲义

第4章

容斥原理与鸽笼原理

推论 2:对 10 个顶点的完全图 K10 任意进行红、兰两边着色,结果存在一个红色 K4 或一个兰色 K3,或存在一个红色 K3 或一个兰色 K4。 解释:任何 10 个人的聚会,若不是 3 个人互相不认识,则必有 4 个人互相认识;若不是 3 个 人互相认识,则必有 4 个人互相不认识。 证明:将图 2 推广到 Kn 为 n 个顶点的完全图。 推论 3:对 9 个顶点的完全图 K9 任意进行红、兰两边着色,结果存在一个红色 K4 或一个兰色 K3,或存在一个红色 K3 或一个兰色 K4。 由推论 2 和推论 3 可以看出,对于 9 个顶点和 10 个顶点的完全图进行红、兰两边着色, 得到的结果是一样的,而 9 是得到这个结果的最少顶点数。

4.4.2 Ramsey 数
定义 对任意给定的正整数 a 和 b,如果存在最小的正整数 r(a, b),使得当 N≥ r(a,b)时,对 Kn 任意进行红、兰两边着色,结果存在一个红色 Ka 或兰色 Kb(或存 在一个红色 Kb 或兰色 Ka) ,则 r(a, b)称为 Ramsey 数。 Ramsey 于 1930 年证明了对于任意给定的正整数 a 和 b,Ramsey 数 r(a, b)的存在性,但 Ramsey 数的确定却是一个非常难的问题,以至于 r(5, 5)至今尚未求出。已经求出的 Ramsey 数如下表所示。
a b 2 3 4 5 6 7 8 9

2 2 3 4 5 6 7 8 9

3 3 6 9 14 18 23 28 36

4 4 9 18 25

5 5 14 25

6 6 18

7 7 23

8 8 28

9 9 36

定理 1 定理 2

对任意正整数 a 和 b,有(1)r(a, b) = r(b, a); (2)r(a, 2) = a。 对任意正整数 a≥3,b≥3,有 r(a, b) ≤r(a-1, b) + r(a, b-1)

证明:令 N = r(a-1, b) + r(a, b-1),设 A∈N,将余下的 r(a-1, b) + r(a, b-1)-1 个人即 N-1 个人 分成如下两个集合: Friend:与 A 互相认识; Strange:与 A 互相不认识。 则|Friend|≥r(a-1, b)或|Strange|≥r(a, b-1)必有一个成立,如若不然,假设:
53

组合数学讲义

第4章

容斥原理与鸽笼原理

|Friend|≤r(a-1, b)-1 且|Strange|≤r(a, b-1)-1 则 |Friend| + |Strange|≤r(a-1, b)+ r(a, b-1)-2 与假设矛盾。 若|Friend|≥r(a-1, b), Friend 集合中有 a-1 个人互相认识, 则 加上 A 个共 a 个人相互认 识, b 个人互相不认识; 或 若|Strange|≥r(a, b-1),则 Strange 集合中有 a 个人互相认识, b-1 有 个人互相不认识,加上 A 共 b 个人互相不认识。 但 r(a, b)是使得有 a 个人互相认识或 b 个人互不相识的最少人数,故 r(a, b) ≤r(a-1, b) + r(a, b-1) 定理 3 对任意正整数 a≥2,b≥2,有
? a ? b ? 2? (a ? b ? 2)! ?? r ( a, b) ? ? ? a ?1 ? (a ? 1)!(b ? 1)! ? r (a ? 1, b) ? r (a, b ? 1) ? ?

证明:对 a + b 做归纳。证明略。 Ramsey 数的推广:将红、兰两种颜色推广到 c1、c2、?、ck 共 k 种颜色;将存在 a 条边 的同色完全图或 b 条边的同色完全图推广到存在 a1、a2、?或 ak 条边的同色完全图,则得到 推广的 Ramsey 数:r(a1, a2, ?, ak)。 推广的 Ramsey 数:对 r 个顶点的完全图,用 k 种颜色 c1、c2、?、ck 任意对边进 行着色,必然存在 a1 条边的颜色 c1 着色的完全图,或 a2 条边的颜色 c2 着色的完 全图, 或 ak 条边的 ck 颜色着色的完全图, ?, 这样的最小正整数称为推广的 Ramsey 数,用 r(a1, a2, ?, ak)。 例 1 用红、兰两种颜色对 r(3, 6)个顶点的完全图着色,结果或出现 3 个顶点的红色三角 形或 6 个顶点的兰色三角形。用黄、绿两种颜色对兰色边的 6 个顶点的完全图着色,结果或出 现 3 个顶点的黄色三角形或 3 个顶点的绿色三角形,即 r(3, 6)≥r(3, 3, 3)。 一般地:r(a1, a2, ?, ak)≤r(a1, r(a2, ?, ak))

54

组合数学讲义

第5章

递推关系与母函数

第 5 章 递推关系与母函数
5.1 递推关系

组合数学很重要的内容是组合计数,有许多组合计数问题可以用递推关系来求解,计算 机算法尤其如此。 例 1 汉诺塔问题 汉诺塔问题来自一个古老的传说:在世界刚被创建的时候有一座钻石宝塔(塔 A) ,其上 有 64 个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石 宝塔(塔 B 和塔 C) 。从世界创始之日起,婆罗门的牧师们就一直在试图把塔 A 上的碟子移动 到塔 C 上去,其间借助于塔 B 的帮助。每次只能移动一个碟子,任何时候都不能把一个碟子 放在比它小的碟子上面。当牧师们完成任务时,世界末日也就到了。 对于汉诺塔问题的求解,可以通过以下三个步骤实现: ⑴ 将塔 A 上的 n-1 个碟子借助塔 C 先移到塔 B 上。 ⑵ 把塔 A 上剩下的一个碟子移到塔 C 上。 ⑶ 将 n-1 个碟子从塔 B 借助于塔 A 移到塔 C 上。 按照上面的操作步骤,n 个碟子的汉诺塔问题需要移动的碟子数 h(n)为:第⑴步需要移动 的碟子数为 h(n-1); 第⑵步需要移动的碟子数为 1; 第⑶步需要移动的碟子数为 h(n-1)。 n=1 当 时,只需要移动一次碟子。由此,得到如下递推关系式: h(n)=2h(n-1)+1 式1 h(1)=1 将式 1 等号右边的式子反复迭代,有:

h(n) ? 2h(n ? 1) ? 1 ? 2(2h(n ? 2) ? 1) ? 1 ? 2 2 h(n ? 2) ? 2 ? 1 ? ?? ? 2 n?1 h(1) ? ? ? 2 2 ? 21 ? 1 ? 2n ? 1

55

组合数学讲义

第5章

递推关系与母函数

定义 1 给定一个数的序列 f(0), f(1),?, f(n), ? (有限或无限) 若存在正整数 n0, , 使得当 n≥n0 时, 可以用等号 (或大于号, 小于号) f(n)与前面的某些项 f(i) (0≤i 将 <n)联系起来,这样的式子称作递推关系式(即描述序列的规律) 。 ※ 建立递推关系式的步骤如下: (1)找第 n 项与前面最近几项的关系; (2)获得最前面几项的具体值,即初值。 例 2 n 位四进制数中,有偶数个 0 的序列共有多少个? 解:设 f(n)表示 n 位四进制数中有偶数个 0 的序列,它有两部分组成: (1)在 n-1 位四进制数中有偶数个 0 的序列再添一位非零(即 1,2,3)的数,可产生 3f(n-1)个满足条件的序列。 (2) 在 n-1 位四进制数中有奇数个 0 的序列再添一位 0 可产生 4n-1- f(n-1)个满足条件 的序列。 (注意到|奇数个 0 的序列| = |全集| - |偶数个 0 的序列|) 由加法原理,得: f (n) = 3f(n-1) + 4n-1- f(n-1)= 4n-1 + 2f(n-1) 显然,f(1) = 3, 即:

? f (1) ? 3 ? n ?1 ? f (n) ? 4 ? 2 f (n ? 1)
例 3 1×n 棋盘用红、白、蓝三种颜色着色,不允许相邻的格子都着红色,求着色方案 数?
1 2 ??

1×n 棋盘

解:设 f (n)表示满足条件的着色方案数,可分为如下四类: (1)1 格着白色,余下 1×(n-1)的棋盘,满足条件的方案数:f (n-1); (2)1 格着蓝色,余下 1×(n-1)的棋盘,满足条件的方案数:f (n-1); (3)1 格着红色,2 格着白色,余下 1×(n-2)的棋盘,满足条件的方案数:f (n-2); (4) 1 格着红色,2 格着蓝色,余下 1×(n-2)的棋盘,满足条件的方案数:f (n-2)。 由加法原理,有: f(n) = 2f(n-1) + 2f(n-2) f(1) = 3 f(2) = 8(白白,蓝蓝,白红,白蓝,蓝白,蓝红,红白,红蓝) ※ 建立递推关系式的关键是找出第 n 项与前面最近几项的关系。

56

组合数学讲义

第5章

递推关系与母函数

5.2

母函数

母函数(也称生成函数)是组合数学用得比较多的工具,也是求解递推关系的工具。 递推关系的求解一般有三种方法:方法 1——扩展递推,反复迭代;方法 2——特征方程, 求特征值;方法 3——母函数。

5.2.1 母函数的定义
例1
?n? ?n? ? n ? n?1 ? n ? n (1 ? x) n ? 1 ? ? ? x ? ? ? x 2 ? ? ? ? ?1 ? ? 2 ? ? n ? 1? x ? ? n ? x ? ? ? ? ? ? ? ? ? ? ?
(1 ? x) m?n ? (1 ? x) m (1 ? x) n

考察等式两边 xk 的系数: 左边: ? ?
?m ? n? ? ? ?k ?
? m ?? n ? ? m ?? n ? ? m ?? n ? ?n?

右边: ? ?? ? ? ? ?? ? 0 ?? k ? ?1 ?? k ? 1? ? ? ? ? k ?? 0 ? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? 可见 f(x) = (1+x)n 在研究序列 ? ?, ? ?, ? ?, ??, ? ? 时所起的作用。 ? 0 ? ?1 ? ? 2 ? ?n? ? ? ? ? ? ? ? ? 定义 1 对于实数域 R 上的序列{a0, a1, a2,??}(有限或无限)对应一个收敛的 形式幂级数 A(x) = a0 + a1x + a2x2 + ??, A(x)为序列{a0, a1, a2,??}的母函数。 称 一般情况下,A(x)中的 x 只是一个抽象的符号,并不需要对它赋予具体值,因而可以不考 虑 A(x)的收敛性。 例如,(1+x)n 为序列 ? ?, ? ?, ? ?, ??, ? ? 的母函数 ? 0 ? ?1 ? ? 2 ? ?n? ? ? ? ? ? ? ? ? 需要强调的是,序列和对应的母函数是一一对应的。即若已知序列{a0, a1, a2,??},则对 应的母函数 A(x)便是确定的,反之,若给定母函数 A(x),则对应的序列便确定了。 因此,若两个母函数之间存在某种关系,那么他们对应的序列之间也必然存在一定的关系。反 之亦然。
?n? ?n? ?n? ?n? ?n? ?n? ?n?

5.2.3 利用母函数求解递归关系式
母函数求解递归关系式的基本思想是:对一个有限(或无限)序列{a0, a1, a2,??}构成幂 级数 A(x) = a0 + a1x + a2x2 + ??,使{ai}与{xi}构成一一对应关系,由此{ai}与{xi}构成了一个 整体,然后通过研究幂级数 A(x)导出序列{a0, a1, a2,??}的构造和性质。 例 2 求解汉诺塔问题的递推关系式:H(n) = 2H(n-1)+1
57

组合数学讲义

第5章

递推关系与母函数

方便起见,记 Hn=H(n),令序列{H0 , H1, H2 , ??, Hn}的母函数为: G(x)=H0 + H1x +H2x2 +?? 补充定义 H0 = 0,并作如下的形式化演算: x: H1 = 2H0 + 1 2 x : H2 = 2H1 + 1 x3: H3 = 2H2 + 1 + ?? G(x) = 2x(H0 + H1x + H2x2 + ??) + (x + x2 + x3 + ??) 又

1 = 1 + x + x2 + ?? 1? x
G(x) = 2xG(x) +

——构造序列和母函数的桥

所以

x 1? x

——关于 G(x)的方程

即: (1-2x)G(x) = 所以 G(x) =

x 1? x

x (1 ? x)(1 ? 2 x)

序列{H0 , H1, H2 , ??, Hn}的母函数已求得,下面设法从 G(x)求序列。 令

B x A = + 1? x 1? 2x (1 ? x)(1 ? 2 x)

(A,B 为待定系数)

A(1 ? x) ? B (1 ? 2 x) ( A ? B ) ? ( A ? 2 B ) x x ? ? (1 ? x)(1 ? 2 x) (1 ? x)(1 ? 2 x) (1 ? x)(1 ? 2 x)

即 所以

?A ? B ? 0 ?A ?1 ,则 ? ? ? A ? 2B ? ?1 ? B ? ?1

G ( x) ?

1 1 ? 1 ? 2x 1 ? x

桥:

1 ? 1 ? ax ? a 2 x 2 ? ?? 1 ? ax

因此:
G ( x) ? 1 1 ? ? (1 ? 2 x ? 2 2 x 2 ? ??) ? (1 ? x ? x 2 ? ??) 1 ? 2x 1 ? x ? x ? (2 2 ? 1) x 2 ? (23 ? 1) x 3 ? ??

因此,Hn = 2n-1。 ※ 利用母函数求解各类递推关系有广泛的适用性,基本步骤为:

58

组合数学讲义

第5章
?

递推关系与母函数

(1)令 A( x) ? ? f (n) x n ,其中 f(n)为递推关系;
n ?0

(2)将关于 f(n)的递推关系式转化为关于 A(x)的方程; (3)解出 A(x),将 A(x)展开成 x 的幂级数,则 x 的系数即是 f(n)。 例 3 求解如下递推关系:
? f (n) ? f (n ? 1) ? n 2 ? ? ? f (0) ? 0 ?
n

解:令 A( x) ? f (0) ? f (1) x ? f (2) x 2 ? ?? 则 x : f(1) = f (0) + 12 x2 : f(2) = f (1) + 22 x3 : f(3) = f (2) + 32 ?? A(x) = x (f (0) + f (1)x + f (2)x2+??) + (12x + 22x2 + 32x3 +??)
A( x) ? xA( x) ? ? n 2 x n
n ?1 ?

+ 即:

得: A( x) ? 则: A( x) ?

1 2 n ?n x 1 ? x n?1
x(1 ? x) (1 ? x) 4

?

桥:

x(1 ? x) (1 ? x)
3

? 12 x ? 2 2 x 2 ? 3 2 x 3 ? ??

则: A( x) ? x(1 ? x) ? ? ? 则 xn 的系数为 f (n) ? ? ?

? i ? 3? i ?x ? i ?1? i ?
?

桥:

1 (1 ? x)
n?1

? n ? 1? ? n ? 2 ? 2 ? x ? ?? ? 0?? ?1 ? x ? ? 2 ? ? ? ? ? ? ?

? n ? 1 ? 3 ? ? n ? 2 ? 3 ? n(n ? 1)(2n ? 1) ??? ?? 。 ? ? ? 6 ? n ?1 ? ? n ? 2 ?

5.2.2 母函数的性质
利用母函数求解递推关系必须要使母函数到对应的序列 (或序列到对应的母函数) 的桥保 持通畅,母函数的性质就在于搭建这样的桥。 设序列{a0, a1, a2,??}的母函数为 A( x) ? ? a k x k ,序列{b0, b1, b2,??}的母函数为
k ?0 ?

B( x) ? ? bk x k ,则母函数有下列性质成立。
k ?0

?

性质 1 若 bk ? ?

?0 ?ak ?l

(k ? l ) (k ? l )

,则 B(x)=xl×A(x)
59

组合数学讲义

第5章

递推关系与母函数

例如,已知 A( x) ?
B( x) ?

x x x ? ? ?? ? ? ?? ? e x ? 1 ,则 1! 2! n!

2

n

x m x m?1 x m?n?1 ? ? ?? ? ? ?? ? x m?1 (e x ? 1) 1! 2! n! 因 a1=bm, a2=bm+1,??则 bm=am-(m-1),即 l = m-1。

性质 2 若 bk ? a k ?l ,则 B( x) ? 性质 3 若 bk ? ? ai ,则 B( x) ?
i ?0 k

1 xl

l ?1 ? ? A( x) ? ? ak x k ? 。 ? k ?0 ? ?

A( x) 。 1? x

例如,已知 A( x) ? 1 ? x ? x 2 ? x 3 ? ? ? x n ? ? ?

1 ,则 1? x ? 1 B ( x) ? 1 ? 2 x ? 3 x 2 ? ? ? (n ? 1) x n ? ? ? ? (k ? 1) x k ? k ?0 (1 ? x) 2

下面是几个常用序列的母函数: ① G{1} = {1, 1, 1, ??} =1 + x + x2 + ?? =

1 1? x
1 1 ? ax

② G{ak} = {a0, a1, a2, ??} = a0 + a1x + a2x2 + ?? = ③ G{k} = {0, 1, 2, ??} = 0 + x + 2x2 + 3x3 + ?? =

x (1 ? x)2 x(1 ? x) ④ G{k2}={02, 12, 22, ??} = 0 + 12x +22x2 + 32x3 + ?? = (1 ? x)3
⑤ G{? ?
?n ? k ? ? n ? 1? ? n ? 2 ? 2 1 ?} ? 0 ? ? ? x ? ?? ? ? ?1 ? x ? ? 2 ? ? ? k (1 ? x) n ?1 ? ? ? ? ? ?

5.3

Fibonacci 序列

Fibonacci 序列和 Catalan 序列都是递推关系的典型序列, 它们的性质对解决许多组合计数 问题十分有用。

5.3.1 Fibonacci 序列
Fibonacci 序列是一个经典问题:把一对兔子(雌、雄各一只)放到围栏中,每个月这对 兔子都生出一对新兔子,其中雌、雄各一只,从第二个月开始。每对新兔子每个月也生出一对 新兔子,也是雌、雄各一只,一年后围栏中有多少对兔子? 分析:令 f(n)表示第 n 个月开始时围栏中的兔子对数(强调是几―对‖而不是几―只‖) 显然有 f (1) = 1,f (2) =2(补充规定 f(0) = 1)
60

组合数学讲义

第5章

递推关系与母函数

在第 n 个月的开始,那些第 n-1 个月初就已经在围栏中的兔子仍然存在,而且每对在第 n-2 个月出生的兔子会生出一对新兔子,所以有: f (n) = f (n-1) + f (n-2) f (0) = 1 f (1) = 1 (n≥2) (式 1)

满足递推关系式 1 的数列称为 Fibonacci 数列,它的项称为 Fibonacci 数。 简单起见,记 fn = f (n),补充规定 f1 = 1,令 A(x)= f 0 + f 1x + f 2x2 + ? 则 x2:f 2 = f 0 + f 1 x3:f 3 = f 1 + f 2 x4:f 4 = f 2 + f 3 + ?? 2 得:f2 x + f3 x3 + f4 x4 +? = x2(f0 + f1x + f2 x2 +?) + x(f1x + f2 x2 + f3 x3 +?) 即:A(x)- f0- f1x = x2 A(x) +x A(x) 故:(1- x- x2) A(x) = x 则 令

x 1? 5 1? 5 由于 ( 1 ? x ? x 2 )=(1x)(1) 2 1? x ? x 2 2 x A B A(x) = + = 1? 5 1? 5 1? 5 1? 5 (1 ? x)(1 ? x) 1? x 1? x 2 2 2 2
A(x) =

求得 A = 则 A(x)=

1 5
1 ( 5

B=-

1 5

1 1 ) ? 1? 5 1? 5 1? x 1? x 2 2
(桥:
1 ? 1 ? ?x ? ? 2 x 2 ? ? ) 1 ? ?x

1? 5 1? 5 , ?? 2 2 1 [(? ? ? ) x ? (? 2 ? ? 2 ) x 2 ? ?] 则 A(x)= 5


??

则 即

fn ?

?n ??n
5

fn ?

1 1? 5 n 1 1? 5 n ( ) ? ( ) 2 2 5 5

例 1 一个小孩上楼梯,每次可以上一个或两个台阶,上 n 阶楼梯有多少种方案? 解:设有 h(n)种方法,这些方法可以分成两类: (1)最后一次上 1 个台阶,其方法数为 h(n ? 1) ; (2)最后一次上 2 个台阶,其方法数为 h(n ? 2) 。 所以, h(n) ? h(n ? 1) ? h(n ? 2) 。 显然, h(1) ? 1, h(2) ? 2 ,再次得到了 Fibonacci 数列
61

组合数学讲义

第5章

递推关系与母函数

5.3.2 Fibonacci 数的性质
作为一个特殊数列,Fibonacci 数具有一些特别重要的性质。 性质 1:Fibonacci 数 f (n) 可以表示为二项式系数之和,即:

? n ? ? n ? 1? ?n ? k ? ?n? f (n) ? ? ? ? ? ? 0 ? ? 1 ? ? ? ? ? k ? ,其中 k ? ? 2 ? 。 ? ? ? ? ? ? ? ? ? ? ?
证明采用归纳法,证明略。 性质 2: f (0) ? f (1) ? ? ? f (n) ? f (n ? 2) ? 1 证明:由递推关系得 (式 2)

f (0) ? f (2) ? f (1) f (1) ? f (3) ? f (2) ? f (n) ? f (n ? 2) ? f (n ? 1)
将上式相加,得:

f (0) ? f (1) ? ? ? f (n) ? f (n ? 2) ? f (1) ? f (n ? 2) ? 1
性质 3: f (0) ? f (2) ? ? ? f (2n) ? f (2n ? 1) 证明:由递推关系得:
f (0) ? f (1) f ( 2) ? f (3) ? f (1) f ( 4) ? f (5) ? f (3) ? f ( 2n) ? f ( 2n ? 1) ? f ( 2n ? 1)

(式 3)

将上式相加得:
f (0) ? f (2) ? ? ? f (2n) ? f (2n ? 1)

性质 4: f (1) ? f (3) ? ? ? f (2n ? 1) ? f (2n) ? 1 证明:式 2-式 3 得:
f (1) ? f (3) ? ? ? f (2n ? 1) ? f (2n ? 2) ? 1 ? f (2n ? 1)

即: f (1) ? f (3) ? ? ? f (2n ? 1) ? f (2n ? 1) ? f (2n ? 2) ? 1 ? f (2n ? 1) ? f (2n) ? 1 即: f (1) ? f (3) ? ? ? f (2n ? 1) ? f (2n) ? 1 性质 5: f 2 (0) ? f 2 (1) ? ? ? f 2 (n) ? f (n) f (n ? 1) 证明:由递推关系得:

f 2 (0) ? f (1) f (0) f 2 (1) ? f (1)[ f (2) ? f (0)] ? f (2) f (1) ? f (1) f (0)
??
62

组合数学讲义
2

第5章

递推关系与母函数

f (n) ? f (n)[ f (n ? 1) ? f (n ? 1)] ? f (n ? 1) f (n) ? f (n) f (n ? 1)
将上式相加,得:
f 2 (0) ? f 2 (1) ? ? ? f 2 (n) ? f (n) f (n ? 1)

性质 6: f (n ? m) ? f (m ? 1) f (n ? 1) ? f (m ? 2) f (n) (m ? 2) 证明:对 m 进行归纳。 当 m = 2 时,有:

f (n ? 2) ? f (n ? 1) ? f (n) ? f (1) f (n ? 1) ? f (0) f (n)
假设 m ? k 时等式成立,则 f (n ? k ? 1) ? f (n ? k ) ? f (n ? k ?1) ? f (k ? 1) f (n ? 1) ? f (k ? 2) f (n) ? f (k ? 2) f (n ? 1) ? f (k ? 3) f (n) ? [ f (k ? 1) ? f (k ? 2)] f (n ? 1) ? [ f (k ? 2) ? f (k ? 3)] f (n)

? f (k ) f (n ? 1) ? f (k ? 1) f (n)
由归纳法,命题成立。

5.4

Catalan 序列

Catalan 序列首先是 Euler 在计算凸多边形的三角形剖分的个数问题时得到的, 许多计数问 题都导致这样的递推关系。 定义 1 凸多边形的三角形剖分问题:在一个凸 n 边形中,通过插入内部不相交 对角线将其剖分成一些三角形区域,有多少种不同的分法? 分析:由几何学知识,凸 n 边形的一个剖分需引 n-3 条互不相交的对角线,将内部区域 分割成 n-2 个三角形。简单起见,令 h(n)表示凸 n+1 边形的三角形剖分的方案数。 定理 1: h(n) ? ? h(k )h(n ? k ) ,显然 n ? 2 。
k ?1 n ?1

例如:几个特殊情况,如图 3 所示。 n = 2 时(为三角形) ,h(2)=1; n = 3 时(为四边形) ,h(3)=2; n = 4 时(为五边形) ,h(4)=5。

图3

四边形的 2 种剖分

图4

五边形的 5 种剖分 63

组合数学讲义

第5章

递推关系与母函数

证明:当 n≥4 时,凸 n+1 边形的顶点用 A1, A2,?, An+1 表示, 取定多边形一条边 A1An+1, 任取多边形的一个顶点 Ak+1 (2≤k + 1≤n ? 1≤k≤n-1) ,将 Ak+1 分别与 A1 和 An+1 连线得到三角形 T,则三角形 T 将凸 n+1 边形分成 T、R1 和 R2 三个部分,其中 R1 为 k+1 边形,R2 为 n-k+1 边形,如图 5 所示。因此,R1 有 h(k)种剖分方法,R2 有 h(n-k)种剖分方法。所以:

Ak+1 Ak R1 T A1
图5

R2

h ( n) ? ? h ( k ) h( n ? k )
k ?1

n ?1

An+1

n+1 边形剖分示意图

补充定义 h(1) = 1,得到 Catalan 数列:

h(1) ? 1, h(2) ? 1, h(3) ? 2, h(4) ? 5, h(5) ? 14, h(6) ? 42,?
即 {1,1,2,5,14,42,?},Catalan 数列的项称为 Catalan 数。 例 1 乘法结合方式问题:设有 n 个元素 a1 , a2 , ?, an ,在其前后次序不变的情况下,每 次只对两个元素进行乘法,以括号决定乘的先后顺序,有多少种不同的相乘方式? 解:n=2 时,h(2)=1,有 1 种相乘方式,为 a1 ? a2 ; n=3 时,h(3)=2,有 2 种相乘方式,为 (a1 ? a2 ) ? a3 , a1 ? (a2 ? a3 ) ; n=4 时,h(4)=5,有 5 种相乘方式,为:

((a1 ? a2 ) ? a3 ) ? a4 , (a1 ? a2 ) ? (a3 ? a4 ), (a1 ? (a2 ? a3 )) ? a4 , a1 ? ((a2 ? a3 ) ? a4 ), a1 ? (a2 ? (a3 ? a4 ))
n 个元素相乘,无论怎样结合(即画括号) 总有一个时刻到达最后一次相乘,即 , 设竖线左边有 k 个元素竖线右边有 n-k 个元素, 则竖线左边有 h(k ) 种 (a1 ? ak ) | (ak ?1 ? an ) , 结合方式,竖线右边有 h(n ? k ) 种结合方式。由乘法原理,共有 h(k )h(n ? k ) 种结合方式。 现移动竖线,竖线可从 a1 | (a2 ,?, an ) 到 (a1 , ?, an?1 ) | an 范围内移动,即从 1 到 n-1,由 加法原理, h(n) ?

? h(k )h(n ? k ) 。补充定义 h(1) ? 1 。
k ?1

n?1

提出问题: h(n) ?

? h(k )h(n ? k ) 递推关系不是线性的,如何求解?
k ?1

n?1

定理:Catalan 数的计算公式: h(n) ?

1 ? 2n ? 2 ? ? ? n ? n ?1 ? ? ?

证明:采用母函数证明,方便起见,记 h(n) = hn。 补充定义 h1 ? 1 ,令 A( x) ? h1 ? h2 x ? h3 x 2 ? ?
64

组合数学讲义

第5章

递推关系与母函数

x : h2 ? h1h1 x 2 : h3 ? h1h2 ? h2 h1 x 3 : h4 ? h1h3 ? h2 h2 ? h3 h1
+ ??

A( x) ? h1 ? h1 x(h1 ? h2 x ? h3 x 2 ? ?) ? h2 x 2 (h1 ? h2 x ? h3 x 2 ? ?) ? h3 x 3 (h1 ? h2 x ? h3 x 2 ? ?) ??
即 A( x) ? 1 ? (h1 x ? h2 x 2 ? h3 x3 ? ?) A( x) 得: A( x) ? 1 ? xA2 ( x) ? xA2 ( x) ? A( x) ? 1 ? 0 解得: A( x) ?

1 ? 1 ? 4x 2x
1 ? 1 ? 4x 有意义 2x
(式 1)

而 Catalan 数只在 A( x) ?
1 ? 4x ? 1 ? 2x ? 1?1
2

1? 3 1? 3 ? 5 ? ?? (2k ? 3) k k 4 2 x 2 ? 3 4 3 x 3 ?? ? 4 x ?? 2 ? 2! 2 ? 3! 2 k ? k!

所以 x

n ?1

项的系数为

1 1 1 1 1 ( ? 1)( ? 2) ? ( ? n)(?4) n?1 (n ? 1)! 2 2 2 2

? 2n ? = ?2 ? ? n ?1? n ? ? ?
代入式 1 得 xn 的系数为:

h(n ? 1) ?


1 ? 2n ? ? ? n ?1? n ? ? ?

h( n) ?
n

1 ? 2n ? 2 ? ? ? n ? n ?1 ? ? ?

或直接得到 x 项的系数为:

? 2 ? 2n ? 2 ? ? ? n ? n ?1 ? ? ?

65

组合数学讲义

第5章

递推关系与母函数

得 h(n) ?

1 ? 2n ? 2 ? ? ? n ? n ?1 ? ? ?

另一种证明:采用排列组合原理,再采用迭代法。 由于

h(n) = ? h(k )h(n ? k )
k ?1

n ?1



h(n) ? 2h(1)h(n ? 1) ? ? h(k )h(n ? k )
k ?2

n ?2

(式 1)

下面证明

? h ( k ) h( n ? k ) =
k ?2

n?2

2(n ? 3) h(n ? 1) 。 n

任取凸 n 边形的一条对角线 A1Ak+1,把凸 n 边形分成 R1 和 R2 两部分,分别是凸 k+1 多边 形和凸 n-k+1 边形, 于是以 A1Ak+1 为分割线的剖分方案数为 h(k)h(n-k) 2≤k≤n-2) ( 如图 6 所示。 由于是对角线,因此,从 A1 引出诸对角线的剖分方案数为 ? h(k )h(n ? k ) ,由于 A1 可以换
k ?2 n?2



A1,A2, ? ,

An , 从 而 总 的 剖 分 数 为 Ak+1 Ak R1 Ak+2

但是, 这里有重复计数的情况: n ? h( k ) h( n ? k ) ,
k ?2

n?2

(1) 同一条对角线由其关联的两个顶点分别计算 了一次,故总数应除以 2; (2)一个三角形剖分是由 n-3 条对角线构成的, 而他们每条都分别作为分割线计算了一次,故其总数 应除以 n-3。 于是: h(n ? 1) =
n?2

R2 An

n?2 1 ? n ? ? h( k ) h ( n ? k ) 2(n ? 3) k ?2

A1
图5

凸 n 边形对角线剖分示意图

即:

? h(k )h(n ? k ) ?
k ?2

2(n ? 3) h(n ? 1) n

代入式 1 中得:

h(n) = 2h(1)h(n ? 1) +
即:

2(n ? 3) 4n ? 6 h(n ? 1) = h(n ? 1) n n

nh(n) = (4n ? 6)h(n ? 1), ,
令 E (n) ? nh(n) 且 E (1) ? 1

h(n) =

E (n) n
66

组合数学讲义

第5章

递推关系与母函数

用迭代法,得:

E (n ? 1) 2n ? 2 2n ? 3 ? ? ? E (n ? 1) n ?1 n ?1 n ?1 2n ? 2 2n ? 3 即 E ( n) ? ? E (n ? 1) n ?1 n ?1 2n ? 2 2n ? 3 2n ? 4 2n ? 5 ? ? ? ? ? E (n ? 2) n ?1 n ?1 n ? 2 n ? 2 E (n) ? (4n ? 6)

? ??
? 2n ? 2 2n ? 3 2n ? 4 2n ? 5 4 ? 3 2 ?1 ? ? ? ??? ? ? E (1) n ?1 n ?1 n ? 2 n ? 2 2 ? 2 1 ?1

?

? 2n ? 2 ? (2n ? 2)! ? ?? (n ? 1)!(n ? 1)! ? n ? 1 ? ? ?
1 1 ? 2n ? 2 ? ? E (n) ? ? n n ? n ?1 ? ? ?

因此 h(n) ? 定理 1

n 个+1 和 n 个-1 构成的 2n 项 a1 , a2 ,?, a2n ,其部分和满足:

a1 ? a2 ? ? ? ak ? 0(1 ? k ? 2n) 的数列的个数等于第 n 个 Catalan 数

Cn ?

1 ? 2n ? ? ?(n ? 1) n ?1? n ? ? ?

证明:在 2n 项中有 n 个 1 的方案数为 ? ?

? 2n ? ? ,则 ? ?n?

所求方案数 = ? ? - 不符合要求的方案数 ?n? ? ? 而不符合要求的方案的特征:从左向右扫描,在某个奇数位 2m+1 上首先出现 m+1 个-1 和 m 个 1,在第 2m+1 位后还有 2n-(2m+1) = 2(n-m)-1 位。则在 2(n-m)-1 位中必然有 n-m-1 个-1 和 n-m 个 1。 把剩下的 2(n-m)-1 位的-1 与 1 互换,结果得到一个由 n+1 个-1 和 n-1 个 1 组成的 2n 位 数,即 ? ?

? 2n ?

? 2n ? ? 2n ? ?或? ? ,反之亦然。 ? ? ? ? n ?1? ? n ?1?

因而不符合要求的方案数 ? 由 n+1 个-1 和 n-1 个 1 组成的组合数,即

? 2n ? ? 2n ? ? 1 ? 1 (2n)! 1 ? 2n ? ? ??? ? n ? ? n ? 1? ? (2n)!? n!?n! ? (n ? 1)!(n ? 1)!? ? n!(n ? 1)! ? n ? 1 ? n ? ? ? ? ? ? ? ? ? ? ? ?
例 2 有 2n 个人排成一行进入剧场,入场费 50 元,2n 个人中有 n 个人有 50 元的纸币,
67

组合数学讲义

第5章

递推关系与母函数

n 个有 100 元的纸币,剧场售票处用一个空的现金收录机开始售票,有多少种排队方法使得只 要有 100 元的人买票,售票处就有 50 元找零。 解:有 50 元的人用+1 标识,有 100 元的人用-1 标识,且这 2n 个人是不可区分的,则方 案数为 Cn ?

1 ? 2n ? ? ? n ?1 ? n ? ? ?
1 ? 2n ? ? ?。 n ?1? n ? ? ?

如果这 2n 个人是可区分的,则方案数为 n! n! ? ?

68

组合数学讲义

第 6 章 Polya 计数理论

第6章

Polya 计数理论

在组合计数问题中经常遇到的困难之一是: 区分所讨论的问题类型的困难, 即哪些问题是 相同的,哪些问题是不同的,解决这个困难,就能在计数过程中避免重复或遗漏。引入 Polya 计数定理的目的在于区分问题的同类性,Polya 定理是组合数学中强有力的计数工具。 1937 年,美国数学家 Polya 以《关于群、图和化学化合物的组合计算方法》为题,发表 了长达 110 页的论文,这篇论文推广了 BurnSide 引理,给出了普遍适用的一般计数方法—— Polya 定理。

6.1



在数学史上,人们很早就掌握了求解一次方程和二次方程的方法。 ax2 + bx + c = 0 (a,b,c ? 实数 R)
2 则:x = ? b ? b ? 4ac ( ? ? b 2 ? 4ac ? 0 时有解) 2a 到了 16 世纪,人们也掌握了求三次方程和四次方程的方法,其解(根)都可以表示为系 数的四则运算(称有根式解) ,但在求解五次及五次以上的方程时遇到了极大的困难,经过三 百年的努力仍没有得到求根公式。 对 n 次方程解的求根公式的研究,Lagrange 迈出了重要的一步,他曾经预见到一般方程 的可解性问题最后都将归结到关于诸根的某种排列置换问题, 但他在按照自己的设想方案处理 五次方程时碰了壁, 使他放弃了工作。 但是, Lagrange 的研究思想启发了年轻的 Abel 和 Galois, 他们证明了一般的五次和五次以上的方程没有根式解, Galois 在判断一个五次及五次以上的方 程是否有根式解的研究过程中首次引入了群的概念。目前,群论是近世代数(也称抽象代数) 研究的重要内容。

6.1.1



定义 1 给定集合 G 和 G 上的二元运算―·‖(点乘) ,如果满足以下 4 个条件: (1)封闭性:―·‖运算在 G 上是封闭性的,即对任意 a, b∈ G,都有 a·b∈ G。

69

组合数学讲义

第 6 章 Polya 计数理论

(2)结合性:―·‖运算满足结合性,即对任意 a, b ? G ,都有(a·b)·c = a·(b·c)。 (3)存在单位元素:存在 e∈ G,对任意 a∈ G,都有 e·a = a·e = a,e 称为 G 的 单位元素。 (4)存在逆元素:对任意 a∈ G,恒有一个 b∈ G,使得 a·b = b·a = e,元素 b 称 -1 -1 为元素 a 的逆元素,记作 a ,即 b = a 。 则称集合 G 在运算―·‖下是一个群,简称 G 是一个群,记为(G,·。 ) 理解起来,群是满足某些运算条件的集合。 由于满足结合律, 将(a· c = a· c)记为 a· c, b)· (b· b· 推广到 n 个元素的运算 a1· 2· 3· an a a ?· 等于任一种结合。特别地,当 a1 = a2 = a3 = ? =an 时,记 an =a·a·?·a(n 个 a 的点乘) 例 1 G ={1, -1}在乘法运算下是一个群。 证: (1)封闭性:1 ? -1 = -1,1 ? 1 = 1,-1 ? -1 = 1,-1 ? 1 = -1。 (2)结合性:显然成立。 (3)单元素:显然,e = 1。 (4)逆元素:1 ? 1 = 1,-1 ? -1 = 1,所以,1-1=1,(-1)-1=-1。 例 2 对于任意两个正整数,当除以 n 的余数相等时,称他们为 mod n 相等。 证明 G = {0, 1, 2,?, n-1}在加法运算下对于 mod n 运算是一个群。 证明: (1)封闭性:除以 n 的余数只能是 0~n-1。 (2)结合性:对任意 a,b,c ? G,有 ((a mod n) + (b mod n)) + (c mod n) = (a mod n) + ((b mod n) + (c mod n)) (3)单元素:e=0,因为对于 a ? G,有 0 + a mod n = a mod n + 0 = a mod n (4)逆元素:对任意 a ? G,有 (a mod n) + ((n-a) mod n) = n mod n = 0 因此 a-1 =n-a

6.1.2 群的基本性质
群具有如下基本性质: 性质 1:群的单位元是唯一的。 性质 2:若 a·b = a·c,则 b = c,若 b·a = c·a,则 b = c。 性质 3:G 中每个元素的逆元素是唯一的。 性质 4:(a·b·c·?·l·m·n)-1= n-1·m-1·l-1·?·c-1·b-1·a-1
70

组合数学讲义

第 6 章 Polya 计数理论

性质 5:G 是有限群,设 g =|G|,即 G ={a1, a2, a3, ?, ag},对任意 a ? G 必存在一个最小 常数 r(a),使得 ar(a) = e 且 a-1 = ar(a)-1 证明:构造 a·a·?·a(r 个 a 的点乘)即 r 为最小常数。 a, a2, a3, ?, ag, ag+1 由群的封闭性,这 g+1 项都属于 G,而 G 只有 g 个不同元素,根据鸽笼原理,其中至少 有两项相等。设 al= am (1≤l ≠ m≤g+1) 不妨设 l ? m, 由于 al=e·am,则 al-m = e
r 令 r ? l ? m ,故 a ? e 。称 r 为元素 a 的阶,即

r ? min j | a j ? e, j ? 1,2,?, g

?

?

而 a·ar-1 = e,即 a-1 = ar-1。 不难证明,对于元素 a,集合 H = { a, a2, a3, ?, ar-1, ar = e}在原来群的运算下构成群,称 为 G 的子群。

6.1.3 子群、循环群、交换群
定义 2 设(G,· )是群,H 是 G 的非空子集,若 H 在运算―·‖下也构成群,则称 H 是 G 的子群。 定义 3 设(G,· )是群,若存在 a∈ G,且任何 G 中的元素 b 均可表示成 a 的方幂, 则称 G 为循环群,a 称为该群的生成元。 即在性质 5 中,有 H = G 成立。 定义 4 设(G,· )是群,对任意 a, b∈ G,恒满足 a·b = b·a 时(即满足交换律), 称 G 为交换群,也称 Abel 群。

6.2

置换群

置换群是非常重要的群,所有的有限群 G ={a1, a2, a3, ?, an}, (即 G 是有限集合)都可 以用一个 n 元置换群来表示。 在以下讨论中,不失一般性,令 G = {1, 2, ?, n}。

71

组合数学讲义

第 6 章 Polya 计数理论

6.2.1 置换群的定义
定义 1
?1

集合 G = {1, 2, ?, n}上的一一映射称为 n 元置换,记为
2 ? n ? ? ,其中 ? (1) , ? ( 2) ,?, ? ( n) 是{1, 2, ?, n}的一个全排列。 ? ? ( n) ? ?

? ?? ? ? (1) ? ( 2) ?

令 Sn 是 G 上置换的全体,则显然|Sn| = n!。 定义 2 令 δ1, δ2∈ n(即 G 上的两个置换) S ,定义运算―·‖为
? 1 ? ? 2 ?i ? ? ? 2 ? (? 1 (i))

即 ? 1 ? ? 2 ? ? 2 ? ? 1 ,解释为先作 δ1 的置换再作 δ2 的置换,其结果与先作 δ2 的置换再 作 δ1 的置换相同,则 Sn 对于元算―·‖构成群,则称(Sn,)为 n 次对称群, n,) · (S · 的任意子群称为置换群。 说明:上述运算也可写作: (i)?1 ? ? 2 ? (i?1 ) ? ? 2 ,即将自变量 i 放到置换运算符之前。因为置换 的复合运算顺序与函数的复合运算顺序相反,这种写法更易于体现置换的复合运算的特点。 例1

?1 2 3 4? 有置换 ? 1 ? ? ?3 1 2 4? ? ? ?

? 1 2 3 4? ?2 ? ? ?4 3 2 1? ? ? ?

? 1 2 3 4 ?? 1 2 3 4 ? 则 ?1 ? ? 2 ? ? ? 3 1 2 4 ?? 4 3 2 1 ? ?? ? ? ?? ?

? 1 2 3 4 ?? 3 1 2 4 ? ? 1 2 3 4 ? ?? ? 3 1 2 4 ?? 2 4 3 1 ? ? ? 2 4 3 1 ? ?? ? ? ? ? ?? ? ? ?
即先作 δ1 置换,再作 δ2 置换,置换过程如下:
1 2 1 2 1 2 1 2 1 ??? 3 ??? 2 , 2 ???1 ???4 , 3 ???2 ???3 , 4 ???4 ???1 ? ? ? ? ?

?

?

?

?

?

?

?

?

? 1 2 3 4 ?? 1 2 3 4 ? ? 1 2 3 4 ? 而 ? 2 ? ?1 ? ? ? 4 3 2 1 ?? 3 1 2 4 ? ? ? 4 2 1 3 ? ?? ? ? ? ? ?? ? ? ?
可见:δ1·δ2 ≠ δ2·δ1 例 2 {1, 2, 3}有 3! = 6 个置换,分别为:
??1 2 3 ? ?1 2 3 ? ? 1 2 3 ? ? 1 2 3 ? ? 1 2 3 ? ? 1 2 3 ?? ? ? ?,? ?,? ?,? ?,? ?,? ?? S n ? ?? ??1 2 3 ? ?1 3 2 ? ? 2 1 3 ? ? 2 3 1 ? ? 3 1 2 ? ? 3 2 1 ?? ? ? ? ? ? ? ? ? ? ? ?? ??

则 Sn 为一个置换群。 证明: (1)封闭性:
72

组合数学讲义

第 6 章 Polya 计数理论

?1 2 ? ?1 3 ?
?1 2 ? ?1 3 ?

3 ?? 1 2 3? ?1 2 ?? ??? 2 ?? 2 1 3? ?1 3 ?? ? ?
3 ?? 1 ?? 2 ?? 2 ?? 2 3? ?1 2 ??? 3 1 ? ?1 3 ? ?

3 ?? 1 3 2 ? ? 1 ?? ??? 2 ?? 2 3 1 ? ? 2 ?? ? ?
3 ?? 1 3 2 ? ? 1 ?? ??? 2 ?? 2 1 3 ? ? 2 ?? ? ?

2 3? ? 3 1? ?
2 3? ? 1 3? ?

?1 2 3 ?? 1 2 3 ? ?1 2 3 ?? 1 3 2 ? ? 1 2 3? ? ?1 3 2 ?? 3 1 2 ? ? ?1 3 2 ?? 3 2 1 ? ? ? 3 2 1 ? ?? ? ? ?? ? ? ? ? ?? ? ? ?? ? ? ? ?1 2 3 ?? 1 2 3? ?1 2 3 ?? 1 3 2 ? ? 1 2 3 ? ? ?1 3 2 ?? 3 2 1 ? ? ?1 3 2 ?? 3 1 2 ? ? ? 3 1 2 ? ?? ? ? ?? ? ? ? ? ?? ? ? ?? ? ? ?
(2)结合性:
? ?1 2 3 ?? 1 2 3 ? ?? 1 2 3 ? ? 1 2 3 ?? 1 2 3 ? ? 1 2 3 ? ?? ?? ? ?? ? ? ?? ? ? ? ? ?1 3 2 ?? 2 1 3 ? ?? 2 3 1 ? ? ? 2 3 1 ?? 2 3 1 ? ? ? 3 1 2 ? ?? ? ?? ? ? ?? ? ? ? ??
?1 2 3 ?? ? 1 2 3 ?? 1 2 3 ? ? ?1 2 3 ?? 1 2 3 ? ? 1 2 3 ? ? ?1 3 2 ?? ? 2 1 3 ?? 2 1 3 ? ? ? ?1 3 2 ?? 3 2 1 ? ? ? 3 1 2 ? ?? ? ?? ?? ? ?? ? ? ? ? ?? ? ?? ?? ? ?? ? ? ?

(3)单位元素: e ? ?1 2 ? ?1 2 ? (4)逆元素:

3? ? 3? ?

? 1 2 3 ?? 1 2 3 ? ?1 2 3 ? ? 1 2 3 ?? 1 2 3 ? ? 1 2 3 ? ? ? 2 3 1 ?? 3 1 2 ? ? ?1 2 3 ? ? ? 3 1 2 ?? 2 3 1 ? ? ? 2 3 1 ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ?

?1

?1 2 3? ?? ?3 1 2? ? ? ?

?1 2 3 ??1 2 3 ? ?1 2 3? ? ?1 3 2 ??1 3 2 ? ? ?1 2 3? ?? ? ? ? ? ?? ? ? ? ? 1 2 3?? 1 2 3? ?1 2 3? ? ? 2 1 3?? 2 1 3? ? ?1 2 3? ?? ? ? ? ? ?? ? ? ? ? 1 2 3?? 1 2 3? ?1 2 3? ? ? 3 2 1 ?? 3 2 1 ? ? ?1 2 3? ?? ? ? ? ? ?? ? ? ?
因而 Sn 构成一个置换群。 Sn 有如下子集 H1、H2、H3、H4、H5:

?1 2 ?? ?1 3 ?

3? ? 2? ?

?1

?1 2 ?? ?1 3 ?

3? ? 2? ?

? 1 2 3? ?? ? 2 1 3? ? ? ?
? 1 2 3? ?? ? 3 2 1? ? ? ?

?1

? 1 2 3? ?? ? 2 1 3? ? ? ?
? 1 2 3? ?? ? 3 2 1? ? ? ?

?1

??1 2 3 ? ? 1 2 3 ?? ?, ?? H 1 ? ?? ? ?? ? ? ??1 2 3 ? ? 3 2 1 ??

??1 2 3 ? ? 1 2 3 ?? ?, ?? H 2 ? ?? ? ?? ? ? ??1 2 3 ? ? 2 1 3 ??

73

组合数学讲义

第 6 章 Polya 计数理论

??1 2 3 ? ?1 2 3 ?? ?, ?? H 3 ? ?? ? ?? ? ? ??1 2 3 ? ?1 3 2 ??

??1 2 3 ? ? 1 2 3 ? ? 1 2 3 ?? ?, ?, ?? H 4 ? ?? ? ?? ? ?? ? ? ??1 2 3 ? ? 2 3 1 ? ? 3 1 2 ??

??1 2 3 ? ? 1 2 3 ? ? 1 2 3 ? ?1 2 3 ?? ?, ?, ?, ?? H 5 ? ?? ? ?? ? ?? ? ?? ? ? ??1 2 3 ? ? 2 3 1 ? ? 3 1 2 ? ?1 3 2 ??
则 H1、H2、H3、H4 为 Sn 的子群,因而 H1、H2、H3、H4 都是置换群,而 H5 不满足封闭性,因 而 H5 不是 Sn 的子群。

?1 2 3 ?? 1 2 3? ? 1 2 3? ? ?1 3 2 ?? 2 3 1 ? ? ? 2 1 3? ? H 5 ?? ? ? ? ? ?? ? ? ?

6.2.2 置换的轮换之积表示
? 1 ? ?? ? ?1? 2 n ? (1)包含了许 ? 置换记号是由 Cauchy 发明的,它有两个主要缺点: ? ? ?n ? ? ? ?

? ?2 ?

多重复的符号; (2)掩盖了置换所具有的潜在的结构。 Jordan 改进了置换的表示方法,将置换表示成多个轮换之积的形式。 定义 3 置换 δ∈ n 可以确定一个有向图 G = (V, E),其中 V = {1, 2, ?, n},E = {<i, S

δ(i)>且 i, δ(i) ∈ },从顶点 i 出发存在一条路径: i ? ? ?i ? ? ? ?2? ? ? ? ? ?li?1 ? ? ?li ? , V i ? 该路径构成了一个长为 l 的回路,对应一个长为 l 的轮换( i? ?i ?? ?2? ?? ?li?1 ) i ? 。 由于 δ 置换是一个一一映射,所以,图中任意顶点 i 的入度和出度均为 1。在路径
2 l ?1 l i ? ? ?i ? ? ? ?2? ? ? ? ? ?li?1 ? ? ?li ? 中,若 i, ? ?i ? , ? ?i ? ,?, ? ?i ? 是互不相同的顶点,而 ? ?i ? 是首次重 i ?

复出现的顶点,则 i ? ? ?li ? 。否则,若 ? ?li ? ? ? ?m (0 ? m ? l ) ,则顶点 ? ?m 的入度为 2。 i? i?
?1 2 3 4 5 6 7 8 ? 例 1 置换 ? ? 3 2 1 6 5 7 8 4 ? 确定的有向图如图 5 所示。 ? ? ?

1

2

3

4

8 图5

7

6

5

置换对应的有向图

由图 5 可以看到 (1 3)是一个长度为 2 的轮换, (2)和(5)是两个长度为 1 的轮换, 6 7 (4
74

组合数学讲义

第 6 章 Polya 计数理论

?1 2 3 4 5 6 7 8 ? 8)是一个长度为 4 的轮换。则 ? ? 3 2 1 6 5 7 8 4 ? 可表示为: ? ? ?

(1 3)
长度为 2

(2)

(5)

(4 6 7 8)
长度为 4

长度为 1

观察上例,发现: (1)由于轮换表示一个回路,因此轮换(a1, a2, ?, al)只与元素的相邻位置有关,与哪个 元素为首无关。例如: (1 2 3) = (2 3 1) = (3 1 2)。 (2)轮换因子的排列没有顺序要求。例如: (1 3)(2)(5)(4 6 7 8) = (1 3)(2) (4 6 7 8) (5) (3) 一般地, 若置换 δ 有 bi 个长度为(1≤i≤n) i 的不相交轮换因子, 则称 δ 是1 1 2 2 ?n 型置换,bi = 0 的轮换因子可以不必写出。例如: (1 3)(2)(5)(4 6 7 8)是 122141 型的。 定义 4 若两个轮换(a1, a2, ?, al)和(b1, b2, ?, bm)中没有相同的元素,则称这两个 轮换是不相交的。 定理 1 任何置换都可以表示成不相交的轮换之积。
b b bn

例 2 求正四面体关于顶点集合{1,2,3,4}的置换群。 解:将正四面体进行刚性旋转,则有以下 3 种情况:

1 2 (1)不旋转,对应恒等置换 ? ? ?1 2 ?

3 4? 4 ? ? (1)(2)(3)(4) ,确定 1 型置换 1 个。 ? 3 4?

(2)以顶点与对应面的中心的连线为轴旋转,这样的轴有 4 条,如图 6 所示。对于每一 条轴可做 120o 和 240o 两种旋转。对应置换为(1)(2 3 4)和(1)(4 3 2),确定 1131 型置换 8 个。
1

4 2 3

图6

以顶点与对应面的中心的连线为轴旋转

(3)以对应边中点的连线为轴旋转 180o,这样的轴有 3 条,如图 7 所示。确定置换为(1 3)(2 4),确定 22 型置换 3 个。

75

组合数学讲义 1

第 6 章 Polya 计数理论

4 2 图7 3

以对应边中点的连线为轴旋转

以上 3 种情况共 12 个置换构成 S4 的一个置换群,即 H ? S 4 。 H = {(1)(2)(3)(4), (1)(2 3 4), (2)(1 3 4), (3)(1 2 4), (4)(1 2 3), (1)(4 3 2), (2)(4 3 1), (3)(4 2 1), (4)(3 2 1), (1 3)(2 4), (1 2)(3 4), (1 4)(2 3)} 定理 2 若一个轮换的长度为 l,则该轮换自乘 l 次,得到 l 个长度为 1 的轮换。 2 3) = (1 3 2)

例 3 δ1 =(1 2 3) 则 δ12 = (1 2 3)(1 δ13 = (1 3 2)(1 2 3) = (1)(2)(3)

定理 2 一个置换若是 k 个长度为 l1, l2, ?, lk 的轮换的乘积,且 l1, l2, ?, lk 的最小 公倍数是 m,则这个置换自乘 m 次后,一定得出一个恒等置换。 例 4 有一副扑克牌 52 张,已排好序,且自下而上编号为 1, 2, ?, 52,按以下方法洗牌: 顶牌和底牌不动,其他牌交替放置,即

1 2 ? 52
分成两半 ?? ? ???

1 2 ?

27 28 ?
第一次对洗 ???????

26 52

1 27 2 ? 52

用这种方法洗牌,洗多少次后才能使牌恢复原来的顺序? 解:对应的置换为:

?1 2 3 4 5 6 ? ? 49 50 51 52? ? ?1 27 2 28 3 29 ? ? 25 51 26 52? ? (1)(2, 27, 14, 33, 17, 9, 5, 3) ? ? ?
(4, 28, 40, 46, 49, 25, 13, 7)(10, 31, 16, 34, 43, 22, 37, 19)(12, 32, 42, 47, 24, 38, 45, 23) (6, 29, 15, 8, 30, 41, 21, 11)(20, 36, 44, 48, 50, 51, 26, 39)(18, 35)(52) 即为 2 个长度为 1,一个长度为 2,6 个长度为 8 的轮换之积,而 1,2,8 的最小公倍数是 8, 所以,该置换自乘 8 次后就成为恒等置换,即洗 8 次牌后恢复原来的顺序。

76

组合数学讲义

第 6 章 Polya 计数理论

6.3
6.3.1 共轭类

Burnside 引理

Sn 中的置换可按轮换积的型的不同而分类。 例如, (1)(2 3)(4 5 6 7)属于 112141 型, 1 1 1 4)(5)(6 7)也属于 1 2 4 型。将 Sn 中具有相同型的置换全体称为与该型相应的共轭类。 定义 1 设 H(H ? Sn)是 Sn 的置换群,在 Sn 上定义 H 共轭:对任意 s, t? H, 若 存在 g ? H,使得 s = g-1 t g,则称 s 与 t 是 H 共轭的(即置换 s 和 t 是共轭的) 。

(1 2 3

解释:H 为一个共轭类,Sn 中所有同型的置换是关于 Sn 共轭的。共轭关系是一种等价关 系,即满足: (1)自反性:对任意 S ? H, 均有 S=I-1SI,其中 I 为恒等置换, 即 S 与其自身是共轭的。 (2)对称性: 若 s 和 t 是共轭的,即存在 g ? H, 使得 s = g-1 t g,而 t = (g-1)-1 s (g-1),且 g-1 ? H, 所以 t 与 s 是共轭的。 (3)传递性: 若 r 与 s 是共轭的,s 与 t 是共轭的,即存在 g1, g2 ? H,使得 r = g1-1 s g1,s = g2-1 t g2,则 r = g1-1g2-1 t g2 g1 =(g2 g1)-1 t(g2 g1),而 g2 g1 ? H,所以 r 与 t 是共轭的。 例 1 S3={(1)(2)(3), (1 2 3), (1 3 2), (1)(2 3), (2)(1 3), (3)(1 2)}, S3 有 3 个共轭类, 则 分别是 13 型 1 个,31 型 2 个,1121 型 3 个。以共轭类{(1)(2 3), (2)(1 3), (3)(1 2)}为例: (1)(2 3)的逆元是自身,则(2)(1 3) = ((1)(2 3)) ((3)(1 2)) ((1)(2 3)); (2)(1 3)的逆元是自身,则(1)(2 3) = ((2)(1 3)) ((3)(1 2)) ((2)(1 3))。 定理 Sn 中属于 1b1 2 b2 ? n bn 型的元素(置换)个数为

n! . b1 !b2 ...!bn !1b1 2b2 ...nbn

证: 1b1 2 b2 ? n bn 型置换的轮换形式为:
n个 ?n个? ??? ? ( x)...( x) ( xx)...( xx) ( xx..x)...( xx...x) ??? ? ?? ??? ? ? ? ? ??? ? b1个 b2个 bn个

其中, b1 ? 2b2 ? ... ? nbn ? n 。 把{1, 2, …, n}的一个全排列填入该框架中, 就得到这个共轭类的一个置换。显然,全排列 构造这个共轭类的置换时会产生许多重复,原因是: (1)轮换的书写方法。一个长度为 k 的轮换可以写成 k 种形式:

(a1a2 ...ak ) ? (a2a3...ak a1 ) ? ... ? (ak a1...ak ?1 )
而它们属于不同的全排列,长度为 k 的轮换因子有 bk 个,故应除以 k k (1 ? k ? n) 。
b

(2)互不相交的轮换的乘积可以交换,bk 个长度为 k 的轮换是互不相交的。在乘积中轮 换因子可以以任何顺序出现,而它们属于不同的全排列,故应该除以 bk !(1 ? k ? n) 。
77

组合数学讲义

第 6 章 Polya 计数理论

例 2 S4 中 22 型共轭类有

4! ? 3 个置换,即 2!? 22

{(1 2) (3 4), (1 3) (2 4), (1 4)(2 3)} S4 中 1 2 型共轭类有
2 1

4! ? 6 个置换,即 2!? 21

{(1)(2)(3 4), (1)(3)(2 4), (1)(4)(2 3), (2)(3)(1 4), (2)(4)(1 3), (3)(4)(1 2)}

6.3.2 k 不动置换类
设 G 是{1, 2, …, n}上的置换群,令 Zk ? {? / ? ? G, ? ( k ) ? k} 是 G 中使元

定义 2

素 k 保持不动的置换全体,则称 Zk 为 G 的 k 不动置换类。 ( Z k ? G) 例 3 G = {I, (1 2)(3)(4), (1)(2)(3 4), (1 2 3 4)}, 则:

Z1 ? Z2 ? {I ,(1)(2)(34)} , Z3 ? Z4 ? {I ,(12)(3)(4)} 。
定理 群 G 中关于 k 的不动置换类 Zk 是 G 的一个子群。 证明: (1)封闭性: p1 , p2 ? Z k , (k ) p1 ? p2 ? ((k ) p1 ) p2 ? (k ) p2 ? k , 则 p1 ? p2 ? Zk 。 (2)结合性: Z k ? G ,而 G 是一个置换群,满足结合律。 (3)单位元:显然, I ? Zk 为单位元. ( 4 ) 逆 元 : p ? Z k , 即 置 换 保 持 k 不 动 , 而 (k ) p?1 ? p ? e(k ) ? k , 而 p(k ) ? k ,

((k ) p ?1) p ? k ,所以 p ?1 (k ) ? k ,即 p?1 ? Zk 。
故 Zk 本身也是一个群,并且是 G 的子群. 将 k 不动置换类与对几何图形进行着色的例子联系起来,则 Zk 是由那些经过变换后使元 素 k 位置不变的变换组成的集合。 例 4 一个正方形有四个格子, 分别有 A, B, C, D, G ={σ1, σ2, σ3, σ4, σ5, σ6, σ7, σ8}, 其中 σ1, 设 σ2, σ3, σ4 依次表示将正方形旋转(顺时针)90? 180? 270? 360? 5, σ6, σ7, σ8 依次表示以直线 , , 和 ,σ l1, l2, l3, l4 为对称轴将正方形翻转,如下图所示。则有 ZA = ZD = {σ4, σ6},ZB = ZC = {σ4, σ5}。

78

组合数学讲义

第 6 章 Polya 计数理论

A B C D
l1 l3 l2

l4

6.3.3 等价类
设 G = {I, (12)(3)(4), (1)(2)(34), (12)(34)},在 G 的作用下,1→2→1, 1→1, 2→2,因此 1 与 2 属于一类;3→4→3, 3→3, 4→4,因此 3 与 4 属于一类。2 或 1 不能在 G 的作用下映射为 3 或 4,3 或 4 不能在 G 的作用下映射为 1 或 2,因此,1 和 2 属于一个等价类,3 和 4 属于一个 等价类。 定义 设 G 是 D = {1, 2, ?, n}上的置换群, 对任意 k, l∈ 若存在 σ∈ 使得 σ(k) G, G, = l,则称 k 与 l 是等价的,或称 k 与 l 属于同一个等价类,元素 k 所属的等价类记 为 Ek。 例 5 G = {I, (12)(3)(4), (1)(2)(34), (12)(34)},则 E1 = E2 = {1, 2},E3= E4 = {3, 4}。 注意: E k ? D 。 定理 设 G 是 D = {1, 2, ?, n}上的置换群,则 D 可按群 G 的置换分划成若干等价 类,称为 G 诱导出来的等价类。 解释:k 所属的等价类可以看作是 k 在 G 的作用下映射的“轨迹” 。 -1 (1)若存在 p1∈ G,使得 p1(k) = l,则一定存在 p2 = p1 ,使得 p2(l) = k,而 p2∈ G,即:

k ?l

p1

? p2 ? p1 1



l

? k

(2)若存在 p1, p2∈ G,使得 p1(k) = l, p2(l) = m,则一定存在 p3 =p1 p2,使得, p3(k) = m, 而 p3∈ G,即:

k ?l ? m 则 k

p1

p2

p3 ? p1 ? p2

?

m

由(1) (2)可知,k 在 G 的作用下,其“轨迹”形成一个封闭的类,故{1, 2, …, n}在 G 的作用下可分划成若干个等价类。 ※设 G 是 D={1, 2, …, n}上的置换群,对于 k ? G ,有对应得等价类 Ek 和不动置换类 Z k , 注意: Ek ? D , Zk ? G 。

79

组合数学讲义

第 6 章 Polya 计数理论

6.3.4 Burnside 引理
Burnside 引理 设 G = {p1, p2, ?, pg}是 D = {1, 2, ?, n}上的置换群,则 G 诱导出

的等价类个数是: l ?

1 g ? c( P ) i G i ?1

其中,c(pi)表示在置换 pi 的作用下保持不变的元素个数。 例 1 G = {I, (1 2)(3)(4), (1)(2)(3 4), (1 2)(3 4)},则 p1 = I = (1)(2)(3)(4),则 c(p1) =4; p2 = (1 2)(3)(4),则 c(p2) = 2; p3 =(1)(2)(3 4),则 c(p3) = 2; p4 = (1 2)(3 4),则 c(p4) = 0。 则 G 诱导出的等价类个数 l ? 1 (4 ? 2 ? 2 ? 0) ? 2 ,实际上,这两个等价类是: 4 E1 = E2 = {1, 2},E3 = E4 = {3, 4}。 例 2 一个正方形均分为 4 个格子,用两种颜色对 4 个格子着色,能得到多少种不同的方 案? 解:因为每个格子有两种颜色可供选择,故有 16 种可能方案,但经过旋转吻合的两种方 案应该属于同一种方案。

正方形

c1(0000)

c2(1111)

c3(1000)

c4(0100)

c5(0010)

c6(0001)

c7(1100)

c8(0110)

c9(0011)

c10(1001)

c11(1010)

c12(0101)

c13(1110)

c14(0111)

c15(1011)

c16(1101)

设 D = {c1, c2, ?, c16},G = {p1, p2, p3, p4} (1)不动置换 p1。 p1=(c1)(c2)…(c16),所以 c(p1) = 16。 (2)顺时针旋转 90° 2。 p
80

组合数学讲义

第 6 章 Polya 计数理论

p2 = (c1)(c2)(c3c4c5c6)(c7c8c9c10)(c11c12)(c13c14c15c16),所以 c(p2) = 2。 (3)顺时针旋转 180° 3。 p p3 = (c1)(c2)(c3c5)(c4c6)(c7c9)(c8c10)(c11)(c12)(c13c15)(c14c16),所以 c(p3) = 4。 (4)顺时针旋转 270° 4。 p p4 = (c1)(c2)(c3c4c5c6)(c7c8c9c10)(c11c12)(c13c14c15c16),所以 c(p4) = 2。 1 则不同等价类的个数为 l ? (16 ? 2 ? 4 ? 2) ? 6 。不同的方案为: 4

用 Burnside 引理来研究 m>2 种颜色的不同着色方案数,其求解过程很复杂,所以采用 Polya 定理。

6.4
6.4.1
Polya 定理的一般形式

Polya 定理

Polya 定理

设 G = {p1, p2, …, pg}是 D = {1, 2, …, n}上的置换群,用 m 种颜色对 D

上的 n 个对象着色,则不同的着色方案数为: l ?

1 G

?m
i ?1

g

c ( pi )

其中 c( pi ) 表示置换 pi 分解为不相交轮换之积中轮换因子的个数。 (包括长度为 1 的轮换) 注意与 Burnside 引理不同 例 3 一个正方形均分为 4 个格子, 用两种颜色对 4 个格子着色, 能有多少种不同的方案?

D = {1, 2, 3, 4},G = {p1, p2, p3, p4},则: p1:不动置换,p1 = (1)(2)(3)(4),则 c( p1 ) ? 4 ; p2:顺时针旋转 90° 2 = (1 2 3 4),则 c( p2 ) ? 1 ; ,p p3:顺时针旋转 180° 3 = (1 3)(2 4),则 c( p3 ) ? 2 ; ,p p4:顺时针旋转 270° 4 = (4 3 2 1),则 c( p4 ) ? 1 。则 l ? ,p
81

1 4 ( 2 ? 2 1 ? 2 2 ? 21 ) ? 6 。 4

组合数学讲义

第 6 章 Polya 计数理论

例 4 正六面体的 6 个面分别用红、蓝两种颜色着色,问有多少种不同方案? 解:D = {1, 2, 3, 4, 5, 6}使正六面体重合的刚体运动群有以下几种情况: (1)不动置换,即 p1=(1)(2)(3)(4)(5)(6), c( p1 ) ? 6 。 (2)绕过 1 面、6 面中心的 AB 轴旋转± ,对应有: 90° p2=(1)(2 3 4 5)(6),则 c( p2 ) ? 3 。 p3=(1)(5 4 3 2)(6),则 c( p3 ) ? 3 。 正六面体有 3 个对面,故同类的置换有 6 个。

(3)绕 AB 轴旋转 180° ,对应有: p4 = (1)(2 4)(3 5)(6),则 c( p4 ) ? 4 。 同类的置换有 3 个。 (4)绕平面对角线的平行棱 CD 轴绕 180° ,对应有: p5 = (1 6)(2 5)(3 4),则 c( p5 ) ? 3 。 正六面体中与对角线平行的中位棱有 6 对,故同类的置换有 6 个。 (5)绕对角线 EF 轴旋转± 120° ,对应有: p1 = (3 4 6)(1 5 2),则 c( p6 ) ? 2 。 p7=(6 4 3)(2 5 1),则 c( p7 ) ? 2 。 正六面体的对角线有 4 条,故同类的置换有 8 个。 综上,不同的着色方案数为: 1 l? (6 6 ? 6 * 6 3 ? 3 * 6 4 ? 6 * 6 3 ? 8 * 6 2 ) ? 2226 24 有重复的方案,再应用容斥原理。

6.4.2 母函数型的 Polya 定理
设 G = {p1, p2, …, pg}是 D = {1, 2, …, n}上的置换群,用 m 种颜色{c1, c2,…, cm}进行着色,

82

组合数学讲义

第 6 章 Polya 计数理论

不同的着色方案数为: l ? 1 G 在上式中, m
n

?m
i ?1

g

c ( pi )



c ( pi )

用(c1 + c2 + … + cm)λ1(pi), (c12 + c22 + … + cm2)λ2(pi),??,(c1n+c2n+…+cm

)λn(pi)替换,得

l ?

1 G

?S?
i ?1 1

g

1 (P i

)

? ? S 2 2 ( Pi ) ...S n n ( Pi )

其中 Sk = (c1k + c2k + … + cmk),k =1, 2, …, n,λk 表示长度为 k 的轮换因子。 重新解上例: (1)不动置换,为 16 型。 (2)绕 AB 轴旋转± ,为 1241 型。 90° (3)绕 AB 轴旋转 180° ,为 1222 型。 (4)绕 CD 轴旋转 180° ,为 23 型。 (5)绕 EF 轴旋转± 120° ,为 32 型。 所以

l?

1 [(x1 ? x2 ? x3 ? x4 ? x5 ? x6 ) 6 24 4 4 4 4 4 4 ? 6( x1 ? x2 ? x3 ? x4 ? x5 ? x6 ) 2 ( x1 ? x2 ? x3 ? x4 ? x5 ? x6 ) ? 3( x1 ? x2 ? x3 ? x4 ? x5 ? x6 ) 2 ( x1 ? x2 ? x3 ? x4 ? x5 ? x6 ) 2
2 2 2 2 2 2

? 6( x1 ? x2 ? x3 ? x4 ? x5 ? x6 ) 3 ? 8( x1 ? x2 ? x3 ? x4 ? x5 ? x6 ) 2 ]
2 2 2 2 2 2 3 3 3 3 3 3

由于是要求 6 种颜色各用一次, 要求 x1x2x3x4x5x6 项的系数只能在(x1+ x2+ x3+ x4+ x5 +x6)6 的展开 6! 6! 式中出现。由多项式定理,其系数为: ? 30 。 ? 6!,所以: l ? 11 1 ! !... ! 24

83

组合数学讲义

第7章

组合设计

第7章

组合设计

(区组设计)介绍的是组合计数,这一章介绍组合设计,可以应用到实验设计(科学地 安排实验) ,计算机编码/译码等领域。 ep:有{1,2,3,4} 4 种品牌的汽车轮胎磨损测试,由于同一牌子的轮胎在不同部位的磨 损程度有差别,所以不能仅试验一个部位的轮胎,若动用 4 辆小汽车(A,B,C,D)参加试验, 可以安排如下: 2    4 ? 左前轮 ?1   3   ? 一列都没有相同元素; 3   1 ? 右前轮 ?2    4      观察:每一行,每 ? ? ?   每一列构成了一个 区组,整个试验方案 3   1   左后轮 ?  4    2? 1   3 ? 右后轮 ?4    2      由4个区组构成。 ? ?
     B C D A

这样安排的试验,其构点是每一种品牌的轮胎在不同的位置,不同的小汽车上都均衡的 做了安排,每一种品牌的轮胎都用了 4 次,试验的次数也均衡。

7.1

拉丁方与正交拉丁方

拉丁方是 Latin Square 的音译,本身就是一门饶有趣味的学问。

7.1.1 拉丁方

定义 1

由 1,2,3,…, n 构成的 n? n 方阵 (aij ) n?n ,要求每行,每列中各元素

恰好出现一次,这样的方阵称为 n 阶拉丁方。

7.1.2 正交拉丁方
36 名军官问题:有 36 名军官,来自 6 个不同地区,每个地区 6 名军官且这 6 名军官的军
84

组合数学讲义

第7章

组合设计

衔不同,现要将这 36 名军官排成 6 ? 6 方阵,要求每行、每列中都有来自 6 个地区的军官各一 名,且每行、每列中 6 种军衔的军官各一名。 分析:每一名军官有两个标志,一个是军衔,一个是地区,对应一个偶对 (i, j ) ,其中 i 为 军衔标志, j 为地区标志, i,j = 1,2,…,6。则 36 名军官问题对应于一个由偶对 (i, j ) 构 成的 6 ? 6 方阵,且第一个数字构成一个 6 阶拉丁方,第 2 个数字也构成一个 6 阶拉丁方,36 对偶对 (i, j ) 中,每队序偶只出现一次。 定义 2
( ( ( ( 设 A1 ? (aij1) ) n?n , A2 ? (aij2) ) n?n 是两个 n 阶拉丁方,若矩阵 ((aij1),aij2) ))n?n

( ( 中的 n2 个序偶 (aij1),aij2) ) ( i =1,2,…,n)互不相同,则称 A1 和 A2 正交,或称

A1 和 A2 是相互正交的拉丁方。
?1 例如: A ? ?2 1 ? ?3 ? 2 3 1

?1 3? ? , A ? ?2 1  2 ? ? ?3 2? ? ?

3 1 2

2? 3? ,A1 和 A2 都是 3 阶拉丁方。 ? 1? ?

矩阵

( 1 ) 3) 2) ? 1, (2, (3, ? ? 2, (3, ( , ? ( 2) 1 ) 1 3) ? ? ? 3) 1 2) (3, ( , (2, ? 1 ? ) ?

中的 9 对序偶均不相同,故 A1 和 A2 是正交的。

并不是任意的正交拉丁方都是存在的,36 名军官问题是无解的,即不存在一对 6 阶正交 拉丁方。

7.1.3 正交拉丁方的性质
定理 1 相互正交的 n 阶拉丁方的个数不超过 n-1 个,即若 A1、A2、…Ak 是两两正 交的 n 阶拉丁方,则 k≤n-1。 例如:3 阶拉丁方只有一对是正交的。 当 k = n - 1 时,A1、A2、…An-1 是一组正交的 n 阶拉丁方,则称 A1、A2、…An-1 是完全的 n 阶正交拉丁方族。

7.2
7.2.1 域的概念

正交拉丁方的构造

定义 3 F 是至少含有两个元素的集合,对 F 的元素定义“+”和“· ”两种运算, 并满足以下三个条件的代数系统<F,+, ·>称为域: (1)F 的元素关于“+”运算为交换群,设其单位元素为 0;
85

组合数学讲义

第7章

组合设计

(2)F\{0}的元素关于“· ”运算为交换群; (3)满足分配律,即对于 a、b、c ? F,有 a·( b + c ) = a·b + a·c ( b + c )·a = b·a + c·a 如果集合 F 的元素个数无限,则称为无限域,否则称为有限域。

例如,实数的全体关于通常的加法和乘法运算构成域,称为实数域。 再如,若 p 是素数,则 F = {0,1,…,p-1}在 mod p 的意义下关于加法和乘法运算构成 域。设 F = {0,1,2,3,4} ,p = 5,有 + 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3

· 1 2 3 4

1 1 2 3 4

2 2 4 1 3

3 3 1 4 2

4 4 3 2 1

7.2.2 用有限域构造完全的正交拉丁方族
定理 2 若存在一个素数 p 和一个正整数 α,对于任何 n = pα(n≥3),存在 n-1 个相 互正交的 n 阶拉丁方。 例如,3 = 31,则存在两个 3 阶的正交拉丁方;4 = 22,则存在三个 4 阶的正交拉丁方;5 = 5 ,则存在四个 5 阶的正交拉丁方; 但不能回答是否存在 6 阶正交拉丁方的问题。
1

定理 3 设 F = {a0, a1, ?, an-1},|F| = n = pα(α 为正整数,p 是一个素数) ,其中
( a0 = 0 , a1 = 1 , 构 造 A1, A2, ? , An-1 为 Ak ? (aijk ) )n?n (1 ? k ? n ? 1) , 其 中

( aijk ) ? ak ? ai ? a j (0 ? i, j ? n ?1,1 ? k ? n ?1, ) ,则 A1、A2、…Akn-1 构成完全的正

交拉丁方族。 例如:构造 3 阶完全的正交拉丁方族。 解:F = {0, 1, 2},其加法和乘法运算表如下: + 0 1 2 0 1 2 0 1 2 1 2 2 0 0 1 · 0 1 2 0 1 2 0 0 0 0 0 1 2 2 1
86

组合数学讲义

第7章

组合设计

得:

0 0 0 ?1· ? 0 ? 0 1· ? 1 ? 1 1· ? 2 ? 2? ? 1·? 0 ? 1 1·? 1 ? 2 1·? 2 ? 0 ? A1 ? ? 1 1 1 ? ?1· ? 0 ?   1· ? 1 ? 0 1· ? 2 ? 1? 2 2 2 ? 2 ?
作置换 ? ?

1   ?0    2? ?2    1? A2 ? ? 0    ? ?1   0? 2    ? ?

1   ? 0   2 ? ? 得: ? 2   ?1   3 ?
2    ?1   3 ? ?3   2 ? A2 ? ? 1   ? ?2    1  ? 3   ? ?
?

2    ?1   3 ? ?   3   A1 ? ? 2    1? ? ?3   2   ? 1   ? ?
? ?

定理 4

设 n ? p1 1 p1 2 ? p1 n 是 n (n ? 3) 的素数幂分解,r = min{ p1 j -1},则 n 阶

?

拉丁方存在 r 个正交拉丁方。 该定理还不能判断是否存在 b 阶的正交拉丁方,因为 6 = 2?3 r = min {2 -1, 3-1}=1 欧拉猜想不存在 b 阶的正交拉丁方,但历经 100 年既不能肯定也不能否定,直到 1900 年 才获得证明。

7.2.3 由低阶的正交拉丁方构造高阶的正交拉丁方
B1, B2, ?, Bk 是一组 m 阶正交拉丁方,则构造 k 个 mn 阶正交拉丁方 C1, C2, ?, Ck 为:
(r ?(a11 ) , B r )   12) , B r )    1n) , B r )? (a ( r ? (a ( r ? (r ) ? ( ( (a2r ) ? (a2r ) ?(a2 , B r )    2 , B r )     n , B r )? 1 Cr ? ?     ?       ?       ? ? ? ? (r ) (r ) (r ) ?(a n1 , B r )   n 2 , B r )    nn , B r )? (a ? (a ? ?

其中
( r r r ?(aijr ) , B11 )   ijr ) , B12 )    ijr ) , B1m ) ? (a ( ? (a ( ? (r ) r ? (a ( r ) r ? (a ( r ) r ?(aij , B 21 )   ij , B11 )    ij , B 2m ) ? (r ) ( aij , B r ) ? ? ? ?       ?       ? ?     ? ?(a ( r ) , B r )   ( r ) , B r )    ( r ) , B r )? ( aij ? (a ij m1 m2 mm ? ? ij

87

组合数学讲义

第7章

组合设计

3   1? 2   3 ? ?4   2    ?4    1   1   ?3   2 ? 2    ?3   1 ? ?   4   2? ?   1   4? ? ? 例如: A ? ?   1   A2 ? ?   3   B ? ? 3   1   B ? ? 3   2   ? ? 1 2 ? 2    1? 1 ?2   4   ? 2    3? ?2    3   1   3 ? 4   1 ? ?1   3  ? ?1   2   ? ? 2    ? ? 3   ? ? ? ? ? 2   4  3   2   ?1   3   ? ?1   4    ?
即 A1 和 A2 是一对 3 阶正交拉丁方,B1 和 B2,是一对 4 阶正交拉丁方,从而可以构造一对 3×4 = 12 阶的正交拉丁方 C1, C2:
? (3, B1 ) (2, B1 ) (1, B1 ) ? C1 ? ?(2, B1 ) (1, B1 ) (3, B1 ) ? ? ? ? (1, B1 ) (3, B1 ) ( 2, B1 )? ? ? ? (3, B 2 ) (1, B 2 ) (2, B 2 )? C 2 ? ?(2, B 2 ) (3, B 2 ) (1, B 2 ) ? ? ? ? (1, B 2 ) (2, B 2 ) (3, B 2 ) ? ? ?

其中

?(3,4) (3,3) (3,2) (3,1) ? ? (3,3) (3,4) (3,1) (3,2)? ? ( 3 B1 ) ? ? , ?(3,2) (3,1) (3,4) (3,3) ? ? ? ? (3,1) (3,2) (3,3) (3,4)?

?(3,4) ? (3,3) ( 3 B2 ) ? ? , ?(3,2) ? ? (3,1)

(3,2) (3,1) (3,4) (3,3)

(3,1) (3,2) (3,3) (3,4)

(3,3) ? (3,4)? ? (3,1) ? ? (3,2)?

其余的以此类推,再分别对这 12 个序偶给以从 1 到 12 的标号(即作一个映射或置换)得到一 对 12 阶正交拉丁方。 ? (1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (3,4) (3,1) (3,2) (3,3) (3,4) ? ? ? ?? ? 1 2 3 4 5 6 7 8 9 10 11 12 ? ? ?

7.3

正交拉丁方的应用举例

例 1 采用 4 辆汽车{A,B,C,D}对 4 种品牌的轮胎{l1, l2, l3, l4}进行测试,若同时试 验 4 种不同品牌的刹车车闸{ C1, C2, C3, C4 }对车胎的磨损,该试验需要一对 4 阶正交拉丁方。 解:试验要求(1)每种品牌的轮胎在每辆汽车出现一次; (2)每种品牌的轮胎在汽车的 4 个不同位置各出现一次; (3)不同品牌的轮胎和车闸恰好配合一次; (4)4 种车闸在 4 辆车 及 4 个不同位置各出现一次。 下面两个正交的拉丁方,A1 是轮胎的试验安排,A2 是车闸的试验安排。

左前 ?1 左后 ?2 ? A1 ? 右前 ?3 ? 右后 ?4

2 3 4? 1 4 3? ? 4 1 2? ? 3 2 1? A B C D

元素 i 表示轮胎的编号。

左前 ?4 左后 ?3 ? A2 ? 右前 ?1 ? 右后 ?2 A

1 2 3? 2 1 4? ? 4 3 2? ? 3 4 1? B C D

元素 i 表示车闸的编号。

88

组合数学讲义

第7章

组合设计

则下面的矩阵是车胎与车闸的配合试验安排

      B  C  D A 左前 ? (1,4) (2,1) (3,2) (4,3) ? 左后 ? (2,3) (1,2) (4,1) (3,4) ? ? ? 右前 ? (3,1) (4,4) (1,3) (2,2)? ? ? 右后 ?(4,2) (3,3) (2,4) (1,1) ?
这个方阵的元素(i, j)(i, j = 1, 2, 3, 4)没有重复出现,即 16 个元素不相同,每种轮胎和每种车 闸都恰好配合一次。 例 2 假定有 4 种感冒药,4 种退烧药和 4 种止咳药,试验它们的配合效果,找 4 位病人 进行试验,在 4 天内完成试验,若只考虑一种感冒药,可用一个 4 阶拉丁方。 A B C D 其中 A,B,C,D 为病人;a,b,c,d 为日期。若考虑到两种药的配 a ?1 2 3 4 ? ?2 1 4 3? 合,则需要一对 4 阶的正交拉丁方;若考虑到三种药的配合,则需要 b? ? c ?3 4 1 2? 三个 4 阶的正交拉丁方。 ? ? d ?4 3 2 1 ?

7.4

平衡不完全区组设计

平衡不完全区组设计 BIBD:Balanced Incomplete Block Design 前面讨论的 4 中品牌的轮胎用 4 辆汽车进行试验, 每辆汽车的轮胎试验称为一个区组。 若 参加试验的轮胎有 5 个品牌,但一辆汽车(区组)只能装 4 个轮胎,则这样的试验称为不完全 的区组设计。 例如,用 5 辆汽车对 5 种轮胎进行如下试验:

A B C D E 左前 ?1 左后 ?2 ? 右前 ?3 ? 右后 ?4 2 3 4 5? 3 4 5 1? ? 4 5 1 2? ? 5 1 2 3?

观察:每一区组只含 4 种轮胎;每一种品牌的轮胎都作了 4 次试验。

7.4.1 平衡不完全区组设计的定义
定义 3 设 S = {S1, S2, ?, Sr},B = {B1, B2, ?, Bb}是 S 的 b 个子集,如果 B 满足 (1)|B1| = |B2| = ? = |Bb| = k; (2)S 中的任何元素均属于 r 个区组; (3)S 中的任一对元素均包含在λ 个区组中, 则称 B 是平衡不完全区组设计,其参数记为 (b, v, r , k , ? ) -BIBD。
89

组合数学讲义

第7章

组合设计

理解起来,平衡不完全区组是: (1)由 S 的子集构成区组的集合,b 为子集(即区组)的个数; (2)每个区组含有 S 中的 k 个元素; (3)S 中的每个元素在 b 个区组中恰好出现 r 次; (4)任意一对 S 中的元素在 b 个区组中恰好同时出现 ? 次。 平衡的含义是: (1)所有区组的容量相同(|Bi| = k) ; (2)S 中的任意元素在区组中出现的次数相同(r 次) 。 (3)S 中的任一对元素在区组中相遇的次数相同( ? 次) 。 不完全的含义是: k ? v 。 例: S ? {S1 , S 2 , S3 , S 4 }
v?4

B1 : S1 , S 2 , S3 } {

B2 : S 2 , S3 , S 4 } B3 : S3 , S 4 , S1} B4 : S 4 , S1 , S 2 } { { {

为(4,4,3,3,2)-BIBD。

B1 ? S1 ?S ? 2 ?S3 ?

B2 S2 S3 S4

B3 S3 S4 S1

B4 S4 ? S1 ? ? S2 ? ?

7.4.2 Steiner 三元系(斯梯纳三连系)
定义 4 k=3 的平衡不完全区组设计称为三元系 (b, v, r ,3, ? ) -BIBD。

? =1 的三元系 (b, v, r ,3,1) -BIBD 称为 Steiner 三元系。
定理 5 Kinkman(科克曼定理) v 个对象的 Steiner 三元系存在的必要条件是 : v ? 6n ? 1 或 v ? 6n ? 3 (n 为非负整数) 。 对于 Steiner 三元系,参数 r 和 b 完全由 v 决定,即
r? v ?1 2 , b= v (v ? 1) 称为 v 阶 Steiner 三元系,记为 ST( v )。 6

Kinkman 女生问题(组合数学的古典名题) :一个班有 15 名女生,每天排队出来散步, 15 个人分成 5 行,每行由 3 名女生组成,要求在 7 天里每个女生和其他女生相伴一次且仅一 次。称两人在同一组(行)为一次相遇。

3 分析: 每天分 5 组, 每组 3 人, 共有 ? ? ? 5=15 次相遇; 个人每两个人都要相遇一次, 15 ? ? ? 2? ? ?
105 应有 ?15? =105 次相遇; ? 7 ,正好 7 天可以完成,安排如下: ? ? ?2? 15 ? ?
90

组合数学讲义

第7章

组合设计

第1天

第2天

第3天

第4天

第5天

第6天

第7天

1 2, 1 4, 1 6, 1 8, 1 10 11 1 12 13 1 14 15 ? 第1组 ?( , 3) ( , 5) ( , 7) ( ,9) ( , ,)( , , )( , , ) ? 4,12) (2,10) (2,11 (2, , )(2, , ) (2, 6) (2,7)? ( 8, 9,) 12 14 13 15 4, 5, ? 第2组 ? 8, ? 10 15 13 14 12 15 5, 4, 9, 8,) 第3组(5, , )(3, , )(3, , ) (3,6) (3, 7) (3,10) (3,11 ? ? ? 9, ) 10 14 1115 9, 1114 9, ) 第4组(6, , ) (6,15 (4, , )(4, , ) (5,12) (5, , ) (4,13 ? ? 1113 ( 1112 8, ) 10 13 8, 8, ) 10 12 ? 第5组 ? 7,14) (7, , ) (5,13 (7, , ) (6,14) (7,15 (6, , ) ? 9, ?
当 v ? 3 时: r ? v ? 1 ? 1 , b= v(v ? 1) ? 1 2 6 当 v ? 7 时: r ?

则(1,3,1,3,1)-BIBD

S={1,2,3} ST(3)={{1,2,3}}

v ?1 v(v ? 1) ? 3 , b= ?7 2 6

则(7,7,1,3,1)-BIBD

S={1,2,3,4,5,6,7} ·由于 1 与 2,3,4,5,6,7 各相遇一次,故区组中可包括:{1,2,3},{1,4,5},{1,6, 7}。 ·由于 2 与 3,4,5,6,7 各相遇一次,但 2 与 3,4 与 5,6 与 7 已相遇过,所以包含 2 的区 组中是:{2,4,6},{2,5,7}。 ·由于 3 与 4,5,6,7 各相遇一次,但 4 与 5,4 与 6,5 与 7,6 与 7 已相遇过,所以包含 3 的区组是:{3,4,7},{3,5,6}。 综上,ST(7)={{1, 2, 3},{1, 4, 5},{1, 6, 7},{2, 4, 6},{2, 5, 7},{2, 4, 6},{2, 5,7}} v ?1 v(v ? 1) 当 v ? 15 时: r ? ? 7 , b= ? 35 则(35,7,7,3,1)-BIBD 2 6

91


相关文章:
更多相关标签: