组合数学试题集一.简单题目可以根据需要改成选择题或者填空题1．在1到9999之间，有多少个每位上数字全不相同而且由奇数构成的整数？（参见课本21页）解：该题相当于从“1，3，5，7，9”五个数字中分别选出1，2，3，4作排列的方案数； （1）选1个，即构成1位数，共有15P 个；（2）选2个，即构成两位数，共有25P 个；（3）选3个，即构成3位数，共有35P 个；（4）选4个，即构成4位数，共有45P 个；由加法法则可知，所求的整数共有：12345555205P P P P +++=个。

2．一教室有两排，每排8个座位，今有14名学生，问按下列不同的方式入座，各有多少种做法？（参见课本21页）（1）规定某5人总坐在前排，某4人总坐在后排，但每人具体座位不指定；（2）要求前排至少坐5人，后排至少坐4人。

解：（1）因为就坐是有次序的，所有是排列问题。

5人坐前排，其坐法数为(8,5)P ，4人坐后排，其坐法数为(8,4)P ，剩下的5个人在其余座位的就坐方式有(7,5)P 种，根据乘法原理，就座方式总共有：(8,5)(8,4)(7,5)28449792000P P P =（种）（2）因前排至少需坐6人，最多坐8人，后排也是如此。

可分成三种情况分别讨论：① 前排恰好坐6人，入座方式有(14,6)(8,6)(8,8)C P P ；② 前排恰好坐7人，入座方式有(14,7)(8,7)(8,7)C P P ；③ 前排恰好坐8人，入座方式有(14,8)(8,8)(8,6)C P P ；各类入座方式互相不同，由加法法则，总的入座方式总数为：(14,6)(8,6)(8,8)(14,7)(8,7)(8,7)(14,8)(8,8)(8,6)10461394944000C P P C P P C P P ++= 3．一位学者要在一周安排50个小时的工作时间，而且每天至少工作5小时，问共有多少种安排方案？（参见课本21页）解：用i x 表示第i 天的工作时间，1,2,,7i =，则问题转化为求不定方程123456750x x x x x x x ++++++=的整数解的组数，且5i x ≥，于是又可以转化为求不定方程123456715y y y y y y y ++++++=的整数解的组数。

该问题等价于：将15个没有区别的球，放入7个不同的盒子中，每盒球数不限，即相异元素允许重复的组合问题。

故安排方案共有：(,15)(1571,15)54264RC C ∞=+-= （种）♦ 另解：因为允许0i y =，所以问题转化为长度为1的15条线段中间有14个空，再加上前后两个空，共16个空，在这16个空中放入6个“＋”号，每个空放置的“＋”号数不限，未放“＋”号的线段合成一条线段，求放法的总数。

从而不定方程的整数解共有：212019181716(,6)(1661,6)54264654321RC C ⨯⨯⨯⨯⨯∞=+-==⨯⨯⨯⨯⨯（组） 即共有54 264种安排方案。

4.求下列函数的母函数: {(1)}n n -；（参见课本51页）母函数为：2323000222()(1)(1)2(1)(1)(1)n n nn n n x x x G x n n x n n x nx x x x ∞∞∞====-=+-=-=---∑∑∑； ♦ 方法二：()()()()()2202222002222023()(1)00121121nn n n n n n n n n G x n n x x n n x x n n x x x x x x x x x x ∞∞-==∞∞+==∞+==-=++-"=++=""⎛⎫⎛⎫== ⎪ ⎪-⎝⎭⎝⎭=-∑∑∑∑∑5.求下列函数的母函数:{(2)}n n +；（参见课本51页）母函数为：232300023()(2)(1)(1)(1)(1)n n nn n n x x x x G x n n x n n x nx x x x ∞∞∞===-=+=++=+=---∑∑∑。

