《组合数学》试题

组合数学期末试题期末试卷2012—2013学年第二学期课程：组合数学专业：数学与应用数学年级：2010本试卷共2页满分：100分考试时间：120分钟考试方式：闭卷一、填空题（本大题共8小题，每小题2分，共16分）1、将5个苹果分给3个小孩，有_______种不同的分法.2、多项式()4012324x x x x +++中项22012x x x ??的系数是 .3、22件产品中有2件次品，任取3件，恰有一件次品方式数为________.4、Fibbonacci 数F(9)= .5、6()x y +所有项的系数和是________.6、含3个变元,,x y z 的一个对称多项式包含9个项，其中4项包含x ，2项包含xyz ，1项包含常数项，求包含xy 的项有个.7、在{1，2，3，4,5,6}全排列中，使得只有偶数在原来位置的排列方式数为 .8、把某英语兴趣班分成两个小组，甲组有2名男同学，5名女同学；乙组有3名男同学，6名女同学，从甲乙两组均选出3名同学来比赛，则选出的6人中恰有1名男同学的方式数 .二、单项选择题（本大题共8小题，每小题3分，共24分）9、在一次聚会上有15位男士和20位女士，则形成15对男女一共有多少种方式数（）A 、20!5!B 、20!15!C 、2015D 、152010、某年级的课外学科小组分为数学、语文二个小组，参加数学小组的有23人，参加语文小组的有27人；同时参加数学、语文两个小组的有7人。

这个年级参加课外学科小组人数（）。

B 、57C 、43D 、1111、组合式???? ??50120与下列哪个式子相等？（）A 、???? ??60120B 、???? ??50119+???? ??49119C 、512???? ??49120D 、???? ??4911912、从1至1000的整数中，有多少个整数能被5整除但不能被6整除？（）A 、167B 、200C 、166D 、3313、商店有六种饮料供选择，若小明每天至少和一种饮料（喝过的不再选择），5天里把全部饮料都喝过，则有多少种不同的安排？（）A 、9B 、16C 、90D 、180014、...0110p q p q p q r r r +++= ??? ??? ???-????????（）min{,}r p q ≤。

《组合数学》练习卷1. 有4个相同的红球，5个相同的白球，那么这9个球有多少种不同的排列方式？2. 公司有5台电视机，4台洗衣机，7台冰箱，现要把其中3台电视机，2台洗衣机，4台冰箱选送到展销会，试问有多少种选法？3. 设S = {1, 3∙2, 3∙3, 2∙4, 5}是一个多重集，那么由集合S 的元素能组成多少个不同的四位数。

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

5. 证明在边长为2的正方形内任意56. 解非齐次递推关系1201693,20,1n n n a a a n a a --++=≥⎧⎨==⎩ 7.一教室有两排座位，每排8个，今有14名学生，5人总坐在前排，4人总在后排，问学生入座有几种方式？8. 将字母a,b,c,d,e,f,g 排成一行，使得模式beg 和cad 都不出现的排列总数是多少？9. 某次会议有10个代表参加，每一位代表至少认识其余9位中的一位，则10位代表中至少有两位代表认识的人数相等。

组合数学练习卷参考答案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. 解：令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 ⋂⋂=-+++++-=5. 解：把边长为2的正方形，分成4个边长为1的小正方形，这4个小正方形组成4个抽屉，根据抽屉原理：正方形内任意5点必有两点落入一个小正方形内，而小正方形内两点间对角线长)6. 解：特征方程为：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 =----+ 7. 解：由5人总坐在前排，在前排选5个座位，有C 85 5!种坐法；由4人总坐在后排，在后排选4个座位，有C 84 4!种坐法；在余下的7个座位中选5个座位，给余下的5人坐，有C 75 5!种坐法；所以学生入座共有C 85 5! C 84 4! C 75 5! = 28 449 792 000种方式.8 . 解：仅有beg 模式，或cad 模式的排列数都是P(5,5)=5!(将模式捆在一起视为一个元素，再和其余4个元素构成5个元素的全排列)。

组合数学之染色与覆盖例1．有一次车展共36个展室，如下图，每个展室与相邻的展室都有门相通，入口和出口如图所示。

参观者 （填“能”或“不能”）从人口进去，不重复地参观完每个展室再从出口出来。

解：答：不能；如图将展室黑白相间染色，入口为白色，出口也是白色，而走遍36个展室，从白到黑，再从黑到白，共走了35步，最后应该走到黑格，而出口仍然是白格，矛盾，所以无法完成。

例2．棋盘由下图所示的9个小圆圈排列而成，用1~9编号，在3号和9号的小圆圈中各方一枚棋子，分别代表警察和小偷。

若两个小圆圈之间有线相连，则棋子可以从其中一格走入另一格，现在由警察先走，两人轮流，每人每次走一步，每步可以从一格走到有线相连的临格之中。

如果在6步之内警察走入小偷所在的格子中，就算警察抓住了小偷而立功获胜；如果警察走了6步还没有抓住小偷，就算他失职而失败。

问警察应如何取胜。

解：警察先从3走到1，则小偷从9走到7（或8）；第2步，警察走到2，小偷走到6（或9）； 第3步，警察走到3，小偷走到7或8；第4步，警察走到4，小偷走到9；第5步，警察6，小偷无论是走到7（或8），警察在第6步一定可以获胜。

