组合数学期末重点第一章：7 11 14 25 267. n 个男n 个女排成一男女相间的队伍，试问有多少种不同的方案？若围成一圆桌坐下，又有多少种不同的方案？[解].(1)若第1个位置是男，有n ⋅n ⋅(n -1)⋅(n -1)⋅⋯⋅3⋅3⋅2⋅2⋅1⋅1=(n!)2种排法；若第1个位置是女，也有(n!)2种排法；故n 个男n 个女排成一男女相间的队伍，有2(n!)2种不同的排法。

因为若不记座位的差别，只记人与人之间的相对位置的变化，则每一种坐法可产生2n个男女相间的排列，从而坐法为22])!1[()!1(!2)!(2-=-=n n n n nn 种，若不记顺、逆时针则有坐法22])!1[(21)!1(!2122)!(2-=-=⋅n n n n n n 种。

(2)若第1个座位坐男，有n 个可能，则第2个坐女为n 个可能，……，根据乘法原理，故有n ⋅n ⋅(n -1)⋅(n -1)⋅⋯⋅3⋅3⋅2⋅2⋅1⋅1=(n!)2种方案。

同理，第1个座位坐女，也有(n!)2种方案。

故有2(n!)2种方案。

11.凸10边形的任意三条对角线不共点。

试求这凸10边形的对角线交于多少个点？又把所有的对角线分割成多少段？[解].(参见柯召《组合数学》上册。

P 34 例1.6.1)(2)从上。

一个点引出的7条线中第一条线上有7个点，故将该线段分成8段；第二条线上有12个点，故将该线段分成13段，故从一个点出发的7条线上的段数为第11题图1第11题图28+13+16+17+16+13+8=91故有10个点。

故总的段数可为91⨯10=910。

但有重复，重复数为2（因为每条线有两个端点）。

故总的段数为4552910=。

14.从26个英文字母中取出6个字母组成一字,若其中有2或3个母音.问分别可构成多少个字(不允许重复)?[解].英语中有6个元音字母a,e.i,(y),o,u,其余20个是辅音。

(1)若取出6个字母组成一字,其中有2个元音,可构成1234561256123417181920!626420⨯⨯⨯⨯⨯⨯⨯⨯⨯⨯⨯⨯⨯⨯⨯=⋅⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛=52 326 000 (2)若有三个元音,可构成123456123456123181920!636320⨯⨯⨯⨯⨯⨯⨯⨯⨯⨯⨯⨯⨯⨯⨯=⋅⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛=16 416 000； 另一种解法认为有5个元音，其余21个是辅音(1)若取出6个字母组成一字,其中有2个元音,可构成1234561245123418192021!625421⨯⨯⨯⨯⨯⨯⨯⨯⨯⨯⨯⨯⨯⨯⨯=⋅⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛=43 092 000 (2)若有三个元音,可构成1234561245123192021!635321⨯⨯⨯⨯⨯⨯⨯⨯⨯⨯⨯⨯⨯=⋅⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛=9 576 000。

25.5台教学机器m 个学生使用，使用第1台和第2台的人数相等，有多少种使用方案？ [解].先从m 个学生中选取k 个使用第1台机器，再从剩下的m -k 个学生中选取k 个使用第2台机器，其余m -2k 个学生可以任意使用剩下的3台机器，按乘法原理，其组合数为C (m,k)C (m -k ,k )⋅3(m -2k )。

这里k=0,1,2,⋯,q (⎥⎦⎥⎢⎣⎢=2m q )，于是，按加法原理，共有)2(qk 3),(),(k m k k m C k m C -=⋅-∑种使用方案。

26.在由n 个0及n 个1构成的字符串中，任意前k 个字符中，0的个数不少于1的个数的字符串有多少？[解].转化为格路问题（弱领先条件—参见P36例4该例是强领先条件）。

即从(0,0)到(n,n)，只能从对角线上方走，但可以碰到对角线。

它可看作是从(0,1)到(n,n+1)的强领先条件（只能从对角线上方走，但不可以碰到对角线）的格路问题。

更进一步的，它可看作是从(0,0)到(n,n+1)的强领先条件的格路问题(n+1,n+1)(0,1)(1,0)(n,n+1)(n,n) (0,0) 第26题图1(因为此种格路第一步必到(0,1)格点)。

故这样的字符串有⎪⎪⎭⎫ ⎝⎛-++-n n n 1)1(0-⎪⎪⎭⎫ ⎝⎛--++-10)1(1n n n =C (2n,n)-C (2n,n -1)个。

第二章：2.42 2.43 2.44 4 5 62.42. 设{a n }满足a n - a n -1- a n -2 = 0，{b n }满足b n - 2b n -1- b n -2 = 0，c n = a n + b n ，n =0, 1, 2, 3, ⋯，试证序列{c n }满足一个四阶线性常系数齐次递推关系。

[解]方法一：(特征系数法)由于序列{a n }满足递推关系：a n - a n -1- a n -2 = 0 故显然也满足递推关系：(a n - a n -1- a n -2) + A 1(a n -1 - a n -2- a n -3) + A 2(a n -2 - a n -3- a n -4) = 0 这里A 1，A 2为任意常数整理为：a n + (A 1 - 1)a n -1+ (A 2 - A 1 - 1)a n -2 - (A 1 + A 2)a n -3 - A 2a n -4 = 0 由于序列{b n }满足递推关系：b n - 2b n -1- b n -2 = 0 故显然也满足递推关系：(b n - 2b n -1- b n -2) + B 1(b n -1 - 2b n -2- b n -3) + B 2(b n -2 - 2b n -3- b n -4) = 0 这里B 1，B 1为任意常数整理为：b n + (B 1 - 2)b n -1+ (B 2 - 2B 1 - 1)b n -2 - (B 1 + 2B 2)b n -3 - B 2b n -4 = 0 ● 令：⎪⎪⎩⎪⎪⎨⎧=+=+--=---=-222121121211212121B A B B A A B B A A B A解之得：⎩⎨⎧-=-=1221A A ，⎩⎨⎧-=-=1121B B将此解代入 和●，有：a n - 3a n -1 + 3a n -3 + a n -4 = 0 ❍b n - 3b n -1 + 3b n -3 + b n -4 = 0 ⏹将❍+⏹，并注意到c n = a n + b n ，我们有：c n - 3c n -1 + 3c n -3 + c n -4 = 0 ☐ 这就是序列{c n }所满足的四阶线性常系数齐次递推关系。

方法二：(特征根法)序列{a n }的递推关系：a n - a n -1- a n -2 = 0特征方程：γ2 - γ - 1 = 0 特征根：γ1 =251+，γ2 =251- 故其通解为：b n = A ⋅(251+)n+ B ⋅(251-)n 序列{b n }的递推关系：b n - 2b n -1- b n -2 = 0特征方程：γ2 - 2γ - 1 = 0特征根：γ1 =21+，γ2 =21-故其通解为：b n = C ⋅(21+)n + D ⋅(21-)n于是有：c n = a n + b n = A ⋅(251+)n+ B ⋅(251-)n + C ⋅(21+)n + D ⋅(21-)n 因此序列{c n }所满足的线性常系数齐次递推关系的特征多项式为： (γ -251+)(γ -251-)[γ -(21+)][γ -(21-)] = 0 整理为：(γ2 - γ - 1)(γ2 - 2γ - 1) = 0再整理为：γ 4 - 3γ3 + 3γ + 1 = 0因此，对应的四阶线性常系数齐次递推关系为：c n - 3c n -1 + 3c n -3 + c n -4 = 0 。

2.43.在习题2.42中，若c n = a n b n ，试讨论之。

[解](特征根法)序列{a n }的递推关系：a n - a n -1- a n -2 = 0特征方程：γ2 - γ - 1 = 0 特征根：γ1 =251+，γ2 =251- 故其通解为：b n = A ⋅(251+)n+ B ⋅(251-)n 序列{b n }的递推关系：b n - 2b n -1- b n -2 = 0特征方程：γ2 - 2γ - 1 = 0 特征根：γ1 =21+，γ2 =21-故其通解为：b n = C ⋅(21+)n + D ⋅(21-)n于是有：c n = a n b n = [A ⋅(251+)n+ B ⋅(251-)n ][C ⋅(21+)n + D ⋅(21-)n ] = AC ⋅(251+)n (21+)n + AD ⋅(251+)n (21-)n + BC ⋅(251-)n (21+)n + BD ⋅(251-)n(21-)n 因此序列{c n }所满足的线性常系数齐次递推关系的特征多项式为： [γ -251+(21+)][γ -251+(21-)][γ -251-(21+)][γ -251-(21-)] = 0 整理为：[γ2 - (51+)γ - (251+)2][γ 2- (51-)γ - (251-)2] = 0 再整理为：γ 4 - 2γ 3 - 7γ2 - 2γ + 1 = 0因此，对应的四阶线性常系数齐次递推关系为：c n - 2c n -1- 7c n -2 - 2c n -3 + c n -4 = 0 。

2.44. 设{a n }和{b n }均满足递推关系x n + b 1x n -1+ b 2x n -2 = 0，试证： (a) {a n b n }满足一个三阶齐次线性常系数递推关系； (b) a 0, a 2, a 4, ⋯ 满足一个二阶线性常系数齐次递推关系。

[证](a)(特征根法)二阶齐次线性常系数递推关系x n + b 1x n -1+ b 2x n -2 = 0的特征方程为： x 2 + b 1x + b 2 = 0 设其特征根为γ1，γ2(1)如果 γ1 ≠ γ2 ，则有：a n = A ⋅n 1γ+ B ⋅n 2γ ，b n = C ⋅n 1γ+ D ⋅n 2γ 于是：c n = a n b n = (A ⋅n 1γ+ B ⋅n 2γ)(C ⋅n 1γ+ D ⋅n 2γ) = AC ⋅(21γ)n + (AD + BC )⋅(γ1γ2)n + BD ⋅(22γ)n 这说明{c n }满足一个三阶齐次线性常系数递推关系。

其特征方程为：(x -21γ)(x -γ1γ2)(x -22γ) = 0整理为：x 3 - (21γ+ γ1γ2 +22γ)x 2 + (231γγ+2221γγ +321γγ)x - (γ1γ2)3 = 0由于γ1 + γ2 = - b 1，γ1γ2 = b 2，故21γ+ γ1γ2 +22γ=21b - b 2 因此有：x 3 - (21b - b 2)x 2 + b 2(21b - b 2)x -32b = 0 故此{c n }满足如下的三阶齐次线性常系数递推关系：c n - (21b - b 2)c n -1 + b 2(21b - b 2)c n -2 -32b c n -3 = 0 。