♦ 方法二：()()()()()()()()00002121000023223()(2)1211111121111111131n n nn n n n n n n n n n n n n G x n n x n n x n x x x x x x x x x x x x x x x x x x x ∞∞∞∞====∞∞∞∞++++=====+=++-+-"'"'⎛⎫⎛⎫=--=-- ⎪ ⎪--⎝⎭⎝⎭"'⎛⎫⎛⎫=--=-- ⎪ ⎪----⎝⎭--⎝⎭-=-∑∑∑∑∑∑∑∑6．利用递推关系求下列和：0(2)nn k S k k ==+∑ （参见课本第92页）显然，1(2)n n S S n n --=+，同理对应的齐次方程的特征根为1，特解为(1)n n S A A ==，非齐次方程的特解为：*232()nS n Bn Cn D Bn Cn Dn =++=++， 所以，非齐次方程的通解为：32n S Bn Cn Dn A =+++，初始条件为：01230,3,11,26S S S S ====，代入上式，可得00S A ==，13S B C D A =+++=，284211S B C D A =+++=，3279326S B C D A =+++=，解得：0A =，13B =，32C =，76D =， 所以 32137(1)(27)3266n n n n S n n n ++=++= ♦ 方法二：显然，1(2)n n S S n n --=+，类似可得，12(1)(1)n n S S n n ---=-+，两式相减得12221n n n S S S n ---+=+，同理可得12322(1)1n n n S S S n ----+=-+，两式再相减得123332n n n n S S S S ----+-=，同理得1234332n n n n S S S S -----+-=，两式再相减，可得关于n S 的齐次定解问题：1234012346400,3,11,26n n n n n S S S S S S S S S -----+-+=⎧⎨====⎩ 由（1）知，方程的通解为：23n S A Bn Cn Dn =+++，代入初始条件得：00S A ==，13S A B C D =+++=，224811S A B C D =+++=，3392726S A B C D =+++=，解得：7310,,,623A B C D ====， 故 23731(1)(27)6236n n n n S n n n ++=++= ♦ 方法三（快速求系数） 通解为：0123(1)(1)(2)2!3!n n n n n n S A A n A A ---=+++， 初始条件：01230,3,11,26S S S S ====，代入得00A =，013A A +=，012211A A A ++=，01233326A A A A +++=，解得：00A =，13A =，25A =，32A =所以，(1)(1)(2)(1)(27)3522!3!6n n n n n n n n n S n ---++=++=7．利用递推关系求下列和：0(1)(2)n n k S k k k ==++∑ （参见课本第92页） 显然，1(1)(2)n n S S n n n --=++，同理对应的齐次方程的特征根为1，特解为(1)n n S A A ==，非齐次方程的特解为：*32432()nS n Bn Cn Dn E Bn Cn Dn En =+++=+++， 所以，非齐次方程的通解为：432n S Bn Cn Dn En A =++++，初始条件为：012340,6,30,90,210S S S S S =====，代入上式，可得00S A ==，16S B C D E A =++++=，21684230S B C D E A =++++=，381279390S B C D E A =++++=，425664164210S B C D E A =++++= 解得：0A =，14B =，32C =，114D =，32E = 所以 ()()()4321231311342424n n n n n S n n n n +++=+++= ♦ 方法二： 显然，1(1)(2)n n S S n n n --=++，类似可得，12(1)(1)n n S S n n n ---=-+，两式相减得1223(1)n n n S S S n n ---+=+，同理可得12323(1)n n n S S S n n ----+=-，两式再相减得123336n n n n S S S S n ----+-=，同理得1234336(1)n n n n S S S S n -----+-=-，两式再相减得12344646n n n n n S S S S S -----+-+=，同理可得123454646n n n n n S S S S S ------+-+=，两式再相减，可得关于n S 的齐次定解问题：123450123451010500,6,30,90,210n n n n n n S S S S S S S S S S S ------+-+-=⎧⎨=====⎩ 其特征方程为：543251010510x x x x x -+-+-=，1x =是五重特征根，所以方程的通解为：234n S A Bn Cn Dn En =++++，代入初始条件得：00S A ==，16S A B C D E =++++=，22481630S A B C D E =++++=， 339278190S A B C D E =++++=，441664256210S A B C D E =++++=， 解得：311310,,,,2424A B C D E =====， 故 ()()()2341233113124244n n n n n S n n n n +++=+++= ♦ 方法三（快速求系数） 通解为：01234(1)(1)(2)(1)(2)(3)2!3!4!n n n n n n n n n n S A A n A A A ------=++++， 初始条件：012340,6,30,90,210S S S S S =====，代入得00A =，016A A +=，012230A A A ++=，01233390A A A A +++=，01234464210A A A A A ++++=解得：00A =，16A =，218A =，318A =，46A =所以，()()()(1)(1)(2)(1)(2)(3)6181862!3!4!1234n n n n n n n n n n S n n n n n ------=++++++=8. 求从1到500的整数中能被3和5整除但不能被7整除的数的个数。