《组合数学》测试题含答案(4)

ｎ

（（ｋ－１＋ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２） ＋（ｋ／（２（ｋ－１））－ｋ／（２·ｓｑｒｔ（（ｋ－１）（ｋ＋３）））·

ｎ

（（ｋ－１－ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２）

假设从ｋ（ｋ＞１）个不同文字取出ｎ个（可以重复）作排列，但不允许一个文字连续出现３次的排列所组成的集合为Ａｎ，则所求排列数ａｎ＝｜Ａｎ｜。将Ａｎ中的字符串按最后一个文字可以分成两类：一类是最后一个文字同其前一个文字不相同的那些字符串，共有（ｋ－１）ａｎ－１个（最后一位有ｋ－１种选择，而前ｎ－１位是没有一个文字连续出现３次的字符串），另一类是最后两个文字相同，但与倒数第３个文字不相同的字符串，共有（ｋ－１）ａｎ－２个，所以有递推关系

ａｎ＝（ｋ－１）ａｎ－１＋（ｋ－１）ａｎ－２（

２３

而ａ１＝ｋ，ａ２＝ｋ，ａ３＝ｋ－ｋ＝ｋ（ｋ－１）（ｋ＋１ 递推关系的特征方程为

２

ｘ－（ｋ－１）ｘ－（ｋ－１）＝０ 其根为：

α１＝（ｋ－１＋ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２ α２＝（ｋ－１－ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２

ｎｎ

于是知 ａｎ＝Ａ１α１＋Ａ２α２

２

由于ａ１＝ｋ，ａ２＝ｋ，由递推关系知ａ０＝ｋ／（ｋ－１），所以

００

ａ０＝ｋ／（ｋ－１）＝Ａ１α１＋Ａ２α２Ａ＝Ａ１＋Ａ２

１１

ａ１＝ｋ＝Ａ１α１＋Ａ２α２＝Ａ１（ｋ－１＋ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２ ＋Ａ２（ｋ－１－ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２ 解得

Ａ１＝（ｋ／（２（ｋ－１））＋ｋ／（２·ｓｑｒｔ（（ｋ－１）（ｋ＋３））） Ａ２＝（ｋ／（２（ｋ－１））－ｋ／（２·ｓｑｒｔ（（ｋ－１）（ｋ＋３））） 所以

ａｎ＝（ｋ／（２（ｋ－１））＋ｋ／（２·ｓｑｒｔ（（ｋ－１）（ｋ＋３）））·

ｎ

（（ｋ－１＋ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２） ＋（ｋ／（２（ｋ－１））－ｋ／（２·ｓｑｒｔ（（ｋ－１）（ｋ＋３）））·

ｎ

（（ｋ－１－ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２）

n＋1n＋1

53. f（n）＝（（（１＋√５）／２）－（（１－√５）／２））／√５

假设从A（编号为０）到编号为i的顶点有f（i）条路径，则f（１）＝１，f（２）＝２，当i＞2时，f（i）＝f（i-1）＋f（i－2），由此知f（０）＝f（A）＝１。当i＝n时，f（n）＝f（n-1）＋f（n－2）,即f（n）－f（n-1）－f（n－2）＝０。其特征方程为： 2

x－x－1=0，它的两个根分别为：α１＝（１＋√５）／２，α２＝（１－√５）／２。

ｎｎ

于是知f（n）＝Ａ１α１＋Ａ２α２，根据 f（０）＝１＝A1＋A2

f（１）＝１＝A1（１＋√５）／２＋A2（１－√５）／２， 解得

A1＝（１＋√５）／（２√５），A2＝（１－√５）／（２√５）

所以，

n＋1n＋1

f（n）＝（（（１＋√５）／２）－（（１－√５）／２））／√５＝F（n＋1） 其中F（n）为第n个Fibonacci数。

54. an＝（n＋n＋２）／２

设n条符合条件的直线将平面分成an个区域，那么n－１条直线可将平面分成an－１个区域，而第n条直线与前n-1条直线均相交，有n－１个交点，因此第n条直线被分成n段，而每一段对应一个新增的区域，所以有an＝an－１＋n，即an－an－１＝n。于是

