组合数学复习要点

1、2021/8/61复习要点复习要点一、排列组合一、排列组合1.1.排列和组合的基本性质排列和组合的基本性质2.2.基本的组合等式及其证明，用组合意义法证明基本的组合等式及其证明，用组合意义法证明 组合等式组合等式3.3.排列组合的计数公式，多重集的排列数和组合排列组合的计数公式，多重集的排列数和组合 数的求法数的求法4.4.多项式系数及其求法多项式系数及其求法5.5.应用应用2021/8/62二、母函数二、母函数1. 母函数与数列的关系母函数与数列的关系2. 母函数的基本性质母函数的基本性质3. 母函数与排列数、组合数的关系母函数与排列数、组合数的关系4. 用母函数解决多重集的排列和组合问题用

2、母函数解决多重集的排列和组合问题5. 正整数的分拆的应用正整数的分拆的应用6. 正整数的分拆数、不定方程的（正、非负）整正整数的分拆数、不定方程的（正、非负）整 数解的个数、多重集的组合数之关系数解的个数、多重集的组合数之关系2021/8/63三、递推关系三、递推关系1.1.常系数线性递推关系的解法（特征根法）常系数线性递推关系的解法（特征根法）2.2.用待定系数法求常系数线性非齐次递推关系的用待定系数法求常系数线性非齐次递推关系的 特解特解( (三种类型三种类型) )3.3.一般递推关系的线性化一般递推关系的线性化4.Fibonacci4.Fibonacci数列及其模型数列及其模型5.Sti

3、rling5.Stirling数列的组合意义数列的组合意义6.6.根据具体问题建立递推关系并求解根据具体问题建立递推关系并求解2021/8/64四、容斥原理四、容斥原理1.1.容斥原理的基本形式（容斥原理、逐步淘汰原容斥原理的基本形式（容斥原理、逐步淘汰原 理）理）2.2.容斥原理的应用（比如在排列组合、初等数论容斥原理的应用（比如在排列组合、初等数论 等方面）等方面）3.3.有限制条件的排列（比如错排问题、相邻禁位有限制条件的排列（比如错排问题、相邻禁位 排列问题、保位问题）排列问题、保位问题）4.4.有禁区的排列有禁区的排列2021/8/65五、抽屉原理和五、抽屉原理和RamseyRams

4、ey问题问题1.1.抽屉原理的几种基本形式抽屉原理的几种基本形式2.2.抽屉原理的应用抽屉原理的应用3.3.完全图的染色问题完全图的染色问题4.4.Ramsey问题基本概念问题基本概念5. 几个基本的几个基本的Ramsey数数2021/8/66六、波利亚六、波利亚(Plya)定理定理1.1.置换在研究等价类计数中的作用置换在研究等价类计数中的作用2.2.将置换表为轮换之积将置换表为轮换之积3.Burnside3.Burnside引理计数公式引理计数公式4. Plya定理计数公式定理计数公式5.5.Plya定理的应用定理的应用2021/8/671212(09,1,2, ) 1 ,. , ninn

5、Aa aaainnaaaAn 设设是是一一个个位位数数 如如果果则则称称 是是一一个个数数字字具具有有非非降降顺顺序序的的 位位数数 求求小小于于1 10 0 且且其其数数字字具具有有非非降降顺顺序序的的正正整整数数 例例的的个个数数 12121 10, 101010nnnnnAAA = aaaa 解解 设设 是是任任一一个个小小于于且且数数字字具具有有非非降降顺顺序序的的正正整整数数 则则 可可表表成成1212,09nna aaaaa 其其中中是是不不全全为为零零的的非非负负整整数数, ,且且 ,100,1,2,9n因因此此 所所求求正正整整数数个个数数等等于于元元集集的的 可可2021/8

6、/68即为即为1019 11.nnnn 1,重重组组合合数数减减去去2 2,2. nn 证证明明: :在在任任意意给给出出的的个个正正整整数数中中 必必有有两两个个数数 它它们们的的差差或或它它们们的的和和能能 例例被被 整整除除 2,An 证证 设设 是是所所给给的的个个正正整整数数之之集集 则则|(2 ) (2 )(2) 0,1,2,iAxA xn qixn pniin 令令或或012nA = AAAA则则 |2,An2021/8/69,|2.kkAA 由由抽抽屉屉原原理理 必必存存在在使使得得2 .n或或者者余余数数之之和和为为,2,(2 ), (2 )ka bAa bnan prbn

7、qr 设设若若分分别别除除以以所所得得的的余余数数相相同同 即即 2 (), 2 |.abn pqn ab 则则 所所以以 ,2,(2 ), (2 )(2)a bnnan prbn qnr若分别除以所得的余数之和为2即若分别除以所得的余数之和为2即 2 (1), 2 |.abn pqn ab则 所以 则 所以 2,iAn且且中中任任两两个个数数分分别别除除以以所所得得的的余余数数或或者者相相同同2021/8/61036,1,2,3, 36 36把把一一个个圆圆盘盘分分成成个个相相等等的的扇扇形形 然然后后把把这这些些数数任任意意填填入入个个扇扇形形中中, ,证证明明存存在在三三个个连连续续的的

