组合数学答案合集.pdf

第五章习题答案 6.在在(3x-2y)18的展开式中，的展开式中，X5Y13的系数是什么？的系数是什么？X8Y9的系数是的系数是 什么？(后一问并非排印的错误) 解答： 1355 18 )2(3c ；0； 9.计算和计算和? ? ? ? 的值。的值。 解答： nnkk n k n k c9)1(10)1(10)-(1 0 n 16.通过积分二项式的表达式，证明对整数通过积分二项式的表达式，证明对整数 n 有有 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 解答： n k kk n n xcx 0 )1( 两边同时在（0，1）上求定积分得： 1 0 0 1 0 )1( n k kk n n xcdxx 等 式 左 边 积 分 后 为 1 12 1 n n , 右 边 为1+ n nnn c n cc 1 1 3 1 2 1 21 20.求整数求整数 a,b,c,使得对所有的使得对所有的 m ? ? ? ? ? ? ? ? ? ? ? 然后求级数然后求级数 13+23+33+ +n3的和。的和。 解:cmmm b mmm a m)1( 2 )2()1( 6 3 利用系数相等得： 1 6 6 c b a 13 1 1233 666 mmmmm cccccm 11 2 1 1 3 1 3 4 3 3 333 621 nn ccccccn 4 )1( 6 22 2 1 4 2 nn cc nn 25.应用组合学论证方法， 证明二项式系数的应用组合学论证方法， 证明二项式系数的Vandermonde卷积： 对所有的正整数 卷积： 对所有的正整数 m1,，m2，和，和 n，? ? ? ? ? ? ? ? ? ? ? ? ?作为 特殊情形，推导恒等式 作为 特殊情形，推导恒等式? ? ? ? ? ? ? ? ? ? ? ? . 解答： 等式右边表示从 21 mm 中选出 n 个元素， 共有 n mm c 21 中选法。两外一种解释是：将 21 mm 分成两类.一类含有 1 m个元素，另一种含 2 m个，则整个选取的过程分两步， 第一步从第一类中选 k 个，然后从第二类中选取(n-k)个其中 （nk2.1.0 ） 41.在在(x1-x2+2x3-2x4)9的展开式中的展开式中 x13x23x3x42的系数是什么？的系数是什么？ 22 2 1 3 33 6 3 9 )2(2)1(cccc 第七章第七章 递推关系和生成函数递推关系和生成函数 4、证明斐波那契序列是递推关系 54 35 += nnn aaa )5( n 的解，其中， . 3 , 2, 1, 1, 0 43210 =aaaaa n 然后利用这个公式证明斐波那契序列满足条件： 可被 5 整除当且仅当可被 5 整除。 n f 解：根据斐波那契序列的定义，1, 0 10 =ff 545454 4544343221 3524 222 +=+= +=+=+= nnnnnn nnnnnnnnnnn ffffff fffffffffff 由题意可知斐波那契序列满足递推关系 54 35 += nnn aaa 所以斐波那契序列是此递推关系的解。 下面来证明可被 5 整除当且仅当n可被 5 整除。 n f n f可被 5 整除等价于可被 5 整除，由递推关系可知，又等价于可被 5 整除， n a 5n a 易知，当时，可被 5 整除，所以很显然和n可被 5 整除也是等价的。 ?10, 5=n n a 8、考虑一行 n 列棋盘。假设用红和蓝两种颜色之一位棋盘的每一个方格着色。令是使得没有两 个被涂成红色的方格相邻的着色方法数。求出并验证所满足的递推关系。然后得出的公式。 n h n h n h 解：当第一列是蓝色时，有种着色方法， 1n h 当第一列是红色时，第二列为蓝色，有种着色方法， 2n h 所以满足递推关系 n h 21 += nnn hhh )2( n 特征方程为 01 2 = xx 特征方程的根是 2 51 , 2 51 21 = + =qq 一般解为 nn n cch) 2 51 () 2 51 ( 21 + + = 为确定，我们来求，使得初始值满足 n h 21 cc 和2, 1 10 =hh 这导致了下面的方程组 2) 2 51 () 2 51 (, 1 1, 0 21 21 = + + = =+= ccn ccn 因此 52 53 , 52 53 21 + = + =cc nn n h) 2 51 ( 52 53 ) 2 51 ( 52 53+ + + = 01223 3 (1) 12 3 (1)( 2 ) 16.1,0,032(3). 320 1 (1)(1) -2 (2) nnn nn n n n nnn hhhhhhn xx HCC n HC hHHC = += =+ = =+= （ 2） 求 解 初 始 值递 推 关 系 解 ： 这 个 递 推 关 系 的 特 征 方 程 为 ： 它 的 三 个 根 是， 1， -2 于 是 ， 部 分 一 般 解 对 应 于 根 1的 是 ： 而 一 般 解 对 应 于 根的 部 分 ： 一 般 解 123 123 13 123 123 12 (2) , (0) 1 (1) 20 (2) 240 8 9 n C nC CCC nCC nCCC nCCC CC + =+= =+= =+= = 下 面 要 确 定使 初 始 条 件 成 立 该 方 程 组 唯 一 解 是 ： 3 21 39 821 (2) 939 n n C hn = =+因 此 解 为 ： 234 22 5,12,29 50 102 18. nn nnn hhh n aaa n aa = + 的递推关系，然后求出 的公式 解：根据题意可知 当时，对于三进制串，第一个位置不为 ， 当第一个位置为 时，第二个位置为 或 ，对应的三进制串分别为种和种 当第一个位置为2时，第二个位置为0，1或2，此 确定长为 ，不包含两个相连的0或相连的1的三进制串（即由一些0、1、2组成 的串）的个数 3 12 123 323 123 123 1 35 31 0 -11+ 21- 2 ( 1)(12)(12) , 2 ( nn nnnnn nnn n aa aaaaa xxx aCCC C C C nC + =+ = =+ = 时三进制串有种 于是 满足递推关系 （n） 它的特征方程为 计算可知此特征方程的三个根是 ， 因此一般解为 下面要确定使出事条件成立 222 23 333 123 444 123 123 1)(12)(12)5 3 ( 1)(12)(12)12 4 ( 1)(12)(12)29 2222 0, 44 2222 (12)(12) 44 nn n CC nCCC nCCC CCC a += =+= =+= + = + =+ 经计算可得 所以 23、求解非齐次递推关系 n nn hh234 1 += ) 1( n 1 0 =h 解解 对应的齐次递推关系为，它的特征方程为 1 4 = nn hh04 =x n pp42 = ，有一个特征根，一般解为 。设非齐次递推关系的特解为，则，求得 4=q n n ch4= n n ph2= nn 232 1 + 3=p，则 。由初始条件 n 23 n n ch4 +=1 0 =h，得出1=c。故为原问题的解。 n 2 n n h34 += 26、求解非齐次递推关系 nhhh nnn 296 21 += )2( n 1 0 =h 0 1= h 解解 对应的齐次递推关系为 21 96 = nnn hhh n nc3 2 ，它的特征方程为，3 是二重特征根， 一 般 解 为。 设 非 齐 次 递 推 关 系 的 特 解 为 096 2 =+ xx h n n ch3 1 +=srn n +=， 则 nsnrsnrsrn2)2(9) 1(6+=+， 求得 2 1 =r， 2 3 =s， 则 2 3 2 33 21 += n ncch nn n 。 由初始条件，得出1 0 =h0 1= h 2 1 1 =c， 6 1 2 =c。故 2 3 22 3 2 3 += nn h nn n 为原问题的解。 1 12 , 11 10 Se ee 的倍数次。 或 次。 234 2 , 2 ee ee 组合数： 出现至多一次。 出现 012 29., i) ii) iii) iv)45 v) i) n n i ehh hh hSn e e e ?令。确定组合序列的生成函数，其中 为 具有如下附加限制的 每个 每个 元素 元素次，而元素，或 次。 每个 解： 每 ( ) 3 13 i i i 为多重集 出现奇数次。 出现 不出现，而 出现 ， 出现至少 35 24 )( 111 x x xxxx + + 引入一个因子，我们发现 35 24 )(xx xx + +? 3535 2424 2222 (1)() (1) (1) (1) (1) 1 i i e e g xxxxxxxxx xxxxxxxxx xxxx x =+ =+ = = ? ? 个 出现奇数次 对每个 ( ) 4 24 3633636 33 3 4 12 (1) ? (1)(1)(1) 111 1111 1 (1) ? i i x e e g xxxxxxx xxxx x ee =+ = = ? 每个 出现3的倍数次 对每个 引入一个因子，我们发现 元素 不出现，而 对每个 ( ) 6 33 )(1 1 xx+ 出现至多一次。 ( ) 2 31124311311 (1)(1)(1) 1 (1) iv)131145 ()()() i i i e g xxxx x x e g xxxxxxxxxx =+ + = =+ ? 引入一个因子，我们发现 元素 出现 ， 或次，而元素，或 次。 对每个 引入一个因子，我们发现 22 2 5 )(1 2 ) xx ee xxx + + 出现 ( ) 101112101112101112101112 1012101210121012 v)10 ()()()() (1)(1)(1)(1) i i e e g xxxxxxxxxxxxx xxxxxxxxxxxx =+ =+ ? ? 每个 出现至少次。 对每个 引入一个因子，我们发现 10101010 40 4 1111 (1) xxxx xxxx x x = = 30、通过用 7.5 节所描述的生成函数的方法求下列递推关系 ) 2 4 = nn hh1, 0);2( 10 =hhn ) 21 h += nnn hh3, 1);2( 10 =hhn ) 321 99h += nnnn hhh 3, 1, 0);3( 210 =hhhn ) 21 16h8 = nnn hh0, 1);2( 10 =hhn ) 32 2h3 = nnn hh 0, 0, 1);3( 210 =hhhn ) 4321 8465 += nnnnn hhhhh 2, 1, 1, 0);4( 3210 =hhhhn 解：) 该序列的生成函数 = = 0 )( n n nx hxg = = + = = 00 2 0 22 4)41 ()()41 ( nn n n n n n n n xhxhxhxxgx = += 2 210 )4( n n nn xhhxhh x= )21)(21 (41 )( 2 xx x x x xg + = = 2 )41 (4 1 )21 (4 1 xx + = = = += 00 2 4 1 )2( 4 1 n nn n nn xx() = = 0 2)2( 4 1 n nnn x 因此，() nn n h2)2( 4 1 = ) 该序列的生成函数 = = 0 )( n n nx hxg = = 0 22 )1 ()()1 ( n n nx hxxxgxx = += 2 21010 )()( n n nnn xhhhxhhh x21+= ) 2 51 )( 2 51 ( 21 1 21 )( 2 + + + + + = + = xx xx x xg ) 2 51 ( 1 ) 2 51 ( 1 + + + + + = xx = + + = 0 1 ) 2 51 () 2 51 ( n nnn x 因此， 11 ) 2 51 () 2 51 ( + + + = nn n h ) 该序列的生成函数 = = 0 )( n n nx hxg = +=+ 0 3232 )991 ()()991 ( n n nx hxxxxgxxx = += 3 1 2 012010 ()9()( n nn hhxhhhxhhh + 32 )99 n nn xhh 2 xx += )1)(31)(31 (991 )( 2 32 2 xxx xx xxx xx xg + + = + + = )1 (4 1 )31 (12 1 )31 (3 1 xxx + + + = = = 0 ) 4 1 12 )3( 3 3 ( n n nn x 因此， 4 1 12 )3( 3 3 = nn n h ) 该序列的生成函数 = = 0 )( n n nx hxg = +=+ 0 22 )1681 ()()1681 ( n n nx hxxxgxx 18 = x = += 2 21010 )168()8( n n nnn xhhhxhhh 22 ) 14( 18 1681 18 )( = + = x x xx x xg 14 2 ) 14( 1 2 + = xx = = 0 4) 1( n nn xn 因此， n n nh4) 1( = ) 该序列的生成函数 = = 0 )( n n nx hxg = +=+ 0 3232 )231 ()()231 ( n n nx hxxxgxx = += 3 32 2 0210 )23()3( n n nnn xhhhxhhxhh 2 31x= 2 2 32 2 ) 1)(12( 31 231 31 )( + = + = xx x xx x xg )21 (9 1 ) 1(3 2 2 x + ) 1(9 14 xx+ =+ = += 0 )2( 9 1 ) 1( 3 2 9 14 ( n nn xn n ) = 0 4) 8 n n hx + 01 )4 因此， n n nnh2( 9 1 3 2 9 8 )2( 9 1 ) 1( 3 2 9 14 =+= ) 该序列的生成函数 = = 0 )( n n nx hxg +=+ 32432 4651 ()()84651 ( n xxxxxgxxxx += 3 23 2 012010 65()65()5( n = + 4 4321 )8465( nnnnn xhhhhhhhxhhhxhhh 32 34xxx+= xhh ) 1()21 ( 34 84651 34 )( 3 32 432 32 + + = + + = xx xxx xxxx xxx xg ) 1(27 8 )21 (108 17 )21 (9 2 )21 (12 1 23 + + + + = xxxx = + ) 1 nn x + + + + = 0 1 ( 27 8 2 108 17 2 9 1 2 24 ) 1)(2( n nnn nnn 因此， nnn n nnn h2 108 17 2 9 1 2 24 ) 1)(2( 1 + n ) 1( 27 8 + + + = + 31、求解非齐次递推关系 n nn hh44 1+ = ) 1( n 3 0 =h 解法一 对应的齐次递推关系为 1 4 = nn hh，它的特征方程为04 =x，有一个特征根4=q，一般 解为。 设非齐次递推关系的特解为， 则， 求得 n pn4 nn n44) 1( 1 + n ppn44 =1=p， n n ch4= n h = 则。由初始条件 nn n nch44 +=3 0 =h，得出3=c =00 4 nx h = + 0 4 n 。故为原问题的解。 nn n nh443+= = = += 11 0 4 nn n nx hh = += 0 42 n nn x 解法二 该序列的生成函数 = = 0n n h = = nx h = + 1 4 n n x )( n xxg + = 1 0 )4( nn nn n n nx hx n nx h =1 ()()41xgx = + 1 0 4( n n hhh = 1) n n x= 0 n h= 3 nn x x41 1 2+= 2 )41 1 x = + 0 3( n n (41 2 41 41 1 2 )( xx x xg+ = + = = = += 00 4) 1(42 n nn n nn xnx=4) n xn 因此， n n nh4)3( += 36、确定 neeee+ 21 52+ 43 7 43, f e = 的非负整数解的个数的生成函数。 n h 解：令 432211 7,5,2efefef= n h也等于的非负整数解的个数，其中是偶数，是 5 的倍数，是 7 的 倍数。因此， nffff=+ 43211 f 2 f 4 f 7 5 1 x x + = 2 2 n 52 21042 11 1 1 1 1 1 )1)(1 ()( xxx xxxxxg = +=? 1473 1)(xxx+? )0 1)( +? n 37、令是由定义的序列(。确定该序列的生成函数。 ?, 21, 0n hhhhh 解 x x n n = = 1 1 0 两边求导数得到 0 1 ( 1 x nx n n = = 2 ) 两边再求导数得到 3 0 2 )1 ( 2 ) 1( x xnn n n = = 两边乘 2 2 x 得到 3 2 0 )1 (2 ) 1( x x x nn n n = = 因此，该序列的生成函数 3 2 000 )1 (2 ) 1( 2 )( x x x nn x n xhxg n n n n n n n = = = = = = 42、令 S 表示多重集 k eeee?, 321 1 。确定序列的指数生成函数， 其中并对有： ?, 210n hhhh , 1 0 =hn （1） 等于 S 的-排列数，其中每个物体出现奇数次。 n hn （2） 等于 S 的-排列数，其中每个物体出现至少 4 次。 ， n hn （3） 等于 S 的-排列数，其中至少出现一次，至少出现两次，至少出现次。 n hn 1 e 2 e k ek （4） 等于 S 的-排列数，其中至多出现一次，至多出现两次，至多出现次。 n hn 1 e 2 e k ek 解： （1）指数生成函数： k e xx xxg +=? ! 5! 3 )( 53 )( （2） k e xx xg +=? ! 5! 4 )( 54 )( （3） + + +=? ! 3! 2! 2 )( 322 )( k xxxx xxg k e （4）() + + += ! 2 1 ! 3! 2 1 ! 2 11)( 2322 )( k xxxxx xxxg k e ? 43、令表示用红，白，蓝和绿以下述方式给一行 n 列棋盘上的方格涂色的方法数：涂成红色方格 的数目为偶数， 涂成白色方格的数目为数。 确定 0 h指数生成函数， 然后找出 n h 简单公式。 n h ?, 21n hhh的的 解：指数生成函数： , 1 0 =h !4 12436445 )464( 4 1 ) 1 2 ( ! 2 1 ! 4! 2 )( 0 234532 3 2 2 42 )( n x eeeeee ee x x xx xg n n nnnn xxxxxx xx e = + = += + = + +=? 所以 4 123245 211 + = +nnnn n h 45、确定用所有的奇数数字组成的位数的个数，其中 1 和 3 每个都出现非零偶数次。 n 解：，指数生成函数： 0 0 =h = += = + = + + += 0 4 2 2 2342 )( !4 4 4 1 4 1 22 ! 2 1 ! 3! 4! 2 1)( n nn x x xxxx e n x e e eeee x x x x xx xg? 因此 1 4 = n n h 第八章第八章 特殊计数序列特殊计数序列 1、设在圆上选择 2n 个（等间隔的）点。证明将这些点成对连接起来所得到的 n 条线段不相 交的方法数等于第 n 个 Catalan 数。 n C 证明 设为将圆上的 2n 个点成对连