例3．空间六点任三点不共线，任四点不共面，成对地连接它们得到十五条线段，用红色或蓝色染这些线段（一条线段只染一种颜色），求证：无论这么染，总存在一个同色的三角形。

解：设六点为A 、B 、C 、D 、E 、F ，从A 点出发的五条线段AB 、AC 、AD 、AE 、AF 中至少有3条是同色的，不妨设AB 、AC 、AD 为红色，我们再看△BCD 的三边，如果都是蓝色，那么存在同为蓝色的△BCD ，若△BCD 中有一条边不是蓝色，而是红色，不妨设BC 是红色，则AB 、AC 、BC 都是红色，这是一个红色三角形。

所以总存在一个同色的三角形。

例4．下图是由14个大小相同的方格组成的图形，试问 （“能”或“不能”）剪裁成7个由相邻两个方格组成的长方形。

组合数学试题集一.简单题目可以根据需要改成选择题或者填空题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 ++++++=的整数解的组数。

图论与组合数学期末复习试题含答案组合数学部分第1章排列与组合例1：1)、求⼩于10000的含1的正整数的个数；2、)求⼩于10000的含0的正整数的个数；解：1)、⼩于10000的不含1的正整数可看做4位数,但0000除外.故有9×9×9×9－1＝6560个.含1的有：9999－6560=3439个2)、“含0”和“含1”不可直接套⽤。

0019含1但不含0。

在组合的习题中有许多类似的隐含的规定，要特别留神。

不含0的1位数有19个，2位数有29个，3位数有39个，4位数有49个不含0⼩于10000的正整数有()()73801919999954321=--=+++个含0⼩于10000的正整数9999－7380=2619个。

例2：从[1,300]中取3个不同的数，使这3个数的和能被3整除，有多少种⽅案？解：将[1,300]分成3类：A={i|i ≡1(mod 3)}={1,4,7,…,298},B={i|i ≡2(mod 3)}={2,5,8,…,299},C={i|i ≡0(mod 3)}={3,6,9,…,300}.要满⾜条件，有四种解法：1)、3个数同属于A;2)、3个数同属于B ；3)、3个数同属于C;4)、A,B,C 各取⼀数；故共有3C(100,3)+1003=485100+1000000=1485100。

例3：（Cayley 定理：过n 个有标志顶点的数的数⽬等于2-n n ）1）、写出右图所对应的序列；2）、写出序列22314所对应的序列；解：1）、按照叶⼦节点从⼩到⼤的顺序依次去掉节点（包含与此叶⼦节点相连接的线），⽽与这个去掉的叶⼦节点相邻的另外⼀个内点值则记⼊序列。

如上图所⽰，先去掉最⼩的叶⼦节点②，与其相邻的内点为⑤，然后去掉叶⼦节点③，与其相邻的内点为①，直到只剩下两个节点相邻为⽌，则最终序列为51155.。

2）、⾸先依据给定序列写出（序列长度+2）个递增序列，即1234567，再将给出序列按从⼩到⼤顺序依次排列并插⼊递增序列得到：112223344567。

学科专业代码 081202/081203/430112学科专业名称 计算机应用技术、计算机软件与理论、计算机技术考试科目代码_ 01 考试科目 组合数学 题号一 二 三 四 五 六 七 八 九 十 总分 分数 评卷人（本试卷考试时间为2个小时，卷面分数100分，答案请写在答题本上）一、填空题（本大题共5小题，每小题5分，共25分）1、在35⨯棋盘中选取两个相邻的方格（即有一条公共边的两个方格），有 __________种不同的选取方法。

2、将5封信投入3个邮筒，有_________种不同的投法。

3、含3个变元,,x y z 的一个对称多项式包含9个项，其中4项包含x ，2项包含 xyz ，1项包含常数项，求包含xy 的项有 个.4、由1，2，3，4，5 组成的大于43500的五位数的共有____个。

5、把9个相同的球放入3个相同的盒，不允许空盒，则有_______种不同方式。

三、应用题（本大题共5小题，每题各15分，共75分）6、若有1克砝码3枚，2克砝码4枚，4克砝码2枚，问能称出多少种不同的重量？各有多少方案？7、 某学者每周上班6天工作42小时，每天工作的小时数是整数，且每天工作时间不少于6小时也不多于8小时。

今要编排一周的工作时间表，问有多少种不同的编排方法？8、 核反应堆中有α和β两种粒子，每秒钟内一个α粒子分裂成三个β粒子，而一个β粒子分裂成一个α粒子和两个β粒子，若在时刻t = 0时反应堆中只有一个α粒子，问t = 100秒时反应堆中将有多少个α粒子？多少个β粒子？9、 正六面体的8个顶点分别用红蓝两色染色，问有多少种不同的染色方案？刚体运动使之吻合算一种方案。

10、 期末考试有六科要复习，若每天至少复习完一科（复习完的科目不再复习），5天里把全部科目复习完，则有多少种不同的安排？一、填空题（每小题5分，共25分）：专业姓名1、22 解：用加法原则：5×（3-1）+3×（5-1）=22。

组合数学第五版答案【篇一：组合数学参考答案(卢开澄第四版)60页】使其满足（1）|a-b|=5；（2）|a-b|?5；解：（1）：由|a-b|=5?a-b=5或者a-b=-5，由列举法得出，当a-b=5时，两数的序列为（6，1）（7，2）……（50，45），共有45对。

当a-b=-5时，两数的序列为（1，6），（2，7）……（45，50）也有45对。

