清华大学：《组合数学》课程教学资源（PPT课件讲稿）第二章 习题解答

1.题目 解 (1+x)2=(1+x)2(1+x) 2n(2n x+∴ 2n\_2n 0R 2n n n x+∴ 0 n0 n n n 比较n次方系数即可证

1. 题目 解：         =             =             + +       +      =        + +       +       + = +  +      , n -1 n 1 n , n n 0 n ] n n 1 n 0 n [ 2n 2n 1 2n 0 2n (1 ) (1 ) (1 ) 2 2 2 n n n n n x x x x x x x 比较n次方系数即可证

题目 解::(1+x4+x8) 100 8、100 =|1+(x+x 8k100-k 100°(x+x k=0 分析(x4+x3)的结构可知仅当k=345 时有x20项 k=3时,系数 1003 k=4时,系数=C0C k=5时,系数=CC0 个系数相加即为所求

2. 题目 解：  = − =  +  + + = + + 100 0 4 8 100 100 4 8 100 4 8 100 ( ) 1 (1 ) [1 ( )] k k k k C x x  x x x x 分析 的结构可知仅当 时有 项 k (x x ) 4 8 + k = 3,4,5 20 x 2 3 3 100 k = 3时， 系数 = C C 3 4 4 100 k = 4时， 系数 = C C 0 5 5 100 k = 5时， 系数 = C C 三个系数相加即为所求

3.题目 解 用指数型母函数,可得母函数 G(x)=(1+x+x2)4·(1+x+x2+x3)3 x系数即为所求

3. 题目 解： 用指数型母函数，可得母函数 2 4 2 3 3 G(x) = (1+ x + x ) (1+ x + x + x )  x 10 系数即为所求

4.题目 解:A、B、C、D组成的全排列数为 x× P=(1 2 出现A后,其后续字母必为A、B、C、D 中的一个,其概率相等。 P=(1+x+…):1+3x+4

4. 题目 解：A、B、C、D组成的全排列数为 x e x x P 4 4 2 ) 1! 2! (1 = = + + + 出现A后，其后续字母必为A、B、C、D 中的一个，其概率相等。 x x x e e e x x x P 4 15 4 3 3 2 3 ] 2! ) 4 3( 4 3 ) [1 1! (1 =  =   = + +  + + +

AB至少出现一次的排列为 p=P-pi=e4x-e4 15 排列数为 4

 AB至少出现一次的排列为   = − =  = −  = − 0 4 15 4 ! ) 4 15 4 ( n n n n x x x n P P P e e  排列数为 n n an ) 4 15 = 4 − (

5.题目 解:对符合题设要求的排列如果0可以出现 在最高位,则可得母函数: G(x)=(1+x+-+…)2·( e4x+2e2+1)

5. 题目 解：对符合题设要求的排列如果0可以出现 在最高位，则可得母函数： ! (4 2 2 1) 4 1 ( 2 1) 4 1 ( )] 2 1 [ ) 2! 4! ) (1 2! ( ) (1 0 4 2 2 2 2 2 4 2 2 n x e e e e e x x x G x x n n n n x x x x x = +  + = + + =  + = + + +  + + +   = −  

an=(4+2.2+1) 但是对n位四进制数来说最高位不能为 0 [(4+2.2"+1)-(421+2.2-1+1) 4 (3.4-+2") 4

但是对n位四进制数来说最高位不能为 0。 (4 2 2 1) 4 1  = +  + n n an (3 4 2 ) 4 1 [(4 2 2 1) (4 2 2 1)] 4 1 1 1 1 1 n n n n n n an an an =  + = +  + − +  + = −   − − − −

6.题目 解: 参见第四题解答前半部分

6. 题目 解： 参见第四题解答前半部分

7.题目 解:题设中序列的母函数为: G(x=C(n, n)+C(n+I, n)x+ +C(n+, n)x+ ∑C(n+k,n)x k=0 (k+m)(k+n-1)…(k+1) k=0 由$4性质3得,上式 n+

7. 题目 解：题设中序列的母函数为：    =  = + + − + = = + + + + = + + + 0 0 ! ( )( 1) ( 1) ( , ) ( , ) ( ) ( , ) ( 1, ) k k k k k x n k n k n k C n k n x C n k n x G x C n n C n n x    由$4性质3得，上式 1 (1 ) 1 + − = n x

8.题目 解: 等式的右端相当于从n+m+1个球中取 n+1个球的组合。 把这n+m+1个球编号,如果取出的n+1 个球中最小编号是一,则得到C(n+m,n 如果最小编号是二则得到C(n+m-1,n) 如果最小编号是m则得到C(n,n) 可证

8. 题目 解： 等式的右端相当于从n+m+1个球中取 n+1个球的组合。 把这n+m+1个球编号，如果取出的n+1 个球中最小编号是一，则得到 如果最小编号是二则得到 如果最小编号是m则得到 。 可证 C(n + m,n) C(n + m −1,n) C(n,n) 