8、扇扇形形, ,其其中中的的数数字字之之和和至至少少 例例是是5 56 6. .(1,2,36)im i 证证 用用表表示示该该圆圆盘盘上上三三个个连连续续扇扇形形上上的的数数字字之之和和, ,这这样样的的数数共共有有3 36 6个个. .注注意意到到12,m m1 1, ,2 2, , ,3 36 6这这些些数数中中的的每每个个数数都都在在作作和和数数36m 时时出出现现了了三三次次, ,故有故有361 3(1236)1998iim 2021/8/611, 56.iimm 即即存存在在某某个个使使199836,问问题题归归结结为为: :把把件件物物品品放放入入个个抽抽屉屉里里,)im由由抽抽屉

9、屉原原理理知知 至至少少有有一一个个抽抽屉屉( (即即某某个个放放有有不少于不少于1998 15515636 , 件物品件物品2021/8/612(2 !)(3 !).23 24nnnnn 用用组组合合方方法法证证明明和和都都是是整整数数例例1(21)nnana 于于是是有有 122,1.nnnaa 证证 考考虑虑将将个个球球放放到到 个个相相同同的的盒盒子子里里, ,每每个个盒盒子子 个个球球. .设设方方法法数数为为显显然然2,nx 当当时时 取取定定一一个个球球, ,记记为为 . . 2n在在剩剩余余的的-1-1个个 2xn球球中中任任选选一一个个与与放放在在同同一一盒盒子子里里, ,有

10、有- -1 1种种选选法法. .122nnna 其其余余个个球球放放在在 - -1 1个个盒盒子子里里, ,有有种种放放法法. .12(21)(21)(23)nnnananna 3(21)(23)(25)nnnna 2021/8/6131(21)(23)(25)5 3nnna(21)(23)(25)5 3 1nnn (2 )!(2 )(22)(24)6 4 2nnnn (2 )! (2)2!nnnn (2 )!(2 )!,.2!2nnnnnan 因因是是整整数数 故故是是整整数数1.n 上上式式对对也也成成立立2021/8/61422,2(2 )!(2 )!.2(2!)nnnnnn 另另解解

11、考考虑虑把把个个不不同同身身高高的的人人编编排排成成阵阵列列使使得得每每一一列列的的 人人的的身身高高由由大大到到小小, ,则则编编排排方方案案数数为为22,()!.( !)nnnnnnn 一一般般地地, ,考考虑虑把把个个不不同同身身高高的的人人编编排排成成阵阵列列 使使得得每每一一列列的的 个个人人的的身身高高由由大大到到小小, ,则则编编排排方方案案数数为为33,3(3 )!(3 )!.23(3!)nnnnnnn 同同样样 考考虑虑把把个个不不同同身身高高的的人人编编排排成成阵阵列列使使得得每每一一列列的的 人人的的身身高高由由大大到到小小, ,则则编编排排方方案案数数为为2021/8/

12、61512 , (1)2 ( 2)5 2nnnnnaaanann 球球面面上上有有 个个大大圆圆 其其中中任任何何两两个个都都相相交交于于两两点点 但但没没有有三三个个大大圆圆通通过过同同一一点点. .用用表表示示这这些些大大圆圆所所形形成成的的区区域域数数, ,证证明明: : 例例12,2,4.aa 证证 ( (1 1) )易易知知2,1nnA 当当时时 去去掉掉所所给给个个圆圆中中的的一一个个圆圆 , ,则则nna剩剩下下的的 个个圆圆把把平平面面分分成成个个区区域域. .A现现把把圆圆 放放回回原原 2Ann处处, ,则则 与与其其余余 个个圆圆都都相相交交, ,且且所所得得的的个个交交

13、点点互互异异( (因因无无三三个个圆圆共共点点) ), ,22nAn这这个个交交点点把把圆圆 分分成成段段2021/8/61612nnaan 弧弧. .每每段段弧弧把把原原来来的的一一个个区区域域分分成成两两个个小小区区域域. .故故2An把把圆圆 放放回回原原处处后后增增加加了了个个区区域域. .从从而而1(2) 2(1)nnaan 22(2)2(1)nann 12 12 22(2)2(1)ann 22 12 22(2)2(1)nn 2(1)n n 22nn 12.nn 上上式式当当和和时时仍仍成成立立2021/8/617 例例6 6 从从n双不同的鞋中取出双不同的鞋中取出2 2r(2(2r

14、 n) )只鞋只鞋, ,使使得其中恰有得其中恰有k( (k r) )双成对的鞋双成对的鞋. .问有多少种不同的问有多少种不同的取法？（取法？（鞋分左右鞋分左右）nnkk 解解 先先从从 双双鞋鞋中中选选出出 双双成成对对的的鞋鞋, ,有有种种22,nkrk再再从从其其余余的的双双鞋鞋中中选选定定双双鞋鞋 有有22nkrk 种种选选法法. .方方法法22,rk 最最后后从从选选定定的的双双鞋鞋中中 每每双双22,2rk 取取出出一一只只 有有种种选选法法. .故故所所求求取取法法数数为为22222rknnkkrk 2021/8/618 例例7 7 某学者每周工作某学者每周工作6 6天天, ,共共

15、4242小时小时, ,每天工每天工作的小时数是整数作的小时数是整数, ,且每天工作时间不少于且每天工作时间不少于6 6小时小时也不多于也不多于8 8小时小时, ,如果编排一周的工作时间表如果编排一周的工作时间表, ,问问有多少种不同的方案？有多少种不同的方案？,nnaa解解 设设有有种种不不同同的的编编排排方方法法 则则 相相应应的的母母函函数数为为6786( )()G xxxx 3626( )(1)G xxxx 36366(1) (1)xxx 363606(1615)kkxxxxk 2021/8/61936394205(615)5kkkxxxx 565350615555na nx所所以以的的系系数数