组合数学课件第二章母函数与递推关系习题解答.ppt

1、2023-5-12组合数学1.题目解：,1-nn 1n ,nn 0n nn 1n 0n 2n2n 12n 02n )1()1()1(222nnnnnxxxxxxx比较n次方系数即可证。2023-5-12组合数学2.题目解：10001008410010084100841)()(1)1(kkkkxxCxxxx分析 的结构可知仅当时有 项kxx)(845,4,3k20 x233100 3CCk系数时，344100 4CCk系数时，055100 5CCk系数时，三个系数相加即为所求2023-5-12组合数学3.题目解：用指数型母函数，可得母函数33242)1()1()(xxxxxxG系数即为所求。10

2、 x2023-5-12组合数学4.题目解：A、B、C、D组成的全排列数为xexxP442 )!2!11(出现A后，其后续字母必为A、B、C、D中的一个，其概率相等。xxxeeexxxP41543323 !2)43(431)!11(2023-5-12组合数学AB至少出现一次的排列为 04154!)415(4 nnnnxxxneePPP排列数为nnna)415(4 2023-5-12组合数学5.题目解：对符合题设要求的排列如果0可以出现在最高位，则可得母函数：!)1224(41 )12(41 )(21 )!4!21()!21()(0242224222nxeeeeexxxxxGnnnnxxxxx20

3、23-5-12组合数学但是对n位四进制数来说最高位不能为0。)1224(41nnna)243(41)1224()1224(411111nnnnnnnnnaaa2023-5-12组合数学6.题目解：参见第四题解答前半部分。2023-5-12组合数学7.题目解：题设中序列的母函数为：00!)1()1)(),(),(),1(),()(kkkkkxnknknkxnknCxnknCxnnCnnCxG由$4性质3得，上式1)1(1nx2023-5-12组合数学8.题目解：等式的右端相当于从n+m+1个球中取n+1个球的组合。把这n+m+1个球编号，如果取出的n+1个球中最小编号是一，则得到 如果最小编号是

4、二则得到 如果最小编号是m则得到 。可证),(nmnC),1(nmnC),(nnC2023-5-12组合数学9.题目解：由推导过程知61)(ln(631211 )31211(1)(ln(222222xxxGxxxG2023-5-12组合数学nxnxxxnxxpxnpxGnn61 1ln61ln 1lnln)(ln(22令xnxxy1ln6122023-5-12组合数学求导得2226)1(1xnxy令即0 y06)1(1222xnx解得166 ),1,0(6621nnxnnx2023-5-12组合数学将 代入 得1xyny32nnep322023-5-12组合数学10.题目解：把单位看成元素，共

5、12个元素其中 第1单位有3个第2单位有4个第3单位有5个则命题可看成从12个元素中取8个的组合。母函数为：)1()1()1()(543243232xxxxxxxxxxxxxG2023-5-12组合数学其中 项系数为所求8x2023-5-12组合数学11.题目解：用归纳法可证明：1）当k=1时命题成立2）设当k=N时命题成立 即N可唯一表示成不同且不相邻的F数之和。则当k=N+1时，明显可以分成N的序列再加上1（），但这可能会不能满足“不同且不相邻”的条件。下面予以讨论2F2023-5-12组合数学先讨论相邻的 ，明显若有 ，则可用 代替。以此类推可解决相邻问题。再讨论相同 ，可把超过1个的分

6、解为 再用结决相邻问题的方法即可解决 命题得证iFiF1iF2iFiFiF1iF2iF2023-5-12组合数学12.题目解：设n个满足条件的平面把空间分成 个域n-1个满足条件的平面把空间分成 个域则第n个平面与这n-1个平面有n-1条交线，且这些两两相交，任三线不共点。第n个平面被这n-1条线分成 个域 增加了 个域。可得na1na21nC21nC1 ,2 ,10121aaCaannn2023-5-12组合数学设323210nAnAnAAan解得11113210AAAA321nnnan2023-5-12组合数学13.题目解：当n位二进制数最高位为1时最高位为0时，次高位必为11nnhh2n

7、nhh21nnnhhh即 是F数列nh2)251(51nh2023-5-12组合数学14.题目解：设n为偶数1）先把n-1个盘通过C移到B2）把第n个盘移到C3）把n-3个盘通过C移到A4）把第n-2个盘移到B对n为奇数时上述四步仍然成立，但是B、C对调。)3(1)3(1)1()(nknhnhnk其中2)0(,2)2(,1)1(kkk)(kh为Hanota数列。2023-5-12组合数学15.题目解：这是一个错排问题把某种排列状态看成暂时状态则1)1()1(1mnmnDmDN2023-5-12组合数学16.题目解：把AD看成1则AB为251ADABBBADADABABABBB251215121

8、5 1112023-5-12组合数学ABCDCBCB11同理可得其他矩形相似2023-5-12组合数学满足条件的n条直线把平面分成 个域，其中n-1条直线分割成的域数为 ，第n条直线与这n条直线均相交。被分成n-1+1=n段。增加的域数为n。17.题目解：na1na2,1 ,101aanaann2023-5-12组合数学211112210210nnaAAAnAnAAann设解得2023-5-12组合数学18.题目解：n-1个点把圆分为 部分，加上第n个点则增加了n-1条弦增加第1条弦，被其他弦分成0段增加第2条弦，被其他弦分成1x(n-2-1)段增加第n-2条弦，被其他弦分成(n-3)(n-2

9、-n+3)段增加第n-1条弦，被其他弦分成0段nnaann311na2023-5-12组合数学19.题目解：设n-1位不出现11的个数为n-2位不出现11的个数为n位不出现11的个数为则na2na1na3,2,1 ,02102121aaaaaaaaannnnnn即特征方程为251 ,25101212xxxx2023-5-12组合数学设代入得nnBxAx211053510535BAnnna)251(10535)251(105352023-5-12组合数学20.题目解：设所求为则na21)1()1(nnnanana2023-5-12组合数学21.题目解：411)1(nSSSnnn是n的4次方 满足

10、第推关系1nS061520156654321nnnnnnnSSSSSSS设5432154321nAnAnAnAnASn2023-5-12组合数学代入可解得52446035021511246050151 54321nnnnAnSAAAAAn2023-5-12组合数学22.题目解：由矩阵的结构知nnnK2032011只要求出K即可1)1(,2)1(3)(1KnKnKn2023-5-12组合数学24.题目解：当r是奇数（1）时1221raaarrr当r是偶数时21)1(21raraarrr4)6(4)3)(1(nnnnan2023-5-12组合数学25.题目解：I 当n是偶数时 对所有符合条件的 来说，每边增加1各单位，则可构成符合条件的 。设短边为a、b，长边为c，则(a+b)-c=2即a+b-2c-1，对所有符合条件的 来说，每边减少1各单位，则可构成符合条件的 。3rraa3rarara3ra3rraa3rraa2023-5-12组合数学II 当n为奇数时 由I的讨论知，比 多了a+b-c=1的三角形。而这种三角形可知3rara21nba当 能被2整除时，这种三角形有 个21n21n当 不能被2整除时，这种三角形有 个21n21n2023-5-12组合数学4)1(213nnnnaa(2)8)1()1(8)1(211213nnnnnnnaa