组合数学7章作业答案

第7章 递推关系和生成函数

7.8 练习题

16、求解初始值h0 1，h1 0和h2 0的递推关系hn 3hn 2 2hn 3，（n 3）。

解：

□

18、确定长为n、不包含两个相连的0或相连的1的三进制串（即由一些0、1和2组成的串）的个数an的

公式。

解：

□

23、求解非齐次递推关系hn 4hn 1 3 2（n 1

n

解：由定理3.4.4

6个没有区别的车放在6 6棋盘上，使没有两个车能够互相攻击的放置方法有6！种。

(6!)2

2个红车4个蓝车，那么放置方法是=6！×15种。 2! 4!

□

19、给定8个车，其中5个红车，3个蓝车。

ⅰ) 将8个车放在8 8棋盘上，使没有两个车能够互相攻击的放置方法有多少？

ⅱ) 将8个车放在12 12棋盘上，使没有两个车能够互相攻击的放置方法有多少？

解：ⅰ) 由定理3.4.4

8 8个没有区别的车放在8 8棋盘上，使没有两个车能够互相攻击的放置方法有8! 3

种。

□

ⅱ) 将8个车放在12 12棋盘上，使没有两个车能够互相攻击的放置方法有

12 12 8 8! 8 8 3 种。

□

21、单词ADDRESSES的字母有多少排列？这9个字母有多少8-排列？

解：因为有1个A，2个D，1个R，2个E，3个S

9! 所以，字母的排列共有个。 2! 2! 3!

8!8!8!8!8! 8-排列的个数是种。 2! 2! 3!2! 3!2! 2! 3!2! 3!2! 2! 2!

□