目 录 第一章排列与组合……………………………………1 §1.1集.计数的和、积法则…………………… §1.2排列与组合…………………………… 1.3一些注记 noaP S1.4细合的母函数…………………………………………………23 §1.5排列的母函数…… §1.6例…………………………… 34 第二章母函数……………… 39 §2,1母函数的代数运算……… 39 §2.2形式幕级数的分析运算和有限形式 §2.3普母函数与指母区数间的关系及其他… §24概率论中的一些母函数………… §2.5 Stirling数和Lab数 §2.6复合函数的高阶微商……… 第三章反演公式… §3,1容斥原理 §3,2应用举例……………………………… §3.3广容斥原理 §3.4 Mobius反演……… ……100 §3.5偏序集上的M8biu反演… 110 §3,6其他一些反演…………………………………………12l 第四章递归关系………………………………124 §4,1递归关系的建立…………………… §4.2一元线性递归关系………………………… …l29 否线性递归关系 134 §4.4Abel恒等式… 136 §4.5 Ramsey定理……………………l41
5+.6 Ramsey定理的应用………………150 54.7 Ramsey数 152 第五章(031)-矩阵 ………………159 §5.1桕异代表…………………………………159 55.2相异代表和(0,1)-矩阵………………………166 55.3线秩和项秩 55.4(0,1)矩阵类(R,S)…… 178 §5.5规范类u(R,S)… a187 §5.6(U,1)矩阵与拉丁矩…………………………【91 第六章置换群中的一些组合问题 l97 §6.1置换类 …………197 §6.2具有固定的轮换个数的置换 ………203 56.3具有指定轮换长度的置换………2L §6.4有关奇、偶置换的一些计数问题…… …215 第七章分配………………………222 57.1概论 、,中、·平 222 57.21型分配问题………………225 57.3Ⅱ型分配问题……… 238 57.4ⅢI型分配问题…………………………2+9 575Iv型分配问题 256 57.6VV型分配问题 ………257 第八章分拆…………………259 §8,1概论… 259 §8.2有序分拆………………………264 §8.3分拆的母函数 274 §8.4分拆的 Ferrers图 §8.5芫全分拆…………291 §8,6集B={3"4,…s}的情形…… 294 §8.7pn的估值…… 鲁, ……………………305 §8.8p的数论性质………………………………… 第九章限位排列 ……………314 59.L概论 ……………314
§9.2关联矩阵和棋阵………………………………………319 §9.3关联矩阵和棋阵的性质(I) 329 §9.4矩形棋阵……………………………………34 §9.5关联矩阵和棋阵的性质(I)… §9.6阶梯形棋阵………………………………………356 §9.7梯形棋阵 367 第十章 Polya计数定理 …373 §1.置换群的轮换示式………………………………………373 10.2在一个置换群下的映射等价类………………………………38 §10.3 Burnside引理…………………………………………384 510.4P6ya定理及其推广 387 5105(1-1)映射的等价类数……………………………394 考资料…………… 402
第一章排列与组合 本章介绍最简单、最基本的组合论课题,即通常的“排列”、“组 合问题。考虑问题的思路和解决问题的方法,都力求多样,以利于 培养“组合思维”和熟练“组合技巧”,提高灵活地用之于较复杂的组 合论问题的能力 有两个简单易明的计数法则今后将经常用到,故放在本章之首 来介绍(S1.1).按着,便讨论几个常见的组合问题和组合数的 一些初等性质(S1.2),及其必要的扩充和推广(§1.3).此外,还 介绍了研究排列数、组合数的母函数方法(51.4515),一方面由 此可得出更多的结果.另一方面又为过渡到函数的一般理论(第 二章)提供一些必要的感性材料.最后介绍几个应用的例子(51.6) §1.1集.计数的和、积法则 为了便于引用,这里列出集论的一些简单概念和符号,并不牵 涉数学基础中的深问题和集论的专门矩识.关于自然数的常用 性质,则假定读者已经熟知 人们把所研究的对象叫做元案,或元,把某些元的总体叫做集 合,或集,并说这集由这些元组成.本书中,若不特划声明集中某 些元是相同的,则认为所有元都是互异的,一般情况下,用大写的 拉丁字母表示集,用小写的拉丁字母表示元,元a在集A中,成者 说集A含有元a,记为 a∈d,成d3a 元a不在集A中,或者说集A不含有元a,记为 akA或Aa 如果集A中的每元都在集B中,就说A是B的子集,或者说B是 A的包集,记为
sB或BA 如果集A与B之间既合A=B,又合B→A,就说集A与B相等, 记为 否则记为 d aF B 如果A≌B但A÷B,则说A为B的真子集,或者说B为A的 真包集,记为 或B 易知,A=B的充要条件是集A与B由同样一些元素组成。为了 方便和统一起见,对没有任何元的情形也说存在一个集,叫做空 集,记为∞.不是空集的集叫非空集.易知,对任意集A,有 小sA:对任意非空集B,有cB. 为了确定一个集,常用以下几种方法 第一,列出集A中的全部元。例如, 9,12,15 18 表示集A是由3,6,9,12,15,18这六个数组成的总体、这里,符 号“:=“表示由右节来定义左节的定义式 第一,给出集A中元的特征性质P—合于性质P的元全在 中,不合性质P的元则不在A中,记为 A:一{x|x合于P. 这样,(11.1)中的A又可写为 A{x|1≤x≤20,且3]x}, 这里,符号“3|x表示整数x是3的倍数 第三,用集之间的运算来表出,最基本的运算有:并、交、 差 如果三个集A,B,C之间符合 A口{x|x∈B或x∈C 则说集A是集B,C的并,记为 Uc