所以这样的序列有90对。

（2）：由题意知，|a-b|?5?|a-b|=1或|a-b|=2或|a-b|=3或|a-b|=4或|a-b|=5或|a-b|=0；由上题知当|a-b|=5时有90对序列。

当|a-b|=1时两数的序列有（1，2），（3，4），（2，1）（1，2）…（49，50），（50，49）这样的序列有49*2=98对。

当此类推当|a-b|=2，序列有48*2=96对，当|a-b|=3时，序列有47*2=94对，当|a-b|=4时，序列有46*2=92对，当|a-b|=0时有50对所以总的序列数=90+98+96+94+92+50=5201.2题 5个女生，7个男生进行排列，(a) 若女生在一起有多少种不同的排列？(b) 女生两两不相邻有多少种不同的排列？(c) 两男生a和b之间正好有3个女生的排列是多少？所以总的排列数为上述6种情况之和。

1.3题 m个男生，n个女生，排成一行，其中m,n都是正整数，若(a)男生不相邻(m?n?1); (b)n个女生形成一个整体；(c)男生a和女生b排在一起；分别讨论有多少种方案。

解：(a) 可以考虑插空的方法。

n个女生先排成一排，形成n+1个空。

因为m?n?1正好m个男生可以插在n+1个空中，形成不相邻的关系。

则男生不相邻的排列个数为ppnnn?1m(b) n个女生形成一个整体有n！种可能，把它看作一个整体和m个男生排在一起，则排列数有(m+1)!种可能。

因此，共有n!?(m?1)!种可能。

(c)男生a和女生b排在一起，因为男生和女生可以交换位置，因此有2！种可能，a、b组合在一起和剩下的学生组成排列有(m+n-1)！ (这里实际上是m+n-2个学生和ab的组合形成的)种可能。

计算机科学与技术考试：2021离散数学与组合数学真题模拟及答案(4)1、设f是由群<G；×>到群<G`；*>的同态映射，则Ker（f）是（）。

（单选题）A. G`的子群B. G的子群C. 包含G`D. 包含G试题答案：B2、关于生殖器疱疹错误的是（）。

（单选题）A. 发病时起病缓慢，无明显自觉不适及淋巴结肿大B. 妇科检查见外阴疱疹及浅表溃疡C. 孕妇可发生宫内感染及产道扩散D. 新生儿经产道感染，可引起播散性感染，70％以上死亡E. 生殖器疱疹孕妇应在剖宫产分娩试题答案：A3、S1＝{1，2，...，8，9}，S2＝{2，4，6，8}，S3＝{1，3，5，7，9}，S4＝{3，4，5}，S5＝{3，5}，在条件X⊆S1且X⊄S3下，X与（）集合可能相等。

（单选题）A. X＝S2或S3B. X＝S4或S5C. X＝S1，S2或S4D. X与S1，…，S5中任何集合都不相等试题答案：C4、生殖器疱疹潜伏期为（）。

（单选题）A. 20小时B. 2～7天C. 10天D. 14天E. 1个月试题答案：B5、自然语言理解是人工智能的重要应用领域，下面列举中的（）不是它要实现的目标。

（单选题）A. 理解别人讲的话B. 对自然语言表示的信息进行分析概括或编辑C. 欣赏音乐D. 机器翻译试题答案：C6、某女，26岁，7天前有不洁性交史。

2天前开始出现尿痛、排尿困难。

妇科检查见尿道口肿胀外翻，有黄白色脓液流出，外阴阴道及子宫附件无明显异常。

可能的诊断是（）（单选题）A. 非淋菌性尿道炎B. 淋病C. 非特异性尿道炎D. 滴虫性尿道炎E. 尿道念珠菌病试题答案：B7、专家系统的推理机的最基本的方式是（）。

（单选题）A. 直接推理和间接推理B. 正向推理和反向推理C. 逻辑推理和非逻辑推理D. 准确推理和模糊推理试题答案：B8、为了解决如何模拟人类的感性思维，例如视觉理解、直觉思维、悟性等，研究者找到一个重要的信息处理的机制是（）。

组合数学试题 共 4 页 ，第 1 页电子科技大学研究生试卷（考试时间： 14：30 至 16：30 ，共 2 小时）课程名称 组合数学 教师 卢光辉，张先迪 学时 40 学分 2 教学方式 讲授 考核日期 2006 年 12 月 2 日 成绩 考核方式： （学生填写）一．填空题（每空2分，共22分）1．食品店有三种不同的月饼（同种月饼不加区分），第一种有5个，第二种有6个，第三种有7个， (1) 从中取出4个装成一盒（盒内无序），则不同的装法数有 种 ； (2) 从中取出6个装成一盒（盒内无序），则不同的装法数有 种 ；（3）若将所有的月饼排在一个货架上，则排法数有 种（给出表达式，不必算出数值结果）。

（4）若将所有的月饼装在三个不同的盒子中，盒内有序（即盒内作线排列），盒子不空，则不同的装法数又有 种（给出表达式，不必算出数值结果）。

2．棋盘C 如图1所示，则棋子多项式R (C ) =3．设有足够多的红球、黄球和绿球，同色球不加区分，设从中无序地取出n 个球的方式数为a n ，有序地取出n 个球的方式数为b n ，但均需满足红球的数量为偶，黄球的数量为奇，则(1) 由组合意义写出的{a n }的普通母函数为 ；求和后的母函数为 。

(2)由组合意义写出的{b n }的指数母函数为 ；求和后的母函数为 。

4．（1） 将6个无区别的球放入3个无区别的盒子中且盒子不空的放法数为 。

学 号 姓 名 学 院……………………密……………封……………线……………以……………内……………答……………题……………无……………效……………………图1题……………无效…组合数学试题 共 4 页 ，第 2 页（2）将6个有区别的球放入3个无区别的盒子中且盒子不空的放法数为 。

（已知将5个有区别的球放入3个无区别的盒子中且盒子不空的放法数为25）二、（14 分） 给定重集B = {3·A , 3·B , 4·C ,10·D }。

小学排列问题试题及答案小学排列问题属于组合数学的范畴，是数学竞赛和日常教学中常见的题型。

这类问题主要考察学生的逻辑思维和计算能力。

以下是一些小学排列问题的试题及答案。

# 试题一：数字排列小明有数字卡片1、2、3、4，他想用这些卡片排列成一个四位数。

请问有多少种不同的排列方式？答案：这是一个全排列问题。

全排列是指从n个不同元素中取出m个元素（m≤n），按照一定的顺序排列起来，共有n!/(n-m)!种排列方式。

在这个问题中，n=4，m=4，所以排列方式有4! = 4 × 3 × 2 × 1 = 24种。

# 试题二：字母排列字母A、B、C可以组成多少个不同的三位数？答案：同样，这也是一个全排列问题。

每个位置都可以选择3个字母中的任意一个，因此排列方式有3 × 3 × 3 = 27种。

# 试题三：选择与排列有5个不同的小球，小明想从中选出3个排成一排，有多少种不同的排法？答案：首先，从5个小球中选择3个，这是一个组合问题，组合数为C(5,3)= 5!/(3! × (5-3)!) = 10种。

然后，这3个小球可以以3! = 6种方式排列。

所以，总的排列方式为10 × 6 = 60种。

# 试题四：限制条件排列如果上述5个小球中有2个是相同的，那么小明还能排出多少种不同的排列？答案：由于有2个小球是相同的，我们需要考虑这种情况对排列的影响。

首先，选择3个小球的方式仍然是C(5,3) = 10种。

但是，因为有两个小球是相同的，所以它们的排列方式会减少。

具体来说，排列方式为3!/2! = 3种（因为两个相同的小球可以互换位置，不影响排列的唯一性）。

所以，总的排列方式为10 × 3 = 30种。

# 试题五：环形排列问题8个不同的同学围成一个圆圈，有多少种不同的坐法？答案：环形排列与线性排列不同，因为旋转相同的排列被视为一种。

所以，我们首先计算全排列的数量，然后除以n（n是元素的数量）。

计算机科学与技术考试：2021离散数学与组合数学真题模拟及答案(3)共29道题1、在有理数集合Q上定义的二元运算*：x*y＝x＋y－xy，则Q中满足（）。

（单选题）A. 所有元素都有逆元B. 只有唯一逆元C. ∀x∈Q，x≠1都有逆元x－1D. 所以元素都无逆元试题答案：C2、设谓词P（x）：x是奇数，Q（x）：x是偶数，谓词公式∃x（P（x）∨Q（x））在哪个个体域中为真？（）（单选题）A. 自然数B. 实数C. 复数D. A，B，C均成立试题答案：A3、设f是由群<G；×>到群<G`；*>的同态映射，则Ker（f）是（）。

