研究生组合数学复习要点.ppt
1组合数学复习要点组合数学复习要点一、排列组合一、排列组合1. 排列和组合的基本性质排列和组合的基本性质2. 排列组合的计数公式，多重集的排列数和组合排列组合的计数公式，多重集的排列数和组合 数的求法数的求法3. 应用应用2二、母函数二、母函数1. 母函数与数列的关系母函数与数列的关系2. 母函数与排列数、组合数的关系母函数与排列数、组合数的关系3. 用普通型母函数解决多重集的组合问题用普通型母函数解决多重集的组合问题4. 用指数型母函数解决多重集的排列问题用指数型母函数解决多重集的排列问题5. 用母函数解递推关系式用母函数解递推关系式6. 不定方程的整数解的个数与多重集的组合数之不定方程的整数解的个数与多重集的组合数之 关系关系3三、递推关系三、递推关系1. 常系数线性递推关系的解法（特征根法）常系数线性递推关系的解法（特征根法）2. 用待定系数法求常系数线性非齐次递推关系的用待定系数法求常系数线性非齐次递推关系的 特解特解(前两种类型前两种类型)3.列递推关系解应用题列递推关系解应用题4. 一般递推关系的线性化一般递推关系的线性化5. Fibonacci数列及其模型数列及其模型6. 第二类第二类Stirling数的组合意义数的组合意义7. Catalan数列及其解法数列及其解法4四、容斥原理四、容斥原理1. 容斥原理的基本形式容斥原理的基本形式(容斥原理、逐步淘汰原理容斥原理、逐步淘汰原理)2. 容斥原理的应用容斥原理的应用(比如解决多重集排列组合问题比如解决多重集排列组合问题)3. 有限制条件的排列有限制条件的排列(比如错排问题、相邻禁位排比如错排问题、相邻禁位排 列问题、保位问题列问题、保位问题)5五、抽屉原理五、抽屉原理1. 抽屉原理的几种基本形式抽屉原理的几种基本形式2. 抽屉原理的简单应用抽屉原理的简单应用6六、波利亚六、波利亚(Plya)定理定理1.1.置换在研究等价类计数中的作用置换在研究等价类计数中的作用2.2.将置换表为轮换之积将置换表为轮换之积3.3.Burnside引理计数公式引理计数公式4. Plya定理计数公式定理计数公式5.5.Plya定理的应用定理的应用7 1、一位学者要在一周内安排、一位学者要在一周内安排50个小时的工作个小时的工作时间，而且每天至少工作时间，而且每天至少工作5小时，问共有多少种安小时，问共有多少种安排方案？排方案？127 50 5,1,2,7ixxxxi 解解 问问题题相相当当于于不不定定方方程程 (7151,15)(21,6)CC 解解得得12715 0,1,2,7ixxxxi 即即练习题练习题8 2、n个男个男n个女排成一男女相间的队伍，试问有个女排成一男女相间的队伍，试问有多少种不同的方案多少种不同的方案.若围成一圆桌坐下，又有多少种若围成一圆桌坐下，又有多少种不同的方案？不同的方案？2 1!,!,2 ( !).nnn 解解 （ ）男男士士有有种种排排法法 女女士士也也有有种种排排法法 男男女女相相间间又又分分男男在在前前或或女女在在前前两两种种, ,所所以以共共有有种种(2)(1)!,!,(1)!( !).nnnnnnn 先先安安排排男男士士，有有种种 然然后后在在这这 位位男男士士所所形形成成的的 个个间间隔隔中中安安排排 位位女女士士, ,有有种种 所所以以共共有有种种9 .1nrrnnnr)+ rnrrnr 证证 先先将将每每个个盒盒子子放放一一个个球球，问问题题变变为为将将剩剩余余的的个个相相同同的的球球放放到到 个个不不同同的的盒盒子子里里，其其放放球球方方案案数数为为1111(-1(-1 3-1.-1nrnnrr 、 个个完完全全一一样样的的球球，放放到到 个个有有标标志志的的盒盒子子，要要求求无无一一空空盒盒，试试证证其其方方案案数数为为10 4 (2)1(2), ?m mn n、 用用种种颜颜色色去去涂涂棋棋盘盘 每每个个方方格格涂涂一一种种颜颜色色 使使得得相相邻邻方方格格颜颜色色相相异异的的涂涂色色方方案案有有多多少少11,1.(1).nmmnmm m 解解 第第一一个个方方格格可可涂涂 种种颜颜色色之之一一，有有 种种涂涂色色方方法法；为为使使相相邻邻方方格格颜颜色色相相异异，只只须须使使其其余余个个方方格格的的颜颜色色异异于于它它左左边边相相邻邻的的那那个个方方格格的的颜颜色色 于于是是其其余余的的每每个个方方格格都都有有种种涂涂法法 故故所所求求的的涂涂色色方方案案有有种种11(2)1(2),?m mn n用用种种颜颜色色去去涂涂棋棋盘盘 每每个个方方格格涂涂一一种种颜颜色色，使使得得相相邻邻方方格格颜颜色色相相首首末末两两格格也也异异，的的涂涂色色若若题题目目改改方方案案色色成成：有有多多少少异异nh2(1).hm m 解解 用用表示所求方法数表示所求方法数.易知易知使得相邻格子异色的涂色方法数有使得相邻格子异色的涂色方法数有其中使得首末两格同色的涂色方法有其中使得首末两格同色的涂色方法有所以所以用用m种颜色去涂种颜色去涂1 ()n nm棋盘棋盘,每格涂一种颜色每格涂一种颜色,1(1)nm m 种种,1nh 种种,11(1) (2)nnnhm mhn 从而从而1212(1)(1)( 1)(1)( 1) (1)nnnnmmmm 111222(1)(1)(1)( 1)nnnnnnhm mhm mm mh 123222(1)(1)( 1)(1)( 1)nnnnm mm mm mh 12322(1)(1)( 1)(1)( 1)(1)nnnnm mm mm mm m 2332(1)(1)(1)( 1)(1)( 1)nnnnm mmmm 12(1)( 1)(1)(1)1nnmm mm 另一解法参见教材另一解法参见教材P87例例3.5.7135(2)(),()n nmnmk mnk 、安安排排女女人人和和 个个男男人人围围圆圆桌桌而而坐坐个个座座位位已已编编号号 使使得得任任何何两两个个女女人人之之间间至至少少有有个个男男人人，求求不不同同的的安安排排座座位位方方法法数数. .解解 (1) 先任意选定一个女人入座，有先任意选定一个女人入座，有nm 种方法；种方法； (2) 再安排其他女人入座，使得任何两个女人再安排其他女人入座，使得任何两个女人之间至少有之间至少有k个空座位：个空座位：1211,(1,2,1)niiinna aanaainxaax 用用表表示示 个个女女人人的的一一种种坐坐法法，并并设设与与之之间间有有 个个空空座座位位，与与之之间间有有个个空空座座位位，则则1412(1,2, )nixxxmxk in 此不定方程的解的个数为此不定方程的解的个数为()111nmnknmnkmnkn 于是完成此步骤的方法有于是完成此步骤的方法有1(1)!1nmnknn 种种.15(3) 最后安排最后安排m个男人入座，有个男人入座，有m!种方法种方法.由乘法原理，所求的安排座位方法数为由乘法原理，所求的安排座位方法数为1()!(1)!1nmnknmmnn 16 6 6、某学者每周工作、某学者每周工作6 6天天, ,共共4242小时小时, ,每天工作每天工作的小时数是整数的小时数是整数, ,且每天工作时间不少于且每天工作时间不少于6 6小时也小时也不多于不多于8 8小时小时, ,如果编排一周的工作时间表如果编排一周的工作时间表, ,问有多问有多少种不同的方案？少种不同的方案？,nnaa解解 设设有有种种不不同同的的编编排排方方法法 则则相相应应的的母母函函数数为为6786( )()G xxxx3626( )(1)G xxxx36366(1) (1)xxx 363606(1615)() kkxxxxk1736394205(615)5kkkxxxx 42565350615555a 42x所所以以的的系系数数11861555 141 4623361518 7、将充分多的苹果、香蕉、橘子和梨进行装袋，、将充分多的苹果、香蕉、橘子和梨进行装袋，要求每袋中苹果数是偶数，香蕉数是要求每袋中苹果数是偶数，香蕉数是5 5的倍数，橘子的倍数，橘子最多最多4 4个，而梨的个数为个，而梨的个数为0 0或或1 1。如果每袋装。如果每袋装n个水果，个水果，求装袋的种类数。求装袋的种类数。 24510234( )(1)(1)(1)(1)naG xxxxxxxxxx解解 所所求求种种类类数数 的的母母函函数数为为52521111(1)111(1)xxxxxx 19001(1)nnnnnxnxn 1.nan 所所以以20 8、由字母、由字母a，b，c，d，e组成的总字母数为组成的总字母数为n的的单词中，要求单词中，要求a与与b的个数之和为偶数，问这样的单的个数之和为偶数，问这样的单词有多少个？词有多少个？ 解解 设满足条件的单词个数为设满足条件的单词个数为an ，这样的单词只，这样的单词只有两类：一类包括偶数个有两类：一类包括偶数个a与偶数个与偶数个b；另一类包括；另一类包括奇数个奇数个a与奇数个与奇数个b. 因此因此an 对应的母函数为对应的母函数为 2422335223( )(1) (1)2!4!2!() (1)3!5!2!exxxGxxxxxxx212323()()22xxxxxxeeeeee51()2xxee 001(5)2!nnnnnxxnn051()2!nnnxn 512nna 故故22 9、把、把2n件相异物品放到件相异物品放到m个不同的盒中，使个不同的盒中，使得每个盒子中的物品件数均为偶数得每个盒子中的物品件数均为偶数(零也是偶数零也是偶数)，求不同的放法种数求不同的放法种数.解解 相应的指母函数是相应的指母函数是24( )(1)()2!4!2xxmmexxeeGx 22011(1)22mmxxmmxkxmmkmeeeek (2)012mk m xmkmek 001(2)!2jmjmkjmxkmkj 23001(2)!2jmjmjkmxkmkj 故所求放法数为故所求放法数为 201(2)2mnmkmkmk 2410、由数字、由数字1至至9组成的每种数字至少出现组成的每种数字至少出现1次的次的 (9)n n 位数有多少个？位数有多少个？ 解解 设所求的数为设所求的数为 ,na则则 的指母函数为的指母函数为 na2399( )()(1)2!3!xexxGxxe9(9)09( 1)kk xkek 9009( 1)(9)!nknknxkkn 259009( 1)(9)!nknnkxkkn 所以所以 (此题也可用容斥原理做此题也可用容斥原理做) 909( 1)(9)knnkakk 26 11、求由、求由0、1、2组成的长为组成的长为n的三进制串的个数的三进制串的个数,但其中的但其中的0和和1不相邻不相邻(即即01和和10从不出现从不出现) 解解 设所求三进制串的个数为设所求三进制串的个数为na ，则则 123,7aa ，3n 时时，(1)若首位是若首位是2,则此类三进制串有则此类三进制串有-1na个个；(2)(2)若首位是若首位是1,1,则第二位必是则第二位必是1 1或或2.2.若第二位是若第二位是2,则此类串有则此类串有-2na个个；若前二位是若前二位是1,则第三位必是则第三位必是1或或2. 若第三位是若第三位是2,则此类串有则此类串有-3na个个；27；若前；若前n- -2位是位是1,则第则第n- -1位必是位必是1或或2.若第若第n- -1位必是位必是2，则，则此类串有此类串有1a 个个；若前若前n-1位是位是1,则第则第n位必是位必是1或或2，则此类串有，则此类串有2个个.所以首位是所以首位是1的三进制串有的三进制串有23212nnaaaa 个个.(3)若首位是若首位是0,同理可得三进制串有同理可得三进制串有23212nnaaaa 个个.因此因此, 得得28 123212(2)nnnnaaaaaa 1234212(2)nnnnaaaaaa 两式相减，得定解问题两式相减，得定解问题 12122(3)3,7nnnaaanaa 求得通解求得通解12(12)(12)n
