组合数学试题集
一.简单题目
可以根据需要改成选择题或者填空题
1．在1到9999之间，有多少个每位上数字全不相同而且由奇数构成的整数？（参见课本21页）
解：该题相当于从“1，3，5，7，9”五个数字中分别选出1，2，3，4作排列的方案数；
（1）选1个，即构成1位数，共有P5个； （2）选2个，即构成两位数，共有P5个； （3）选3个，即构成3位数，共有P5个； （4）选4个，即构成4位数，共有P5个；
1234 由加法法则可知，所求的整数共有：P5?P5?P5?P5?205个。
12342．一教室有两排，每排8个座位，今有14名学生，问按下列不同的方式入座，各有多少种做法？（参见课本21页）
（1）规定某5人总坐在前排，某4人总坐在后排，但每人具体座位不指定； （2）要求前排至少坐5人，后排至少坐4人。
解：（1）因为就坐是有次序的，所有是排列问题。
5人坐前排，其坐法数为P(8,5)，4人坐后排，其坐法数为P(8,4)，
剩下的5个人在其余座位的就坐方式有P(7,5)种， 根据乘法原理，就座方式总共有：
P(8,5)gP(8,4)gP(7,5)?28449792000（种）
（2）因前排至少需坐6人，最多坐8人，后排也是如此。
可分成三种情况分别讨论：
① 前排恰好坐6人，入座方式有C(14,6)P(8,6)P(8,8)； ② 前排恰好坐7人，入座方式有C(14,7)P(8,7)P(8,7)； ③ 前排恰好坐8人，入座方式有C(14,8)P(8,8)P(8,6)；
各类入座方式互相不同，由加法法则，总的入座方式总数为：
C(14,6)P(8,6)P(8,8)?C(14,7)P(8,7)P(8,7)?C(14,8)P(8,8)P(8,6)
?104613949440003．一位学者要在一周内安排50个小时的工作时间，而且每天至少工作5小时，问共有多少种安排方案？（参见课本21页）
解：用xi表示第i天的工作时间，i?1,2,L,7，则问题转化为求不定方程
x1?x2?x3?x4?x5?x6?x7?50的整数解的组数，且xi?5，于是又可以转化为求不定方程y1?y2?y3?y4?y5?y6?y7?15的整数解的组数。
该问题等价于：将15个没有区别的球，放入7个不同的盒子中，每盒球数不限，即相异元素允许重复的组合问题。
故安排方案共有：RC(?,15)?C(15?7?1,15)?54264 （种）
? 另解：
因为允许yi?0，所以问题转化为长度为1的15条线段中间有14个空，再加上前后两个空，共16个空，在这16个空中放入6个“＋”号，每个空放置的“＋”号数不限，未放“＋”号的线段合成一条线段，求放法的总数。从而不定方程的整数解共有：
RC(?,6)?C(16?6?1,6)? 即共有54 264种安排方案。
21?20?19?18?17?16?54264（组）
6?5?4?3?2?14.求下列函数的母函数: {n(n?1)}；（参见课本51页）
母函数为：
2x2x2x2G(x)??n(n?1)x??n(n?1)x?2?nx???； 323(1?x)(1?x)(1?x)n?0n?0n?0?n?n?n? 方法二： G(x)??n(n?1)x?0?0?xnn?02??2?n?n?1?xn?22n?2?x????n?0?n?2?x??n?2??n?1?x?xnn?0???2??x???x2??xn?2??x2??1?x?n?0????2x2
?1?x?35.求下列函数的母函数:{n(n?2)}；（参见课本51页）
母函数为：
2xx3x?x2G(x)??n(n?2)x??n(n?1)x??nx???。 323(1?x)(1?x)(1?x)n?0n?0n?0?n?n?n? 方法二：
G(x)??n(n?2)x???n?1??n?2?x???n?1?x??xnnnnn?0?n?0n?0n?0???????xn?2????xn?1?n?0n?02?????11??n?2???n?1?????x????x??1?x?n?0??n?0?1?x???x??x?1211??????????321?x1?x1?x1?x??1?x1?x???????3x?x2
?1?x?36．利用递推关系求下列和：Sn??k(k?2) （参见课本第92页）
k?0n显然，Sn?Sn?1?n(n?2)，
同理对应的齐次方程的特征根为1，特解为Sn?A(1)n?A，
*?n(Bn2?Cn?D)?Bn3?Cn2?Dn， 非齐次方程的特解为：Sn 所以，非齐次方程的通解为：Sn?Bn3?Cn2?Dn?A， 初始条件为：S0?0,S1?3,S2?11,S3?26，代入上式，可得 S0?A?0，S1?B?C?D?A?3，S2?8B?4C?2D?A?11，
S3?27B?9C?3D?A?26，解得：A?0，B?173，C?，D?， 362所以 Sn?n3?n2?n?? 方法二：
133276n(n?1)(2n?7)
6显然，Sn?Sn?1?n(n?2)，类似可得，Sn?1?Sn?2?(n?1)(n?1)， 两式相减得Sn?2Sn?1?Sn?2?2n?1，
同理可得Sn?1?2Sn?2?Sn?3?2(n?1)?1，两式再相减得
Sn?3Sn?1?3Sn?2?Sn?3?2，同理得Sn?1?3Sn?2?3Sn?3?Sn?4?2，
两式再相减，可得关于Sn的齐次定解问题：
?Sn?4Sn?1?6Sn?2?4Sn?3?Sn?4?0 ?S?0,S?3,S?11,S?26123?0 由（1）知，方程的通解为：Sn?A?Bn?Cn2?Dn3，代入初始条件得：
S0?A?0，S1?A?B?C?D?3，S2?A?2B?4C?8D?11，
731S3?A?3B?9C?27D?26，解得：A?0,B?,C?,D?，
623731n(n?1)(2n?7)故 Sn?n?n2?n3?
6236? 方法三（快速求系数）
n(n?1)n(n?1)(n?2)通解为：Sn?A0?A1n?A2， ?A32!3! 初始条件：S0?0,S1?3,S2?11,S3?26，代入得 A0?0，A0?A1?3，A0?2A1?A2?11，A0?3A1?3A2?A3?26， 解得：A0?0，A1?3，A2?5，A3?2 所以，Sn?3n?5
Sn??k(k?1)(k?2) （参见课本第92页） 7．利用递推关系求下列和：
k?0nn(n?1)n(n?1)(n?2)n(n?1)(2n?7) ?2?2!3!6显然，Sn?Sn?1?n(n?1)(n?2)，
同理对应的齐次方程的特征根为1，特解为Sn?A(1)n?A，
*?n(Bn3?Cn2?Dn?E)?Bn4?Cn3?Dn2?En， 非齐次方程的特解为：Sn 所以，非齐次方程的通解为：Sn?Bn4?Cn3?Dn2?En?A， 初始条件为：S0?0,S1?6,S2?30,S3?90,S4?210，代入上式，可得
S0?A?0，S1?B?C?D?E?A?6，S2?16B?8C?4D?2E?A?30，
S3?81B?27C?9D?3E?A?90，S4?256B?64C?16D?4E?A?210
解得：A?0，B?143211133，C?，D?，E?
4422n?n?1??n?2??n?3?1123n?n? 424所以 Sn?n4?n3?? 方法二：
显然，Sn?Sn?1?n(n?1)(n?2)，类似可得，Sn?1?Sn?2?n(n?1)(n?1)，
两式相减得Sn?2Sn?1?Sn?2?3n(n?1)，
同理可得Sn?1?2Sn?2?Sn?3?3n(n?1)，两式再相减得
Sn?3Sn?1?3Sn?2?Sn?3?6n，同理得Sn?1?3Sn?2?3Sn?3?Sn?4?6(n?1)，
两式再相减得Sn?4Sn?1?6Sn?2?4Sn?3?Sn?4?6， 同理可得Sn?1?4Sn?2?6Sn?3?4Sn?4?Sn?5?6，
两式再相减，可得关于Sn的齐次定解问题：
?Sn?5Sn?1?10Sn?2?10Sn?3?5Sn?4?Sn?5?0 ?S?0,S?6,S?30,S?90,S?2101234?0 其特征方程为：x5?5x4?10x3?10x2?5x?1?0，x?1是五重特征根，
所以方程的通解为：Sn?A?Bn?Cn2?Dn3?En4，代入初始条件得：
S0?A?0，S1?A?B?C?D?E?6，S2?A?2B?4C?8D?16E?30， S3?A?3B?9C?27D?81E?90，S4?A?4B?16C?64D?256E?210，
解得：A?0,B?,C?故 Sn?n?32321131,D?,E?， 4241123314n?n?1??n?2??n?3?n?n?n?
4244? 方法三（快速求系数）
通解为：Sn?A0?A1n?A2n(n?1)n(n?1)(n?2)n(n?1)(n?2)(n?3)?A3?A4， 2!3!4! 初始条件：S0?0,S1?6,S2?30,S3?90,S4?210，代入得
（完整版）组合数学试题集
