发布时间 : 星期五 文章《组合数学》测试题含答案更新完毕开始阅读8ba42691866fb84ae55c8d5d
＝ｎ（ｎ＋１）（ｎ＋２）（ｎ＋３）／４ 52. ａｎ＝（ｋ／（２（ｋ－１））＋ｋ／（２·ｓｑｒｔ（（ｋ－１）（ｋ＋３）））·
ｎ
（（ｋ－１＋ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２） ＋（ｋ／（２（ｋ－１））－ｋ／（２·ｓｑｒｔ（（ｋ－１）（ｋ＋３）））·
ｎ
（（ｋ－１－ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２）
假设从ｋ（ｋ＞１）个不同文字取出ｎ个（可以重复）作排列，但不允许一个文字连续出现３次的排列所组成的集合为Ａｎ，则所求排列数ａｎ＝｜Ａｎ｜。将Ａｎ中的字符串按最后一个文字可以分成两类：一类是最后一个文字同其前一个文字不相同的那些字符串，共有（ｋ－１）ａｎ－１个（最后一位有ｋ－１种选择，而前ｎ－１位是没有一个文字连续出现３次的字符串），另一类是最后两个文字相同，但与倒数第３个文字不相同的字符串，共有（ｋ－１）ａｎ－２个，所以有递推关系
ａｎ＝（ｋ－１）ａｎ－１＋（ｋ－１）ａｎ－２（
２３
而ａ１＝ｋ，ａ２＝ｋ，ａ３＝ｋ－ｋ＝ｋ（ｋ－１）（ｋ＋１ 递推关系的特征方程为
２
ｘ－（ｋ－１）ｘ－（ｋ－１）＝０ 其根为：
α１＝（ｋ－１＋ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２ α２＝（ｋ－１－ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２
ｎｎ
于是知 ａｎ＝Ａ１α１＋Ａ２α２
２
由于ａ１＝ｋ，ａ２＝ｋ，由递推关系知ａ０＝ｋ／（ｋ－１），所以
００
ａ０＝ｋ／（ｋ－１）＝Ａ１α１＋Ａ２α２Ａ＝Ａ１＋Ａ２
１１
ａ１＝ｋ＝Ａ１α１＋Ａ２α２＝Ａ１（ｋ－１＋ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２ ＋Ａ２（ｋ－１－ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２ 解得
Ａ１＝（ｋ／（２（ｋ－１））＋ｋ／（２·ｓｑｒｔ（（ｋ－１）（ｋ＋３））） Ａ２＝（ｋ／（２（ｋ－１））－ｋ／（２·ｓｑｒｔ（（ｋ－１）（ｋ＋３））） 所以
ａｎ＝（ｋ／（２（ｋ－１））＋ｋ／（２·ｓｑｒｔ（（ｋ－１）（ｋ＋３）））·
ｎ
（（ｋ－１＋ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２） ＋（ｋ／（２（ｋ－１））－ｋ／（２·ｓｑｒｔ（（ｋ－１）（ｋ＋３）））·
ｎ
（（ｋ－１－ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２）
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 根据容斥原理，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（逆时针旋转60o） （123456） 格式为（６） 2 p3（逆时针旋转120o） （135）(246） 格式为（3） 2 p4（逆时针旋转180o） （14）（25）（36） 格式为（2） 2 p5（逆时针旋转240o） （153）（264） 格式为（3） １ p6（逆时针旋转300o） （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?而 010000100001111001111??1???I3|A4?3? 0??1??4?7?1110???AT??0111? ?1101???3?4H??AT|I3?3?7 59. Ｃ（m＋１，ｎ） 将ｍ个０排成一行，两个０之间有一间隔，共有ｍ＋１（≥ｎ）个间隔（包括头尾处的间隔）。在此ｍ＋１个间隔中任取ｎ个插入１，则所得符号串满足要求，所以共有 Ｃ（ｍ＋１，ｎ）个这样的符号串。 60. （ｎ－１）！ｎ！，（ｎ－１）！ｎ！／（ｎ－ｍ）！ 先让ｎ个男人围坐一圈，共有（ｎ－１）！种坐法。对应于每一种坐法，有n个间隔，将n个女人排成一行插入这n个间隔中，有n!种方案，所以共有（n—1）!n!种不同的坐法。 若只有m（m ｎn+1n+1 61．ａｎ＝4-√3（2+√3）/6+√3（2-√3）/6 设长度为n的由A、B、C、D组成的允许重复的排列中AB至少出现一次的排列所组成的集合为Sn,又设ａｎ＝｜Sｎ｜。而AB一次也不出现的排列所组成的集合为Bn,又设bｎ＝ ｜Bｎ｜。可将Sｎ中的所有排列按AB出现的位置分为两类：一类是在前n-1位中均未出现AB，它仅出现在最末两位，则这种排列共有bn-2个。另一类是在前n-1位中已出 现AB,而最后一位可以是A、B、C、D中的任一个，所以这类排列共有4an-1个，于是知 nn-2n-2 ａｎ＝4an-1 +bn-2，而ａｎ+bn=4，即aｎ-2+bn-2=4，也就是bn-2=4 -aｎ-2， n-2n-2n-2 由此知ａｎ＝4an-1 +4 -aｎ-2，即ａｎ-4an-1 +aｎ-2=4，可推知4(ａｎ-1-4an-2 +aｎ-3)=4 32 于是得ａｎ-8an-1 +17aｎ-2-4an-3=0，其特征方程为x-8x+17x-4=0,解此方程得 nnn α１＝4，α２＝2+√3，α３＝2-√3，所以可设ａｎ＝A1α１+A2α２+A3α３，已知ａ1＝0，a2 =1，由此推知a0=0，所以有 a0=0= A1+A2+A3 a1=0= 4A1+（2+√3）A2+（2-√3）A3 a2=1= 16A1+（7+4√3）A2+（7-4√3）A3 化简得 A1+A2+A3=0 2A1+√3A2-√3A3=0 9A1+4√3A2-4√3A3=0 解得 A1=1 A2=-（3+2√3）/6 A3=-（3-2√3）/6 所以 ｎnn ａｎ=4-（3+2√3）（2+√3）/6-（3-2√3）（2-√3）/6 ｎn+1n+1 =4-√3（2+√3）/6+√3（2-√3）/6 62．135 令y1+6=x1，y2+5=x2，y3+10=x3，则0≤y1≤9，0≤y2≤15，0≤y3≤15，于是有 y1+6+y2+5+y3+10=40，即y1+y2+y3=19，0≤y1≤9，0≤y2≤15，0≤y3≤15，因为 y1+y2+y3=19的非负整数解的个数为C（3+19-1，19）=C（21，2）=21·20/2=210。 令A1是y1+y2+y3=19当y1≥10时的非负整数解集合，则| A1|=C（3+9-1，9）=C（11，2） =11·10/2=55， 令A2是y1+y2+y3=19当y2≥16时的非负整数解集合，则| A2|=C（3+3-1，3）=C（5，2） =5·4/2=10， 令A3是y1+y2+y3=19当y3≥16时的非负整数解集合，则| A3|=C（3+3-1，9）=C（5，2） =5·4/2=10， 而且| A1 ∩A2|=| A2 ∩A3|=| A1 ∩A3|=0，| A1 ∩A2 ∩A3|=0，根据容斥原理可知，符合条件的解的个数为 ｜?１∩?２∩?３｜=210-（55+10+10）=210-75=135 63．30 设S={1，2，3，?，120}，若n∈S且n为合数，即n=n1·n2，则因为11·11=121>120，所以n1或n2中必有一数∈{2，3，5，7}。 设A1表示S中能被2整除的数，则| A1|=int（120/2）=60（int（x）表示不超过x的最大整数）， 设A2表示S中能被3整除的数，则| A2|=int（120/3）=40， 设A3表示S中能被5整除的数，则| A3|=int（120/5）=24， 设A4表示S中能被7整除的数，则| A4|=int（120/7）=17， 而且， | A1 ∩A2|=20，| A1 ∩A3|=12，| A1 ∩A4|=8， | A2 ∩A3|=8，| A2 ∩A4|=5，| A3 ∩A4|=3， | A1 ∩A2 ∩A3|=4，| A1 ∩A2 ∩A4|=2，| A1 ∩A3 ∩A4|=1，| A2 ∩A3 ∩A4|=1，