目 录 第一章排列与组合……………………………………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
如果这三个集符合 一{x!z∈B且x∈C}, 则说集A是集B,C的交,记为 d=B∩C 如果这三个集符合 ∈B且xkC 则说集A是集B对C的差,记为 A一B\C. 并与交的定义和记号容易推广到多个乃至无穷多个集的情形,它 们分别是 A:∪A={xx∈A(某i∈)} A:=∩A:{x|x∈A(切i∈1)} 这里I为指标集 如果按照某一确定的规则φ,集A的每一元a都对应于集B 的唯一一个确定的元4,则称这个对应规则为映射或对应,并说a 是a在映射q之下的像,记为 d=:φ(a)或 这里,符号“=:”表示由左节来定义右节的定义式,如果 B={(a)a∈A}, 则说映射甲是A到B内的映射,并说集A为P的定义域,集B为q 的值域如果 B-{q(a)|a∈A}, 则说甲是A到B上的映射.如果是A到B内的映射,且合条件 g(a2),若 (1.12) 则说甲是A到B内的(1-1)映射.如果是A到B上的映射且合 条件(11.2),则说是A到B上的(1-1)映射,简称为(I-1) 映射。此时又说,集A与B是(1-1)对应的,如果集A与B之间
有一个(1-1)映射存在就说集A与B等势,记为 N B 付于等势的集,又说匕们具有相同的势.势就是等势诸集的公共 性质 用Z表示全体整数所组成的集,用N表示全体自然数所组成 的集,且记N=N∪{0}.称集 x1m≤x≤n,x∈ 为z的m至n截段,记为 【m,a] 也记 m,∞):一{x|m≤x<∞,x∈公}, ≤m,x∈Z}, (m,n]:冖Lm,n]{m}, (m,∞):冖1m,∞){m}, ( 如果集A与[1,n]等势,就说是一个n元集其中恰有n个元 空集和n元集(nEN)统称为有限集.不是有限集的集叫做无限 集。易知,当A,B是有限集时,A~B的充要条件是A,B各有同 样多的元,故此时d的势就是A的元的个数,简称为元数.对于无 限集,势的作用类似于有限集的元数的作用。无论A是有限集还 是无限集,其势均以」A|记之 下面介绍有关计数问题的两个基本法则 定理111(和则).岩有限樂A,B符合A∩B〓则 AUB|=|4|+|B (1.1.3) 证明当A,B中有一个是空集时,结论(11.3)是平凡的 今设卡中,B卡中,记 b 因为 午h(1≤1≤n;1≤1≤m)
故映射 (I≤i≤n) 十j(1 是A∪B到[!,m+n】上的(1-1)映射,故有(113).证毕 和则还可叙述为:如果某物C1有m种方法(这些方法所组成 的集记为A)选出,另一物O2有另外#种方法(这些方法所组成 的集记为B)选出,则定理1.2.1断言,选出物②1或C2有m+ 种方法 设A,B是任惫二集,则称集 (a,b)!a∈A,b∈B} 为集A与B的 Descartes积,记为A×B,同样可以定义任意多 (有限或无限)个集的 Descartes积.须注意,d×B中二元相等, 即(ab)=(41,如1)的充要条件是 且b〓b A×B中的元(a,b)称为A中元4与B中元b的有序对.易知, A×φ冖中×!冖巾,令 D(A,{B}n){(4,b)a∈A,b∈B,且|Bn}, 这里{Ba}a∈A表示由随a而定的集B所组成的集族,如果对任意 的a∈A都有B=B,则记 D(A, B: n):=D(A,B.lae4i n) 易知,当|B}=”时,有 D(A,B;n)一A×B 定理112(积则)如果|Ai一m,JBa叫n(a∈A) m∈N,n∈N,则 ID(A,iBed n) 证明。若m=0或n〓0,则(1.14)的两节同时为零设 0,且记 B〓{bnb }(1≤≤m)
则映射 q:(a,b;)→(i-)m+(!≤i≤m;1≤j≤n) 是集D(A,{Ba}∈4;n)到l1,mn]上的个(1-1)映射,故 (114)成立.证毕 积则还可叙述为:如果某物1有m种方法(这些方法所组成 的集记为A)选出,由中任一种方法a选出O1之后,都有m种方 法(这些方法所组成的集记为B选出另一物巴2,则定理122断 言依次选出物O1和的2有mn种方法 上述两个定理均可推广到有限多个集的情形 定理11.3设诸集A(1≤i≤n)合于 A1∩A;如中(1≤ij≤n), 则 UA,=∑1A (1.1.5) 定理114.已给集A和n1…n∈N.若诸集A,(1≤i k)逐次确定为 A1:当1 A:=D(A1-1,{(B4}A-;n)(2≤j≤饣), 其中集(B;)依A-:中的元a而定,且设|A1|=n1,|(B;) n(a∈A1-1,2≤1≤k),那末, 上述两个定理的证明可由数学归纳法得出 §1.2排列与组合 为了便于引用和比较,首先给出各种常见的排列、组合的定 义 定义121.集A的一个排列是A中元的一个有序选出.若 R是对排列的限制条件,则这样的排列叫做R-排列;如果R的叙 述较长,又写为“排列2具有性质R”特别地,如果性质R是“排列
中元的个数是”,这种R排列就简称为r-排列,又说r是该排列 的长.如果性质R是“在排列中不允许任何元重复出现”,则这种 R-排列简称为无重排列;如果牲质R是“在排列中允许元重复出 现”,则这种R-排列简称为可重排列.全部R-排列的个数叫做 R-排列数。若!4|为有限数,则称A的无重|A|-排列为A的全 排列 定义1.22集d的一个组合是A中元的一个无序选出.若 Q是对组合的限制条件,则这样的组合叫Q组合;如果Q的叙述 较长,又写为“组合,具有性质Q”,特别地,如果性质Q是“组合中 元的个数为r”,则这种Q组合简称为r-组合.如果性质9是“在 组合中不允许任何元重复出现”,则这种Q组合简称为无重组合; 如果性质Q是“在组合中允许元重复出现”,则这种Q组合简称为 可重组合.全部Q组合的个数叫做Q-组合数 例如,设集 那么,d的2-可重排列共有九个: aa,40,4c 3 g 3 2 2-无重排列共有六个: ba. bc.cat 2可重组合共有六个: b CC3 403 4c. c 2一无重组合共有三个: ab, ac, bc 若|A!=n,那末,在讨论排列数和组合数时,不失一般,可 设A为[1,n1.今后常用下列符号: P:集A的r-无重排列全体所组成的集, Pre Pri C":集A的r无重组合全体所组成的集 Cr ae iCr; UP;集A的r-可重排列全体所组成的集, 7