an－１－an－２＝n－１，由此得an－２an－１＋an－２＝１，同样有an－１－２an－２＋an－３＝１，

32

故得an－３an－１＋３an－２－an－３＝０，其特征方程为x－３x＋３x－1＝０，解此方程

2n2

得α＝α１＝α２＝α３＝１，所以an＝（A0＋A1n＋A2n）α＝A0＋A1n＋A2n ，而

a0＝１＝A0 a1＝２＝A0＋A1＋A2

a２＝４＝A0＋２A1＋４A2

解得 A0=1 A1=1/2 A2=1/2

由此知

2

an＝（n＋n＋２）／２

55、56

因为x1＋x2＋x3＋x４＝31,xi≥0（i＝１，２，３，４）的整数解共有C（4+31-1，31）＝C（34，３）＝34·33·32/6＝5984（个）。

再考虑x1＋x2＋x3＋x４＝31,xi≥１0（i＝１，２，３，４）的整数解的个数。令N为全体非负整数解，则｜N｜＝5984。

令Ai(i＝１，２，３，４)为其中xi≥１0的解集合。则｜A1｜即为（x1＋10）＋x2＋x3＋x４＝31，也就是x1＋x2＋x3＋x４＝21的非负整数解的个数。所以，

｜A1｜＝C（４＋21－１，21）＝C（24，3）＝24·23·22/6＝2024。同理可知 ｜A２｜＝｜A３｜＝｜A４｜＝｜A1｜＝2024。类似地，

｜Ai∩Aj｜＝C（4＋11－１,11）＝C（14，3）＝14·13·12/6＝364（１≤i<j≤4）， ｜Ai∩Aj∩Ak｜＝C（4＋1－１，1）＝C（4，1）＝4（１≤i<j<k≤4），而 ｜A１∩A２∩A３∩A４｜＝０。

根据容斥原理，a＋b＋c＋d＝31，０≤a，b，c，d≤９的整数解个数等于 ｜Ã１∩Ã２∩Ã３∩Ã４｜＝

｜N｜－４｜A１｜＋C（4，2）｜A１∩A２｜－C（4，3）｜A１∩A２∩A３｜＋ ｜A１∩A２∩A３∩A４｜

＝5984－4·2024＋6·364—4·4＋0＝56 56. 190800

假设６个学生参加第１位教师的面试的顺序为１、２、３、４、５、６（即对第１个面试的学生编号１，．．．，对第６个面试的学生编号６），那么，这６个学生参加第２位教师的面试的顺序必定是１、２、３、４、５、６的一个错排。不然，就有至少一个学生要同时参加两为教师的面试。于是面试方案总数为

6!D6＝6!6!（1－1＋1/2!－1/3!＋1/4!－1/5!＋1/6!）＝6!256＝190800 57. 1505

对应于旋转与翻转的运动群的置换为：

６

p1（不动） （1）（2）（3）（4）（5）（6） 格式为（１）

１

p2（逆时针旋转60º） （123456） 格式为（６）

2

p3（逆时针旋转120º） （135）(246） 格式为（3）

2

p4（逆时针旋转180º） （14）（25）（36） 格式为（2）

2

p5（逆时针旋转240º） （153）（264） 格式为（3）

１

p6（逆时针旋转300º） （654321） 格式为（６）

22

p7（沿14轴翻转） （1）（4）（26）（35） 格式为（1）（２） 22

p8（沿25轴翻转） （2）（5）（13）（46） 格式为（1）（２）

22

p9（沿36轴翻转） （3）（6）（15）（24） 格式为（1）（２）

３

p10（沿12边54边中线翻转）（12）（36）（45） 格式为（２）

３

p11（沿23边56边中线翻转）（14）（23）（56） 格式为（２）

３

p12（沿16边34边中线翻转）（16）（25）（34） 格式为（２） 所以，总方案数为

61234

l＝（5＋2·5＋2·5＋4·5＋3·5）/12＝18060/12＝1505 58．

3

1110100 H 0111010

1101001 3 7

因为

1

0G

0 0

而

01000010000111100111

1 1

I3|A4 …… 此处隐藏：964字，全部文档内容请下载后查看。喜欢就下载吧 ……