《组合数学》模拟练习题组合数学模拟练习题04一、 填空题1、 红、黄、蓝、白4个球在桌上排成一圈，有 种排法。

2、设P 、Q 为集合，则|P ∪Q| |P| + |Q|.3、0max i nn i≤≤⎧⎫⎛⎫=⎨⎬ ⎪⎝⎭⎩⎭。

4、设S = {1,2,3,4}中仅有2个定位的排列数N(2) = 。

5、依照字典序，排列(4576321)的下一个排列是 。

6.01.nk n k =⎛⎫= ⎪⎝⎭∑ 。

7. 72,0,1,3,1⎛⎫= ⎪⎝⎭.8. 366个人中必有 个人生日相同。

9、 (1,2,3,4)(4)D =的移位排列数。

10、解递推关系 f (r) – 4f (r-1) + 4f (r-2) = 2 r时，应设非齐次的特解为 。

11.的系数为的展开式中，34232641x x x x i i ⎪⎭⎫ ⎝⎛∑= 。

12. 在14个人中至少有 个人为同月份出生。

13. 解常系数线性齐次递推关系的常用方法称为 法 。

14. 记移位排列数为D(n)，则r 定位排列数N(r) = 。

15.数值函数的推迟函数Sk(f)= 。

二、 单项选择题1、数值函数f = (1,1,1,...)的生成函数F(x) =（ ） A 、(1+x)n B 、1－x C 、(1－x)－1D 、(1+x)－n2、递推关系f(n) = 4f(n －1)－4f(n －2)的特征方程有重根2，则（ ）是它的一般解 。

A 、C 12n －1+C 22n B 、(C 1+C 2n)2n C 、C(1+n)2n D 、C 12n +C 22n .3、由6颗不同颜色的珠子可以做成 （ ）种手链。