（单选题）A. G`的子群B. G的子群C. 包含G`D. 包含G试题答案：B4、S1＝{1，2，...，8，9}，S2＝{2，4，6，8}，S3＝{1，3，5，7，9}，S4＝{3，4，5}，S5＝{3，5}，在条件X⊆S1且X⊄S3下，X与（）集合可能相等。

（单选题）A. X＝S2或S3B. X＝S4或S5C. X＝S1，S2或S4D. X与S1，…，S5中任何集合都不相等试题答案：C5、设A＝{1，2，3，4}，在P（A）上规定二元关系如下：R＝{（s，t）：s，t∈P（A）且|s|＝|t|}，则P（A）/R＝（）。

（单选题）A. AB. P（A）C. {{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}D. {{∅}，{{2}}，{{2，3}}，{{2，3，4}}，{A}}试题答案：D6、永真式的否定是（）。

（单选题）A. 永真式B. 永假式C. 可满足式子D. A，B，C均有可能试题答案：B7、设A＝{1，2，3}，则A的二元关系有（）个。

（单选题）A. 23B. 32C. 23×3D. 32×2试题答案：C8、在有理数集合Q上定义的二元运算*：x*y＝x＋y－xy，则Q中满足（）。

（单选题）A. 所有元素都有逆元B. 只有唯一逆元C. ∀x∈Q，x≠1都有逆元x－1D. 所以元素都无逆元试题答案：C9、设A＝{1，2，3，4}，在P（A）上规定二元关系如下：R＝{（s，t）：s，t∈P（A）且|s|＝|t|}，则P（A）/R＝（）。

测 试 题——组合数学一、选择题1. 把101本书分给10名学生，则下列说法正确的是（）A.有一名学生分得11本书B.至少有一名学生分得11本书C.至多有一名学生分得11本书D.有一名学生分得至少11本书2. 8人排队上车，其中A ，B 两人之间恰好有4人，则不同的排列方法是（）A.!63⨯B.!64⨯C. !66⨯D. !68⨯3. 10名嘉宾和4名领导站成一排参加剪彩，其中领导不能相邻，则站位方法总数为（）A.()4,11!10P ⨯B. ()4,9!10P ⨯C. ()4,10!10P ⨯D. !3!14-4.把10个人分成两组，每组5人，共有多少种方法（） A.⎪⎪⎭⎫ ⎝⎛510 B.⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛510510 C.⎪⎪⎭⎫ ⎝⎛49 D.⎪⎪⎭⎫ ⎝⎛⨯⎪⎪⎭⎫ ⎝⎛4949 5. 设x,y 均为正整数且20≤+y x ，则这样的有序数对()y x ,共有（）个A.190B.200C.210D.2206.仅由数字1，2，3组成的七位数中，相邻数字均不相同的七位数的个数是（）A.128B.252C.343D.1927. 百位数字不是1且各位数字互异的三位数的个数为（）A.576B.504C.720D.3368. 设n 为正整数，则∑=⎪⎪⎭⎫ ⎝⎛nk k n 02等于（） A.n 2 B. 12-n C. n n 2⋅ D. 12-⋅n n9. 设n 为正整数，则()k k n k k n 310⎪⎪⎭⎫ ⎝⎛-∑=的值是（） A.n 2 B. n 2- C. ()n 2- D.0 10. 设n 为正整数，则当2≥n 时，∑=⎪⎪⎭⎫ ⎝⎛-n k k k 22=() A.⎪⎪⎭⎫ ⎝⎛3n B. ⎪⎪⎭⎫ ⎝⎛+21n C. ⎪⎪⎭⎫ ⎝⎛+31n D. 22+⎪⎪⎭⎫ ⎝⎛n11. ()632132x x x +-中23231x x x 的系数是（）A.1440B.-1440C.0D.112. 在1和610之间只由数字1，2或3构成的整数个数为（） A.2136- B. 2336- C. 2137- D. 2337- 13. 在1和300之间的整数中能被3或5整除的整数共有（）个A.100B.120C.140D.16014. 已知(){}o n n f ≥是Fibonacci 数列且()()348,217==f f ，则()=10f （）A.89B.110C.144D.28815. 递推关系3143---=n n na a a 的特征方程是（） A.0432=+-x x B. 0432=-+x xC. 04323=+-x xD. 04323=-+x x16. 已知()⋯⋯=⨯+=,2,1,0232n a n n ，则当2≥n 时，=n a （）A.2123--+n n a aB. 2123---n n a aC.2123--+-n n a aD. 2123----n n a a17. 递推关系()⎩⎨⎧=≥+=-312201a n a a n n n 的解为（）A.32+⨯=n n n aB.()221+⨯+=n n n a C.()122+⨯+=n n n a D. ()nn n a 23⨯+= 18. 设()⋯⋯=⨯=,2,1,025n a n n ，则数列{}0≥n n a 的常生成函数是（） A.x 215- B. ()2215x -C.()x 215-D. ()2215x - 19.把15个相同的足球分给4个人，使得每人至少分得3个足球，不同的分法共有（）种A.45B.36C.28D.2020. 多重集{}b a S ⋅⋅=4,2的5-排列数为（）A.5B.10C.15D.2021. 部分数为3且没有等于1的部分的15-分拆的个数为（）A.10B.11C.12D.1322. 设n,k 都是正整数，以()n P k 表示部分数为k 的n-分拆的个数，则()116P 的值是（）A.6B.7C.8D.923. 设A ，B ，C 是实数且对任意正整数n 都有⎪⎪⎭⎫ ⎝⎛⋅+⎪⎪⎭⎫ ⎝⎛⋅+⎪⎪⎭⎫ ⎝⎛⋅=1233n C n B n A n ，则B 的值是（）A.9B.8C.7D.624. 不定方程1722321=++x x x 的正整数解的个数是（）A.26B.28C.30D.3225. 已知数列{}0≥n n a 的指数生成函数是()()t t e e t E 521⋅-=，则该数列的通项公式是（）A.n n n n a 567++=B. nn n n a 567+-=C. n n n n a 5627+⨯+=D. nn n n a 5627+⨯-= 二、填空题1. 在1和2000之间能被6整除但不能被15整除的正整数共有_________个2. 用红、黄、蓝、黑4种颜色去图n ⨯1棋盘，每个方格涂一种颜色，则使得被涂成红色的方格数是奇数的涂色方法共有_______种3. 已知递归推关系()31243321≥-+=---n a a a a n n n n 的一个特征根为2，则其通解为___________4. 把()3≥n n 个人分到3个不同的房间，每个房间至少1人的分法数为__________5. 棋盘⨯⨯⨯⨯⨯⨯⨯的车多项式为___________ 6. 由5个字母a,b,c,d,e 作成的6次齐次式最多可以有_________个不同类的项。

组合数学经典考题难题题目一题目描述：有5个不同的筹码，要将它们分配到4个不同的盒子中，每个盒子至少有一个筹码，问有多少种不同的分配方式？解答：假设有5个不同的筹码分别为A、B、C、D、E，盒子用a、b、c、d来表示。

我们可以列出所有可能的分配情况：- A放入a，B放入b，C放入c，D放入d，E不放入任何盒子- A放入a，B放入b，C放入c，D放入d，E放入任何一个盒子- ...- A放入d，B放入a，C放入b，D放入c，E放入d，其他筹码不放入任何盒子共有5个筹码的排列方式，即5的阶乘，即5! = 5 × 4 × 3 × 2 ×1 = 120。

但是，上面列出的情况中，盒子的顺序并不影响最终的分配方式，因为"盒子a放入A，盒子b放入B"与"盒子b放入B，盒子a 放入A"是同一种分配方式。

所以，我们需要除以盒子的排列方式，即4的阶乘，即4! = 4 × 3 × 2 × 1 = 24。

最后的答案是 5! / 4! = 120 / 24 = 5。

所以，共有5种不同的分配方式。

题目二题目描述：有8个人参加一场比赛，其中只有3个人能够获得奖品。

问有多少种不同的获奖组合？解答：假设参赛的8个人依次编号为1、2、3、4、5、6、7、8。

选出3个获奖人员的组合问题，可以看作是从8个人中选出3个人的问题，即从8个人中不计顺序地选出3个人。

这个问题可以使用组合数的概念来解答。

组合数的计算公式为：C(n, m) = n! / (m! × (n-m)!)，表示从n个不同元素中选取m个元素的组合数。

所以，获奖组合的个数为 C(8, 3) = 8! / (3! × (8-3)!) = 8 × 7 × 6 / (3 × 2 × 1) = 56。

所以，共有56种不同的获奖组合。

组合数学期末考查卷一、选择题。

（每小题3分，共24分）1.在组合数学的恒等式中n k ⎛⎫= ⎪⎝⎭A 11(1)1n n n k k k --⎛⎫⎛⎫+>≥ ⎪ ⎪-⎝⎭⎝⎭B 1(1)1n n n k k k -⎛⎫⎛⎫+>≥ ⎪ ⎪-⎝⎭⎝⎭C 1(1)11n n n k k k -⎛⎫⎛⎫+>≥ ⎪ ⎪--⎝⎭⎝⎭D (1)1n n n k k k ⎛⎫⎛⎫+>≥ ⎪ ⎪-⎝⎭⎝⎭2、14321=++x x x 的非负整数解个数为（ ）。

A.120B.100C.85D.503、()()=94P 。

A. 5B. 8C. 10D. 64、递推关系12432(2)n n n n a a a n --=-+≥的特解形式是（a 为待定系数）（）A 、2n anB 、2n aC 、32n anD 、22nan 5、错排方式数n D =（）A 1(1)n n nD ++-B (1)(1)n n n D ++-C -1(1)n n nD +- D 1(1)(1)n n n D +++-6、将n 个不同的球放入m 个不同的盒子且每盒非空的方式数为（ ）。

Ａ（nm ） Ｂ (),P n m Ｃ ｍ！Ｓ2（ｎ，ｍ） Ｄ（nm ）ｍ！7、有100只小鸟飞进6个笼子，则必有一个笼子至少有（ ）只小鸟。

A 15B 16C 17D 188、若颁发26份奖品给4个人，每人至少有3份，有（ ）种分法A 55B 40C 50D 39二、填空。

（每小题4分，共20分）1、现有7本不同的书，要分给6个同学，且每位同学都要有书，有__________________种不同的分法2、设q 1, q 2,…… ,q n 是n 个正整数，如果将q 1+ q 2+…+q n －n ﹢1件东西放入n 个盒子里，则必存在一个盒子j 0，1≤j 0≤n ，使得第0j 个盒子里至少装有0j q 件东西，我们把该定理称为__________________。

E2-061 网球协会为全体会员排定名次，最强的为第1号，其次为第2号等等．已知，在名次相差高于2的运动员比赛时，总是高名次的运动员获胜．在由1024名最强的选手参加的循环赛中（即参加者为1号选手到1024号选手），按奥林匹克规则进行：每一轮比赛的每对选手都由抽签决定，胜者进入下一轮．因此，每一轮比赛后参赛者将减少一半．这样一来，第十轮后将决出胜者．试问，胜者的最大号码是多少？【题说】第七届（1973年）全苏数学奥林匹克九年级题4．【解】胜者的最大号码是20号．因为不计比他强的选手时，k号选手只可能输给k+1号和k+2号选手，所以，胜1号选手的号数至多为3，胜3号的号数至多为5，…．因此，冠军的号数不可能低于1+2×10=21．但在冠军号数为21时，第一轮比赛后应淘汰1号和2号选手，他们分别败于3号和4号选手；在第二轮中3号，4号被淘汰，5号、6号取胜，等等．依此类推，直到第九轮，在该轮比赛中19号和20号选手应分别战胜17号和18号选手，这样，21号选手将不会进入决赛．下面举一个第20号选手获胜的赛例，全体参赛者按每组512人分成两组，第一组中包括第19号，20号及其他510名较弱的选手，该组的比赛使得第20号选手获胜（显然，这是可能的）．在第二组中有1号至18号选手及其余较弱的选手，在该组比赛中使第18号选手获胜，这只要出现前面所说的情况，是可以作到的：第一轮中3号，4号分别战胜1号，2号；第二轮中5号，6号战胜3号，4号等等；到第八轮，第17号和18号选手战胜15号和16号选手，在第九轮中18号选手战胜17号选手．这样，参加决赛的将是第20号选手和第18号选手，于是，20号选手可能获胜．E2-062 把一个8×8的棋盘（指国际象棋棋盘）剪成p个矩形，但不能剪坏任何一格，而且这种剪法还必须满足如下条件：（1）每一个矩形中白格和黑格的数目相等；（2）令a i是第i个矩形中的白格的个数，则a1＜a2＜…＜a p求出使上述剪法存在的p的最大可能值，同时对这个p求出所有可能的a1，a2，…，a p．【题说】第十六届（1974年）国际数学奥林匹克题4．本题由保加利亚提供．由此可知p≤7．p=7时只有五种可能的组合：第一种组合不可能在棋盘上实现，因为棋盘上剪出的矩形不可能是22格的，其他四种情况都是可以实现的，如上图所示（图中数字表示该块含方格数）．E2－063在一张正方形纸上画出n个边与纸的边平行的矩形，这些矩形中任两个都没有公共内点，证明：如果剪下所有的矩形，那么纸片数不大于n+1．【题说】第十届（1976年）全苏数学奥林匹克十年级题3．【证】设纸片数为k，在每张纸片上标出4个顶点（纸片上可能不止四个顶点），这些顶点每一个都是矩形的顶点，或原正方形的顶点，如果两张纸片上标出的两个顶点实际上是同一个点，那么这一点一定是原来靠在一起的两个矩形的共同顶点．因此4k≤4n+4从而得 k≤n+1E2－064某区学生若干人参加数学竞赛，每个学生得分都是整数，总分为8250，前三名的分数是88、85、80，最低是30分，得同一分数的学生都不超过3人．问至少有多少学生得分不低于60分（包括前三名）？【题说】 1979年全国联赛二试题7．【解】除了前三名外，得分为30～79，总分为8250-（88+85+80）=7997．其中分数为30～59的人至多（每种分数三人），共得（30+31+…+59）×3=4005分，因此至少有7997-4005=3992分分配给60～79分的人．由于（79+78+…+61）×3=3990＜3992，所以60～79的人数至少为3×（79-61+1）+1=58．故得分不低于60分的学生总数为61人（包括前三名）．E2－065一个团体有1982人，在任何4人的小组中，至少有一人认识其他3人，问在此团体中，认识其他所有人的最少人数是多少？【题说】第十一届（1982年）美国数学奥林匹克题1．【解】认识可能是双方的，也可能是单方的．1．假设认识按双向性理解，作一个有1982个点的图G，每点代表一个人，若两人彼此不认识，就将相应两点连一条边，认识者不连．于是，我们的问题变为：已知在此图中，每四点所成之子图，至少有一孤立点，问图中最少有多少个孤立点？设G中有边AB．若又有边CD连结另两点C、D，则A、B、C、D四点所成子图中无孤立点，矛盾．因此G中任一点或者是孤立点，或者与A或B相连．设点C与A相连，则对任一点D，由于A、B、C、D所成子图中有孤立点，所以D不与A、B相连，从而（根据上面所证）D为G的孤立点．于是G中至多有A、B、C三点非孤立点，至少有1979个孤立点，即该团体中至少有1979个人认识其他所有人．2．若认识是单向的，设1982人围成一圆圈，每人皆不认识其右邻，但认识其余的人．容易证明，任4人中都至少有一人认识其他三人，但团体中无一人认识其他所有人，即认识所有其他人的人数最少是0．E2－066设S是边长为100的正方形，L是在S内自身不相交的折线段A0A1，A1A2，…，A n-1A n（A0≠A n）．假定对于边界上每一有两点X、Y，它们之间的距离不大于1，沿折线L，它们之间的距离不小于198．【题说】第二十三届（1982年）国际数学奥林匹克题6．【解】根据题设，对于正方形的顶点S1，S2，S3，S4，在折线L在沿L由A0到A n时，不妨假定先经过L1，并且在L2与L4中，先出现的是L2．将S1S4上的点分为两类：如果Q在A0L2这一段，P在第一类，如果Q在L2A n上，P在第二类．显然S1在第一类，S2在第二类，所以两类都是非空的，这两类可以有公共点（原因见后）．如果P0是公共点，那么另一方面，从Q1沿着L到Q2必须经过L2，而Q1到L2这段长≥以Q1、Q2之间的L的长≥198．Q1、Q2就是要求的点X、Y．最后来说明上面定义的两个类的公共点P0是存在的．设在边S1S4的从S1到S4的方向上，第一类的点最远能延伸到P0，从S4到S1的方E2－067在平面上画出n（n≥2）条直线，将平面分成若干个区域，其中一些区域上涂了颜色，并且任何两个涂色的区域没有相邻的边界．证明：涂色的区域数不超过（n2+n）/3．【题说】第十九届（1985年）全苏数学奥林匹克十年级题4．只有一个公共点的两个区域，不认为是有相邻接的边界．【证】如果所画的直线都互相平行，那么它们将平面分成（n+1）个区域，这时能涂色的区域不超过n个．因为（n2+n）/3=n（n+1）/3≥n（2+1）/3=n所以此时命题成立．设并非所有直线都互相平行，每个区域的边界由若干条位于不同直线上的线段或射线组成，这些线段和射线称为区域的边．每个区域的边数不少于2．用m2表示有两条边的涂色区域的个数；m3表示有三条边的涂色区域的个数，等等，我们用m k表示边数最多的涂色区域的个数．首先证明m2≤n．任何有两条边的区域的边界是由两条射线组成的，并且每条射线只能是一个涂色区域的边界，所有这样的射线不超过2n条（每条直线上的射线不超过两条）．所以有两条边的涂色区域的边数不超过2n，即m2≤n·n条直线中的每一条被分成的区间（线段或射线）数不多于n，所以所有的区间数不超过n2，因而所有区域边的总数也就不超过n2条．由于每个区间至多是一个涂色区域的边，所以2m2+3m3+…+km k≤n2，涂色的区域数m2+m3+…+m k≤n2/3+（2m2+3m3+…+km k）/3≤n/3+n2/3=（n2+n）/3E2－068儿童计数器的三个档上各有十个算珠，如图，将每档算珠分为左右两部分（不许一旁无珠）．现在要左方三档中所表示的三个珠数的乘积等于右方三档中所表示的珠数的乘积．问有多少种分珠法？【题说】 1987年北京市赛高一题5．【解】不妨设左方上中下三档珠数分别为a、b、c，则右方上中下三档珠数分别为10-a、10-b、10-c，依题意得：abc=（10-a）（10-b）（10-c）（1）即 abc=500-50（a+b+c）+5（ab+bc+ca）因1≤a、b、c≤9，且5|abc，故a、b、c三数中至少有一个是5若只有一档珠数为5．不妨设a=5．（1）式化为：bc=（10-b）（10—c）=100-10（b+c）+bc即b+c=10这时b可以取1，2，3，4，6，7，8，9；而c相应取9，8，7，6，4，3，2，1．共得8种分珠法．同理，若b=5（a、c均不等于5），或c=5（a、b均不等于5），也各有8种分珠法．显然a=5，b=5，c=5时，也是一种分珠法（注意：若a、b、c 中有两个是5，则第三个也必然是5）．综上可知，总计共有8+8+8+1=25种分珠法．E2－069五对孪生兄妹参加k个组的活动，若规定：（1）孪生兄妹不在同一组；（2）非孪生关系的任意两个人都恰好共同参加过一个组的活动；（3）有一个人只参加两个组的活动．求k的最小值．【题说】 1987年全国联赛一试题2（5）．原题为填空题．【解】用A、a、B、b、C、c、D、d，和E、e表示五对孪生兄妹．不妨设A只参加两个组的活动，要同时满足（1）、（2），这两组要包含除a外的其余8人，同时每组各为5人（不然，则有一组包含一对孪生兄妹）．由对称性，这两组可以设为（A，B，C，D，E）和（A，b，c，d，e）．再考虑a，为使编组尽可能地少，可在B，C，D，E与b，c，d，e中各取一个（二者非孪生兄妹）编为4组：（B，a，c），（C，a，b），（D，a，e），（E，a，b）最后，将余下没有编在一组的非孪生关系的，每两人编为一组，共8组：（B，d）（B，e）（C，d）（C，e）（D，b）（D，c）（E，b）（E，c）总共14组，所以k的最少值为14．E2－070甲乙两队各出7名队员按事先排好的顺序出场参加围棋擂台赛，双方先由1号队员比赛，负者被淘汰，胜者再与负方2号队员比赛，……直到有一方队员全被淘汰为止，另一方获得胜利，形成一种比赛过程．求所有可能出现的比赛过程的种数．【题说】 1988年全国联赛一试题2（4）．原题为填空题．【解】设甲队胜，则甲队必在前13场比赛中胜7场，可能情况有。

2009 2010学年第二学期组合数学期末试卷 一、填空题（每小题3分，共15分）1、22件产品中有2件次品，任取3件，恰有一件次品方式数为___380 _____.2、6()x y +所有项的系数和是____64 ____.3、把5个不同的球安排到4个相同盒子中，没有空盒的，共有种__10______. 不同方法。

4、不定方程1232x x x++=的非负整数解的个数为____6____.5、若1()f n n =,则2()f n ∆=_______2(1)(2)n n n ++______. 二、选择题（每小题3分，共30分） 1、设A （t ）=nn n=0at ∞∑ 和 B （t ）=nn n=0b t ∞∑ (0b 0≠) 是两个形式幂级数，则A （t ）与 B (t) 的商为 （ A ）。

A.1A(t)=A(t)B (t)B(t)-⋅ B. 1A(t)=A (t)B(t)B(t)-⋅ C.11A(t)=A (t)B (t)B(t)--⋅ D. 1A(t)=(A(t)B(t))B(t)-⋅ 2、某年级的课外学科小组分为数学、语文二个小组，参加数学小组的有23人，参加语文小组的有27人；同时参加数学、语文两个小组的有7人。

这个年级参加课外学科小组人数（ C ）。

A ．50B ．57C ．43D ．113、将11封信放入8个信箱中，则必有一个信箱中至少有（ B ）封信。

A 、1 B 、2 C 、3 D 、44、组合式⎪⎪⎭⎫⎝⎛50120与下列哪个式子相等？（ B ） A 、⎪⎪⎭⎫⎝⎛60120 B 、⎪⎪⎭⎫ ⎝⎛50119+⎪⎪⎭⎫ ⎝⎛49119 C 、512⎪⎪⎭⎫ ⎝⎛49120 D 、⎪⎪⎭⎫⎝⎛491195、在{1，2，3，4,5,6}全排列中，使得只有偶数在原来位置的排列方式数为（ A ）。

A 、 2 B 、 4 C 、 9 D 、 246、若存在一递推关系01124,956(2)n n n a a a a a n --==⎧⎨=-≥⎩则=n a ( A ).A.nn323+⋅ B.nn232+⋅ C.123+⋅n D.11323+++⋅n n7、数列0{}n n ≥的常生产函数是（ D ）。