习题一（排列与组合）
1．在1到9999之间，有多少个每位上数字全不相同而且由奇数构成的整数？
2．比5400小并具有下列性质的正整数有多少个？ 排交错开来，试求从某一特定引擎开始点火有多少种方案？
15．试求从1到1 000 000的整数中，0出现了几
次？
（1）每位的数字全不同；
（2）每位数字不同且不出现数字2与7； 3．一教室有两排，每排8个座位，今有14名学生，问按下列不同的方式入座，各有多少种做法？
（1）规定某5人总坐在前排，某4人总坐在后排，但每人具体座位不指定；
（2）要求前排至少坐5人，后排至少坐4人。 4．一位学者要在一周内安排50个小时的工作时间，而且每天至少工作5小时， 问共有多少种安排方案？
5．若某两人拒绝相邻而坐，问12个人围圆周就坐有多少种方式？
6．有15名选手，其中5名只能打后卫，8名只能打前锋，2名只能打前锋或后卫，今欲选出11人组成一支球队，而且需要7人打前锋，4人打后卫，试问有多少种选法？
7．求(x?y?2z?w)8展开式中x2y2z2w2项的系数。
8．求(x?y?z)4的展开式。
9．求(x361?x2?x3?x4?x5)10展开式中x2x3x4的系数。
10．试证任一整数n可唯一表示成如下形式： n??aii!,0?ai?i,i?1,2,
i?111．证明nC(n?1,r)?(r?1)C(n,r?1)，并给出组合意义。 12．证明
?nkC(n,k)?nn2?1 。
k?113．有n个不同的整数，从中取出两组来，要求
第一组数里的最小数大于第二组的最大数，问有多少种方案？
14．六个引擎分列两排，要求引擎的点火次序两
16．n个男n个女排成一男女相间的队伍，试问有
多少种不同的方案？
17．n个完全一样的球，放到r个有标志的盒子，
n?r，要求无一空盒，
试证其方案数为?
?n?1?
?r?1?。 ?
18．设n?p???11p22pkk，p1,p2,,pk是k个
素数，
试求能整除尽数n的正整数数目。
19．试求n个完全一样的骰子能掷出多少种不同的方案？
20．凸十边形的任意三个对角线不共点，试求这
凸十边形的对角线交于多少个点？又把所有的对角线分割成多少段？
21．试证一整数n是另一整数的平方的充要条件
是除尽n的正整数的数目为奇数。
22．统计力学需要计算r个质点放到n个盒子里去，
并分别服从下列假定之一，问有多少种不同的图像？假设盒子始终是不同的。
（1）Maxwell-Boltzmann假定：r个质点是不
同的，任何盒子可以放任意个；
（2）Bose-Einstein假定：r个质点完全相同，
每一个盒子可以放任意个。
（3）Fermi-Dirac假定：r个质点都完全相同，
每盒不得超过一个。
23．从26个英文字母中取出6个字母组成一字，
若其中有2或3个母音，
问分别可构成多少个字（不允许重复）？
24
．给出
??n????r?????n?1????r?1???n?2??r?2????n?m??r??m??0??m?1??1????m?2????2????0??m???m?????n?r?1??m??的组合意义。
25．
给出
1
?r??r?1??r?2??????????rrr??????的组合意义。 26．
?n??n?1????????r??r?1?证
明
32．由n个0及n个1组成的字符串，其任意前k个字符中，0的个数不少于1的个数的字符串有多少？
?m??m????????m?1???m???????m?????m ?nn习题二（母函数及其应用）??m?2????0??n??1??n?1??n??0?。
27．对于给定的正整数n，证明在所有
C(n,r)(?r1,2,中，当n, ?n?1,n?1,n为奇数 k????22n 时，
???2，n为偶数C(n,r)取得最大值。
28．（1）用组合方法证明
(2n)!2n 和 (3n)!2n3n 都是整数。 （2）证明
(n2)!(n!)n?1是整数。 29．（1）在2n个球中，有n个相同，求从这2n
个球中选取n个的方案数。
（2）在3n?1个球中，有n个相同，求从这
3n?1个球中选取n个的方案数。
30．证明在由字母表{0,1,2}生成的长度为n的字
符串中，
（1）0出现偶数次的字符串有3n ?12个；
（
2
）
??n?n?0??n?n?2?2???2??2????n?n?q3n?1?q??2?2，其中 q?2??n??2??。
31．5台教学仪器供m个学生使用，要求使用第1台和第2台的人数相等，
有多少种分配方案？
1?．求下列数列的母函数n?(n?0,1,2,) （1）??(?1)n???a??n????；
? （2）{n?5}； （3）{n(n?1)}； （4）{n(n?2)}
2．证明序列C(n,n),C(n?1,n),C(n?2,n),的
母函数为
1(1?xn)?1 。 3．设S?{?e1,?e2,?e3,?e4}，求序列
{an}的母函数。
其中，an是S的满足下列条件的n组合数。 （1）S的每个元素都出现奇数次； （2）S的每个元素都出现3的倍数次；
（3）e1不出现，e2至多出现一次；
（4）e1只出现1、3或11次，e2只出现2、4或5次；
（5）S的每个元素至少出现10次。
4．投掷两个骰子，点数之和为r(2?r?12)，其组合数是多少？
5．投掷4个骰子，其点数之和为12的组合数是多少？
6．红、黄、蓝三色的球各8个，从中取出9个，要求每种颜色的球至少一个，问有多少种不同的取法？
7．将币值为2角的人民币，兑换成硬币（壹分、贰分和伍分）可有多少种兑换方法？ 8．有1克重砝码2枚，2克重砝码3枚，5克重砝码3枚，要求这8个砝码只许放在天平的一端，能称几种重量的物品？有多少种不同的称
2
法？
9．证明不定方程x1?x2?拆数等于n分拆为奇数之和的分拆数。
?xn?r的正整数解
17．求自然数50的分拆总数，要求分拆的每个分项不超过3。
习题三（递推关系）
组的个数为C(r?1,n?1)。
10．求方程x?y?z?24的大于1的整数解的个数。 11
．
设
an??(?Ck?0nn,，2k1．解下列递推关系：
)k其中a0?1，bn??C(n?k,2k?1)，b0?0。
n?an?7an?1?10an?2?0（1）?
a?0,a?11?0k?0试证：
（1）an?1?an?bn?1，bn?1?an?bn； （2）求出{an}、{bn}的母函数A(x)，B(x)。 12．设S?{?e1,?e2,,?ek}，求序列
{pn}的母函数，
其中pn是S的满足下列条件的n排列数： （1）S的每个元素都出现奇数次； （2）S的每个元素至少出现4次； （3）ei至少出现i次(i?1,2,,k)； （4）ei至多出现i次(i?1,2,,k)；
13．把23本书分给甲乙丙丁四人，要求这四个人
得到的书的数量分别不超过9本、8本、7本、6本，问：
（1）若23本书相同，有多少种不同的分法？ （2）若23本书都不相同，又有多少种不同的分法？
14．8台计算机分给3个单位，第一个单位的分配
量不超过3台，第二个单位不超过4台，第三个单位不超过5台，问共有几种分配方案？ 15．用母函数证明下列等式成立：
222 （1）??n??n??0?????1??????n??2n?n???n?； ???? （
2
）
??n?????n?1??????n?m??n?m?1? ?n??n??n?????n?1?。
?16．证明自然数n分拆为互异的正整数之和的分
（2）??an?6an?1?9an?2?01
?a0?0,a1?（3）??an?an?2?0?a0?0,a1?2
（4）??an?2an?1?an?2?a
0?a1?1（5）??an?an?1?9an?2?9an?3
?a0?0,a1?1,a2?22．求由A，B，C，D组成的允许重复的排列中AB至少出现一次的排列数。
3．求n位二进制数中相邻两位不出现11的数的个数。
4．利用递推关系求下列和： n （1）S2n??k
k?0n （2）Sn??k(k?1)
k?0n（3）Sn??k(k?2)
k?0n（4）Sn??k(k?1)(k?2)
k?05．求n位四进制数中2和3必须出现偶数次的数目。
6．试求由a，b，c三个字母组成的n位符号串中不出现aa图像的符号串的数目。
3
7．利用递推关系解行列式：
F1?F2?F3?F4?000
?(?1)n?1Fn?(?1)n?1Fn?1?1a?bab100100a?b0000a?bab16．有2n个人在戏院售票处排队，每张戏票票价
为5角，其中n个人各有一张5角钱，另外n个人各有一张1元钱，售票处无零钱可换。现将这2n个人看成一个序列，从第一个人开始，任何部分子序列内，都保证有5角钱的人不比有1元钱的人少，则售票工作能依次序进行，否则，只能中断，而请后面有5角钱的人先上来买票。前一种情况，售票工作能顺利进行，对应的序列称为依次可进行的。问有多少种这样的序列？
17．用an表示具有整数边长且周长为n的三角形的个数，证明
1a?b8．在n?m方格的棋盘上，放有k枚相同的车，设任意两枚不能相互吃掉的放法数为
Fk(n,m)，证明Fk(n,m)满足递推关系： Fk(n,m)?Fk(n?1,m)?(m?k?1)Fk?1(n?1,m)
9．在n?n方格的棋盘中，令g(n)表示棋盘里正方形的个数（不同的正方形可以叠交），试建立g(n)满足的递推关系。
10．过一个球的中心做n个平面，其中无3个平面过同一直径，问这些平面可把球的内部分成多少个两两无公共部分的区域？
11．设空间的n个平面两两相交，每3个平面有且仅有一个公共点，任意4个平面都不共点，这样的n个平面把空间分割成多少个不重叠的区域？
12．相邻位不同为0的n位二进制数中一共出现了多少个0？
13．平面上有两两相交，无3线共点的n条直线，试求这n条直线把平面分成多少个区域？ 14．证明Fibonacci数列的性质，当n?1时，
n （1）Fn2?1?FnFn?2?(?1)
?an?3?n?1an??n?(?1)2?an?3??4的个数是
当n是偶数
当n是奇数18．（1）证明边长为整数且最大边长为r的三角形
?1r(r?2)??4 ??1(r?1)2??4当r是偶数
当r是奇数 （2）设fn为边长不超过2n的三角形的个数，
gn为边长不超过2n?1的三角形的个
数，求fn和gn的解析表达式。
19．从1到n的自然数中选取k个不同且不相邻的整数，
设此选取的方案数为f(n,k)。
（1）求f(n,k)的递推关系及其解析表达式； （2）将1与n也算作相邻的数，对应的选取
方案数记作g(n,k)，利用f(n,k) 求
（2）F1F2?F2F3? （3）F1F2?F2F3?（
?F2n?1F2n?F22n ?F2nF2n?1?F22n?1?1
4
）
nF1?(n?1)F2? 15．证明： （
1
）
n?2Fn?1?Fn?Fn?4?(n?3)当
n?21时，
g(n,k)。
20．球面上有n个大圆，其中任何两个圆都相交
于两点，但没有三个大圆通过同一点，用an表示这些大圆所形成的区域数，例如，
4
F12? （
F22?2
?F2n? ?Fn当
F时
，
）
n?4