A 、720B 、120C 、60D 、6 4、=⎪⎭⎫ ⎝⎛-∑=nk kk n 0)1(（ ）。

A 、2nB 、0C 、n2n －1D 、15、按照字典序，排列4517632的下一个排列是 ( ).A 、4571236B 、4517623C 、4576321D 、45213676、当r ≥k 时差分多项式P k (r) =（ ）A 、0B 、⎪⎭⎫ ⎝⎛k r C 、r(r －1)...(r －k+1) D 、!1k7、设F(x),G(x)分别是f 和g 的生成函数，则以下不成立的是（ ） 。

A 、F(x)+G(x) 是f+g 的生成函数B 、F(x)G(x)是fg 的生成函数C 、x r F(x) 是S r (f)的生成函数D 、F(x)－xF(x) 是∇f 的生成函数.8、在无柄茶杯的四周画上四种不同的图案，共有（ ）种画法。

A 、24B 、12C 、6D 、39、=⎪⎭⎫ ⎝⎛∑=nk k n k 1（ ）。

A 、2n B 、0 C 、n2n －1 D 、110、设S={1,2,3,4,5,6,7}，5-组合12367的下一个组合是 ( ).A 、12567B 、12376C 、12467D 、12456 三、 解答题1. 有4个相同的红球，5个相同的白球，那么这9个球有多少种不同的排列方式？2.公司有5台电视机，4台洗衣机，7台冰箱，现要把其中3台电视机，2台洗衣机，4台冰箱选送到展销会，试问有多少种选法？3.设S = {1, 3•2, 3•3, 2•4, 5}是一个多重集，那么由集合S的元素能组成多少个不同的四位数。

4. 09~用这十个数码，可以组成多少个恰有两个重复数码的三位数？5. 设S ={a, b, c, d, e}，求S的所有3－组合(按字典序排列)。

6. 设集合S ={1, 2, 3, 4}，按照字典序写出排列3124后的所有全排列。

7.试求在1到300之间那些不能被3, 5和7中任何一个整除的整数个数。

8. 数1, 2, 3, 4, 5, 6, 7, 8的全排列中，有4个数字在原来位置上，另外4个不在原来位置上的错排数目。

9. 一人在8小时内加工了40个零件，已知他在第一个小时内加工了6个零件，而最后一个小时内加工了4个零件。

证明一定存在连续的两个小时，这两个小时内至少加工了10个零件。

10. 证明在边长为2的正方形内任意5点必有两点，其距离不超过2。

11. 设数值函数 f = {1,7,72,73,...}, g ={1,6,62,63,...}, 求卷积f * g 的生成函数。

12. 用生成函数求下式之和：123123n n n n n n ⎛⎫⎛⎫⎛⎫⎛⎫⋅+⋅+⋅++⋅ ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭⎝⎭13. 解非齐次递推关系1201693,20,1n n n a a a n a a --++=≥⎧⎨==⎩14. 解齐次递推关系120181601,0n n n a a a a a ---+=⎧⎨=-=⎩15.一教室有两排座位，每排8个，今有14名学生，5人总坐在前排，4人总在后排，问学生入座有几种方式？16. 将字母a,b,c,d,e,f,g 排成一行，使得模式beg 和cad 都不出现的排列总数是多少？17. 按照字典序写出集合S ={1,2,3,4}的前面12个全排列。

18. 求8个字母A 、B 、C 、D 、E 、F 、G 、H 的全排列中只有4个元素不在原来位置上的排列数。

19. 某次会议有10个代表参加，每一位代表至少认识其余9位中的一位，则10位代表中至少有两位代表认识的人数相等。

20. 求数值函数f = {1,－3,32,－33,...}的生成函数.21. 设初始值h(0) = 0, h(1) = 1，求解递推关系 h(n) = 5h(n －1)－6h(n －2). (n = 2,3,...)组合数学模拟练习题参考答案一、 填空题1、6；2、≤；3、2n n ⎛⎫⎪⎡⎤ ⎪ ⎪⎢⎥⎣⎦⎝⎭； 4、6 ；5、4612357.6、2 n ；7、420；8、2；9、9 ； 10、2012222rr rp p r p r ++11、60； 12、2； 13、特征方程； 14、)(r n D r n n -⎪⎭⎫ ⎝⎛- ；15、⎩⎨⎧≥--≤≤kr k r f k r )(100.二、 单项选择题1、C ；2、B ；3、C ；4、B ；5、D ；6、B ；7、B ；8、C ；9、C ； 10、D ；三、 解答题1. 解：设有限多重集S = {4•红球，5•白球}， 则9-重复排列数为：9!4!5!= 126.即9个球有126种不同的排列方式. 2. 解：547.324⎛⎫⎛⎫⎛⎫⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭电视机有种选法；洗衣机有种选法；冰箱有种选法由乘法法则得，5472100.324⎛⎫⎛⎫⎛⎫⨯⨯= ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭共有种选法3. 解：从多重集{1, 3•2, 3•3, 2•4, 5}产生 无重复的四位数有：45P 个；有1个2-重复的四位数有：344!122!⎛⎫⎛⎫ ⎪ ⎪⎝⎭⎝⎭个；有2个2-重复的四位数有：34!22!2!⎛⎫ ⎪⎝⎭个；有1个3-重复的四位数有：244!113!⎛⎫⎛⎫ ⎪ ⎪⎝⎭⎝⎭个；共有120 + 216 + 18 + 32 = 386个四位数。

4. 解：991,2;11⎛⎫⎛⎫ ⎪ ⎪⎝⎭⎝⎭第位重复有991,3;11⎛⎫⎛⎫⎪ ⎪⎝⎭⎝⎭第位重复有 992,3;11⎛⎫⎛⎫⎪ ⎪⎝⎭⎝⎭第位重复有99324311⎛⎫⎛⎫= ⎪ ⎪⎝⎭⎝⎭共有个重复数码的三位数.5. 解：S ={a , b , c , d , e }，按组合生成算法S 的所有3－组合：abc －>abd －>abe －>acd －>ace －>ade －>bcd －>bce －>bde －>cde6. 解：按照字典序排列算法，集合S ={1, 2, 3, 4}的3124后全排列为：3124－>3142－>3214－>3241－>3412－>3421－>4123－>4132－>4213－>4231－>4312－>43217. 解：令A 1,A 2和A 3分别表示1到300之间能被3, 5和7整除的整数集合，则有123300300300||100,||60,||42,357A A A ⎡⎤⎡⎤⎡⎤======⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦121323300300300||20,||14,||8353757A A A A A A ⎡⎤⎡⎤⎡⎤⋂==⋂==⋂==⎢⎥⎢⎥⎢⎥⋅⋅⋅⎣⎦⎣⎦⎣⎦123300||2357A A A ⎡⎤⋂⋂==⎢⎥⋅⋅⎣⎦根据容斥原理知：123||300(1006042)(20148)2138.A A A ⋂⋂=-+++++-=8. 解：求8个数字全排列中只有4个数字不在原来位置上，其余4个数字保持不动，相当于4个数字的移位排列，其数目为：)8(.91412)2416121(24)!41!31!21!111(!4)4(分=+-=+-=+-+-=D故8个数字的全排列中只有4个数字不在原来位置上的排列数为63032456789!4!4!8)4(48=⋅⋅⋅⋅⋅=⋅=⎪⎭⎫ ⎝⎛D9. 解：去掉首尾两个小时，在其余6个小时内加工了30个零件,把这6个小时分成3个“连续的两个小时”（抽屉），根据抽屉原理：一定存在连续的两个小时，这两个小时内至少加工了10个零件。

10. 解：把边长为2的正方形，分成4个边长为1的小正方形，这4个小正方形组成4个抽屉，根据抽屉原理：正方形内任意5点必有两点落入一个小正方形内，而小正方形内两点间距离不超2(对角线长)，所以正方形内必有两点，其距211. 解：数值函数f = {1,7,72,73,...}的生成函数223323()1777...1(7)(7)(7)...1.(|7|1)17F x x x x x x x x x=++++=++++=<-数值函数f = {1,6,62,63,...}的生成函数223323()1666...1(6)(6)(6)...1.(|6|1)16F x x x x x x x x x=++++=++++=<-所以卷积 f * g 的生成函数为1(16)(17)x x --. 12. 解：设数值函数{,,,,,}0123n n n n n f n ⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫= ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭其生成函数23()(1)0123n n n n n n n F x x x x x x n ⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫=+++++=+ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭两边对x 求导211()23(1)123n n n n n n F x x x n x n x n --⎛⎫⎛⎫⎛⎫⎛⎫'=+⋅+⋅++⋅=+ ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭⎝⎭令 x = 1 得1232123n n n n n n n n -⎛⎫⎛⎫⎛⎫⎛⎫+⋅+⋅++⋅= ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭⎝⎭13. 解：特征方程为：x 2 + 6x + 9 = 0 解得特征根为- 3, - 3. 因此齐次通解 (A + Br) (-3) r设非齐次的特解为 C , 代入递推关系式有 C + 6C + 9C = 3所以特解为316C =非齐次的通解3()(3)16r r a A Br =+-+为一般解，由边界条件得30163()(3)116A A B ⎧+=⎪⎪⎨⎪+-+=⎪⎩解此线性方程组得唯一解 31,1612A B =-=- 因此所求的解为313(3)(3)161216r r r a r =----+14. 解：特征方程为：x 2－8x + 16 = 0 解得特征根为4, 4.因此 a r = (A + Br)4r 为一般解，由边界条件得1()40A AB =-⎧⎨+=⎩解此线性方程组得唯一解 A = －1, B = 1因此所求的解为 (1)4rra r =-+15. 解：由5人总坐在前排，在前排选5个座位，有C 85 5!种坐法；由4人总坐在后排，在后排选4个座位，有C84 4!种坐法；在余下的7个座位中选5个座位，给余下的5人坐，有C75 5!种坐法；所以学生入座共有C85 5! C84 4! C75 5! = 28449 792 000种方式.16 . 解：仅有beg模式，或cad模式的排列数都是P(5,5)=5!(将模式捆在一起视为一个元素，再和其余4个元素构成5个元素的全排列)。