下载文档原格式
概述组合数学在生活中处处可见。
计算单循环、双循环赛制下比赛的场数、构造幻方、一笔画、计算扑克牌游戏中满堂红牌的手数，概率等。
扎根于数学游戏和娱乐中，计算机技术的发展促进了其发展。
解决两类问题：排列的存在性问题（这是根本性问题。
排列集合中的某些元素使其满足某些条件，其排列的存在性并非总是显而易见的，若不存在，那么什么条件下会存在）；排列的计数和分类问题。
（若存在，则会有多种方法实现，需要计数，并将其分类）。
一、棋盘的完美覆盖问题二、切割立方体三、幻方：四、四色问题五、36军官问题来自6个军团的6个军衔的军官，排成方阵，要求每行每列都有各种军衔的军官1名，并且每行每列的军官都是来自不同的军团。
六、最短路径问题组合优化的问题。
（路由选择）七、Nim 取子游戏鸽笼原理（抽屉原则）一、简单形式：把n+1个物体放入n 个盒子中，有一个盒子中至少有2个物体。
证明方法：反证法。
鸽笼原理与反证法的关系，类似于不完全归纳法与数学归纳法的关系。
例1 13个人中至少有两个人的生日在同一个月。
例2 有n 对夫妇，至少选择多少个人，才能保证至少有一对夫妇被选出？变化形式：把n 个物体放入n 个盒子中，每一个盒子中至少有1个物体，那么每一个盒子恰好有1个物体。
把n 个物体放入n 个盒子中，每一个盒子中至多有1个物体，那么每一个盒子恰好有1个物体。
例3 整数列a 1，a 2，〃〃〃〃〃〃，a m 中，一定有若干个连续的数的和能被m 整除。
构造∑==ij j i a b 1，构造所有被m 除所得余数的鸽笼，共有m 个若两个b i 被m 除的余数相同，则其差能被m 整除，现在笼子多一个，不用考虑余数为0的情况（此时已经满足要求）例4 大师11周训练，每天至少下一盘，每周不超过12盘，证明：有连续的若干天，刚好下了21盘棋。
证明：共77天，分别下a 1，a 2，〃〃〃〃〃〃，a 77构造则前i 天共下了∑==ij j i a b 1要证明存在b i ，b j ，使得b i - b j =21构造t i =21+b i ，变成证明存在t i = b j1≤b 1< b 2<〃〃〃〃〃〃<b 77≤13222≤t 1< t 2<〃〃〃〃〃〃<b 77≤153b 与t 混合在一起总共有154个，而结果只能有153个，从而必有两个数相同，但不可能同是t ，或同是b ，因为分别严格增加。
组合数学排列组合（1）格路模型，范德蒙德恒等式
1.排列(permutation)：
从n个不同的元素中，取出r个不重复的元素，按次序排列，称为从n个中取r个的⽆重排列。
排列的个数⽤P(n,r)表⽰或P r n n>=r //⾼中的时候教材教我们A r n ，跟这⾥的⼀样。
P(n,r) = n!/r!
排列的基本问题是“n个不同球放r个不同盒”问题。
2.组合(conmutation)：
从n个不同的元素中，取出r个不重复的元素组成⼀个⼦集⽽不考虑其元素的顺序，称为从n个中取r个的⽆重组合。
组合的个数⽤C(n,r)表⽰或C r n n>=r
C(n,r)=n! / [r!*(n-r)!]
组合的基本问题是“n个不同球放r个相同盒”问题。
两个性质：
|—— C(n,r) = C(n,n-r) //C(8,3)=C(8,5)
|—— C(n,l)*C(l,r) = C(n,r)*C(n-r,l-r) //C(9,5)*C(5,2)=C(9,2)*C(7,3)
3.格路模型与组合恒等式：
组合数学有⼀个研究⽅向就是研究组合恒等式。
格路模型
我们把从（0，0）到（m，n）的路径⽤⼀个形如“xxyxyyxy...xyy”的字符串表⽰。
则字符串长度为m+n，有m个‘x’，n个‘y’。
杨辉三⾓⽤于格路模型
在杨辉三⾓中，第n⾏对应着(a+b)n的系数，第n⾏第r列的数值是C(n,r)
范德蒙德恒等式。
组合数学解析在数学领域中，组合数学是研究离散结构的一门学科，它主要关注于物体的集合以及它们之间的排列、组合和选择方式。
组合数学广泛应用于计算机科学、信息技术、统计学、天文学等多个领域，在许多实际问题的建模和解决中都起到了重要的作用。
一、组合数学的基本概念1. 排列与组合在组合数学中，排列和组合是两个基本的概念。
排列是指一组对象按照一定顺序进行排列的方式，而组合则是指从一组对象中选取一部分对象进行组合的方式。
排列和组合的计算公式为：排列公式：P(n,m) = n!/(n-m)!组合公式：C(n,m) = n!/[(n-m)! * m!]其中，n表示对象的总数，m表示要排列或组合的对象的数量，n!表示n的阶乘。
2. 二项式系数在组合数学中，二项式系数表示的是两个数的二项式展开系数，它也是组合数学中的重要概念。
二项式系数的计算公式为：C(n,m) = n!/[(n-m)! * m!]二项式系数在组合数学中起到了非常重要的作用，它们具有许多重要的性质和应用。
二、组合数学的应用领域1. 组合数学在计算机科学中的应用在计算机科学中，组合数学是一门非常重要的学科。
组合数学的许多概念和方法被广泛应用于算法设计、图论、密码学、数据压缩等领域。
例如，在算法设计中，对于排列和组合的问题，组合数学可以提供有效的算法和优化策略。
在密码学中，组合数学的概念被用于设计和分析密码算法的安全性。
2. 组合数学在信息技术中的应用在信息技术领域中，组合数学也扮演着重要的角色。
例如，编码理论中的纠错码和压缩码的设计就依赖于组合数学的概念和方法。
另外，在网络优化、通信网络设计等问题中，组合数学的知识也能够提供宝贵的解决思路。
3. 组合数学在统计学中的应用在统计学中，组合数学可以用于描述和统计样本空间以及事件的可能性。
组合数学中的概率论和统计学概念有紧密的联系，例如样本空间的总数、事件的发生概率等都可以通过组合数学的方法进行计算和分析。
此外，组合数学还在实验设计、随机模型等方面发挥着重要作用。
习题 1（1）基本题：1～9，14，16，19，22～23，29，31 （2）加强题：11～12，17，18，21，28 （3）提高题：13，15，20，24～26，30，32 （4）关联题：10，271-1在1到9999之间，有多少个每位上数字全不相同而且由奇数构成的整数？（解）问题相当于求在相异元素{}9,7,5,3,1中不重复地取1个、2个、…、4个元素的所有排列数，答案为45352515P P P P +++＝5＋20＋60＋120＝2051-2比5400小并具有下列性质的正整数有多少个？（1） 每位的数字全不同； （2） 每位数字不同且不出现数字2与7。
（解）（1）分类统计：①一位正整数有919=P 个；②两位正整数有1919P P ⨯＝81个；③三位正整数有2919P P ⨯＝9×9×8＝648个；④千位数小于5的四位数有3914P P ⨯＝4×9×8×7＝2016个；⑤千位数等于5，百位数小于4的数有28141P P ⨯⨯＝4×8×7＝224个。
由乘法法则，满足条件的数的总个数为9＋81＋648＋2016＋224＝2978（2）仿（1），总个数为17P ＋1717P P ⨯＋2717P P ⨯＋3713PP ⨯＋26131P P ⨯⨯＝7＋49＋294＋630＋150＝11301-3一教室有两排，每排8个坐位，今有14名学生，问按下列不同的方式入座，各有多少种坐法？（1） 规定某5人总坐在前排，某4人总在后排，但每人具体坐位不指定； （2） 要求前排至少坐5人，后排至少坐4人。
（解）（1）5人在前排就座，其坐法数为()58,P ，4人在后排就座，其坐法数为()48,P ，还空7个坐位，让剩下的54514=--个人入坐，就座方式为()57,P 种，由乘法法则，就座方式总数为()58,P ()48,P ()57,P ＝28 449 792 000（2）因前排至少需坐6人，最多坐8人，后排也如此。
《组合数学》教案1章讲解组合数学教案第一章讲解一、教学目标：1.了解组合数学的基本概念和方法2.掌握排列和组合的计算方法3.学会应用排列和组合解决问题二、教学重点：1.排列和组合的基本概念2.排列和组合的计算方法三、教学难点：1.排列和组合的应用问题的解决四、教学准备：1.教材《组合数学》2.课件3.黑板、粉笔五、教学过程：1.导入通过举例引入排列和组合的概念，引发学生对组合数学的兴趣。
例如：小明有5本不同的书，他想从这些书中选出三本看。
那么他有多少种不同的选择方法？2.引入通过引入数学公式引出排列和组合的计算方法以及其应用。
首先引入乘法原理，介绍排列的概念和计算方法。
然后引入除法原理，介绍组合的概念和计算方法。
3.排列的概念和计算方法从实际问题中引出排列的概念，如小红有4个不同的糖果，她想把这些糖果排成一排，一共有多少种不同的排列方法？然后介绍排列的计算方法，如何计算排列的种数。
4.组合的概念和计算方法从实际问题中引出组合的概念，如小明有8个不同的苹果，他想从中选出3个苹果吃，一共有多少种不同的选择方法？然后介绍组合的计算方法，如何计算组合的种数。
5.排列和组合的应用问题解决通过实际问题的解决引出排列和组合的应用。
如有5个不同的音乐家，要从中选出3人组成一支乐队，一共有多少种不同的组合方法？然后引出组合计数原理，帮助学生解决应用问题。
6.练习和总结让学生通过练习巩固排列和组合的计算方法，解决应用问题。
然后总结排列和组合的基本概念和计算方法。
七、课堂小结通过本节课的学习，我们了解了组合数学的基本概念和计算方法，掌握了排列和组合的计算方法，并学会应用排列和组合解决问题。
八、作业布置布置相关习题作业，巩固所学知识。
九、课后拓展鼓励学生自学相关拓展内容，如组合数学的其他应用等。
以上是《组合数学》第一章的教案讲解，通过本节课的学习，相信学生能够掌握排列和组合的基本概念和计算方法，并能够应用排列和组合解决问题。
1.1 题（宗传玉）从{1，2，……50}中找两个数{a ，b}，使其满足 （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=520 1.2题（王星） 解：（a ）可将5个女生看作一个单位，共八个单位进行全排列得到排列数为： 8！×5！，（b ）用x 表示男生，y 表示空缺，先将男生放置好，共有8个空缺， Y X Y X Y X Y X Y X Y X Y X Y 在其中任取5个得到女生两两不相邻的排列数： C （8，5）×7！×5！（c ）先取两个男生和3个女生做排列，情况如下：6. 若A ，B 之间存在0个男生， A ，B 之间共有3个人，所有的排列应为 P6=C(5,3)*3!*8!*21．若A ，B 之间存在1个男生， A ，B 之间共有4个人，所有的排列应为 P1= C(5,1)*C(5,3)*4!*7!*22．若A ，B 之间存在2个男生，A ，B 之间共有5个人，所有的排列应为 P2=C(5,2)*C(5,3)*5!*6!*23．2．若A ，B 之间存在3个男生，A ，B 之间共有6个人，所有的排列应为 P3=C(5,3)*C(5,3)*6!*5!*24．若A ，B 之间存在4个男生，A ，B 之间共有7个人，所有的排列应为 P4=C(5,4)*C(5,3)*7!*4!*25．若A ，B 之间存在5个男生，A ，B 之间共有8个人，所有的排列应为 P5=C(5,5)*C(5,3)*8!*3!*2 所以总的排列数为上述6种情况之和。
数学中的组合数学数学是一门用于研究数量、结构、空间以及变化等概念的学科，而组合数学则是数学中的一个重要分支。
组合数学涉及到各种离散的对象和计数技巧，是解决实际问题和优化算法的重要工具。
在本文中，我们将探讨组合数学的基本概念、应用和研究领域。
一、基本概念组合数学主要研究离散的对象，如集合、排列、组合等。
其中，组合是组合数学中的一个基本概念。
组合指的是从集合中选取若干元素组成一个子集的方式。
在组合中，元素的顺序并不重要，只要元素相同即可。
例如，从1、2、3、4这四个元素中选取2个元素组成的组合是{1, 2}、{1, 3}、{1, 4}、{2, 3}、{2, 4}、{3, 4}。
在组合数学中，常用的计数方法有排列计数和组合计数。
排列计数指的是对于给定的一组对象，按照一定的规则进行排列，计算排列的总数。
组合计数指的是对于给定的一组对象，从中选取若干个对象组成一个子集，计算子集的总数。
二、应用领域组合数学在许多领域都有着广泛的应用。
以下是几个典型的应用领域：1.密码学密码学是研究加密和解密技术的学科，而组合数学在密码学中扮演着重要的角色。
通过组合数学的方法，可以设计出处理大量数据的密码算法，确保信息的安全性。
2.图论图论是研究图及其性质的学科，而组合数学在图论中也有重要的应用。
通过组合数学的方法，可以研究图的连通性、最短路径等问题，从而优化网络通信、交通规划等领域的算法设计。
3.组合优化组合优化是一种研究在给定限制条件下求解最优解的方法，而组合数学是组合优化中的一个重要工具。
通过组合数学的方法，可以在有限的资源条件下，寻找出最优解，解决诸如旅行推销员问题、背包问题等实际应用中的优化难题。
三、研究领域除了应用领域外，组合数学在学术研究中也有着广泛的应用。
以下是几个典型的研究领域：1.组合图论组合图论是研究图结构及其性质的一个分支学科，主要研究图的最短路径、连通性等组合问题。
通过组合数学的方法，可以分析图的特性，揭示图的结构之间的关系。
组合数学（combinatorial mathematics）有人认为广义的组合数学就是离散数学，也有人认为离散数学是狭义的组合数学和图论、代数结构、数理逻辑等的总称。
但这只是不同学者在叫法上的区别。
总之，组合数学是一门研究离散对象的科学。
随着计算机科学的日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用算法处理离散数据。
狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。
组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化等。
一些有趣的组合数学问题①地图着色问题：对世界地图着色，每一种国家使用一种颜色。
如果要求相邻国家的颜色相异，是否总共只需四种颜色？②船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。
只要船夫不在场，羊就会吃白菜、狼就会吃羊。
船夫的船每次只能运送一种东西。
怎样把所有东西都运过河？③中国邮差问题：由中国组合数学家管梅谷教授提出。
邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这是一个NP完全问题。
④任务分配问题（也称婚配问题）：有一些员工要完成一些任务。
各个员工完成不同任务所花费的时间都不同。
每个员工只分配一项任务。
每项任务只被分配给一个员工。
怎样分配员工与任务以使所花费的时间最少？更详细的解释：1. 组合数学概述组合数学，又称为离散数学，但有时人们也把组合数学和图论加在一起算成是离散数学。
组合数学是计算机出现以后迅速发展起来的一门数学分支。
计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。
组合数学的发展改变了传统数学中分析和代数占统治地位的局面。
现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。
组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。
组合的计算公式原理和方法组合是数学中一个重要的概念，它涉及到从给定的元素集合中选择若干个元素，而不考虑元素的顺序。
在实际生活中，组合的概念被广泛应用于排列组合、概率统计、计算机算法等领域。
本文将从组合的计算公式原理和方法进行详细介绍。
一、组合的定义。
在数学中，组合是指从n个不同元素中取出m(m≤n)个元素的所有不同的选择方式的个数。
一般用C(n,m)表示，即从n个元素中取出m个元素的组合数。
组合数的计算公式为：C(n,m) = n! / (m! (n-m)!)。
其中，n!表示n的阶乘，即n(n-1)(n-2)...1。
m!表示m的阶乘，即m(m-1)(m-2)...1。
n-m表示n与m的差值。
二、组合的计算方法。
1. 递推法。
组合数的计算可以采用递推法，即从已知的组合数推导出新的组合数。
递推法的思路是利用组合数的性质，通过已知的组合数计算出新的组合数。
具体实现方法是利用组合数的性质C(n,m) = C(n-1,m-1) + C(n-1,m)来计算新的组合数。
2. 数学公式法。
组合数的计算也可以采用数学公式法，即直接使用组合数的计算公式进行计算。
这种方法适用于小规模的组合数计算，可以通过计算阶乘和求解差值来得到组合数的值。
3. 动态规划法。
在计算机算法中，组合数的计算可以采用动态规划法。
动态规划法的思路是将大问题分解成小问题，通过保存已计算的结果来避免重复计算，从而提高计算效率。
具体实现方法是使用一个二维数组来保存已计算的组合数值，通过填表的方式逐步计算出所有的组合数值。
三、组合的应用。
1. 排列组合。
在排列组合问题中，组合数的计算是一个重要的环节。
排列组合问题涉及到从给定的元素集合中选择若干个元素，而不考虑元素的顺序。
组合数的计算可以帮助解决排列组合问题，从而得到所有可能的选择方式。
2. 概率统计。
在概率统计中，组合数的计算也是一个重要的内容。
概率统计问题涉及到从给定的元素集合中选择若干个元素，计算出发生某种事件的概率。
组合数学知识点归纳总结组合数学是数学中的一个分支学科，它涉及离散数学的一部分内容。
组合数学与集合论、图论和逻辑学等相关，它主要研究的是有限集合的组合和排列问题。
在实际应用中，组合数学在密码学、计算机科学、经济学等领域有着广泛的应用。
本文将对组合数学中一些重要的知识点进行归纳总结。
一、排列组合排列是指将若干个不同元素按照一定的顺序进行排列，组合是指从若干个元素中取出一部分元素进行组合。
组合数学的基础知识就是排列组合。
其中，排列的计算公式为：$P(n,m) = n!/(n-m)!$组合的计算公式为：$C(n,m) = n!/((n-m)! * m!)$二、二项式系数二项式系数是组合数学中一个重要的概念。
在代数表达式$(a +b)^n$中，展开后的每一项的系数称为二项式系数。
根据二项式定理，二项式系数可以通过组合数的形式进行计算。
具体来说，二项式系数可以表示为：$C(n,m) = C(n-1,m-1) + C(n-1,m)$三、抽屉原理抽屉原理是组合数学中的一个基本原理。
简单来说，抽屉原理指的是当将若干个物体放入较少的抽屉中时，至少存在一个抽屉中放置了多个物体。
抽屉原理在组合数学中有着广泛的应用，它可以帮助我们解决一些排列组合问题。
四、容斥原理容斥原理是组合数学中的另一个重要原理。
容斥原理用于计算两个集合的交集、并集和补集之间的关系。
具体来说，对于两个集合A和B，容斥原理可以表示为：$|A ∪ B| = |A| + |B| - |A ∩ B|$五、生成函数生成函数是组合数学中的一种重要工具。
生成函数用于将一个数列转化为一个多项式函数，从而方便求解数列的性质。
通过生成函数，我们可以迅速得到数列的递推关系式和通项公式。
在组合数学中，生成函数的应用非常广泛，它可以帮助我们解决各种组合问题。
六、图论中的组合数学组合数学在图论中也有着广泛的应用。
例如，图的着色问题、图的哈密顿回路问题、图的连通性等都可以通过组合数学的方法得到解决。
１.１ 从{}5021，，，⋅⋅⋅中找两个数{}b a ,，使其满足 （1） 5||=-b a ；（2）5||≤-b a解：（1）根据5||=-b a 可得 55-=-=-b a b a 或则有种种4545 共有90种。
（2）根据5||≤-b a 得 )50,,2,1(,55{⋅⋅⋅∈+≤≤-b a b a b则：当5≤b 时，有 1=b ， 61≤≤a ， 则有 6种 2=b ， 71≤≤a ， 则有7种 3=b ， 81≤≤a ， 则有8种 4=b ， 91≤≤a ， 则有 9种5=b ， 101≤≤a ， 则有10种当455≤<b 时，有 6=b ， 111≤≤a ， 则有 11种7=b ， 122≤≤a ， 则有 11种. . . . . . . . .45=b ， 5040≤≤a ， 则有11种当5045≤<b 时，有 46=b ， 5041≤≤a ， 则有 10种 47=b ， 5042≤≤a ， 则有 9种48=b ， 5043≤≤a ， 则有 8种49=b ， 5044≤≤a ， 则有 7种50=b ， 5045≤≤a ， 则有 6种故：共 种520)678910(21140=+++++⨯1.2 （1）先把女生进行排列，方案为5！，然后把女生看成1个人和7个男生进行排列，总方案数为5！×8！（2）女生不相邻，则先把男生进行排列，方案为7！再把女生插入男生之间的8个空位种的任意5个，总方案数为7！×58P（3）应该是A 女生x 女生y 女生z B,或是B 女生x 女生y 女生z A 的形式，从5个女生中选出3人进行排列，方案为35P ，考虑A,B 可以换位，方案为2×35P ，然后把这个看成一个整体，和剩下的2个女生，5个男生，一共7个人进行排列，总方案数2×35P ×8！1.3 m 个男生,n 个女生,排成一行,其中m,n 都是正整数,若（a ）男生不相邻（m ≤n+1）； （b ）n 个女生形成一个整体； （c ）男生A 和女生B 排在一起； 分别讨论有多少种方案。
组合数学1一、填空题1．从n 个不相同的元素里,每次取出m 个元素（可以重复）的组合.这样的组合叫做相异元素可重复的组合,其个数为 m n 。
2．从n 个不相同的元素里,每次取出m 个全不相同的元素,并且将这些元素放在圆周上进行排列,即排列好的元素列没有头尾,则其排列的个数为 ()!!n m n m -。
3．从88⨯的棋盘中，取出一个由三个小方格组成的“L ”型,如图问共有 196 种不同的取法.4．计算⎭⎬⎫⎩⎨⎧2n = 121n -- 。
5．计算⎥⎦⎤⎢⎣⎡-1n n = ()12n n - 。
6．计算⎭⎬⎫⎩⎨⎧24= 11 。
7．6321)32(x x x +-中23231x x x 的系数是 1440- . 8、在多项式()7521...x x x +++的展开式中的项534321x x x x 的系数是 420 。
9．不定方程N x a x a x a n n =+++ 2211有整数解的充分必要条件是 ()1,2,0,n a a a N .二、选择题1．8人排队上车，其中A ，B 两人之间恰好有4人，则不同的排队方法数是（ B ）。
A !63⋅ B !64⋅ C !66⋅ D !68⋅2．由一个正方体的三个顶点所构成的正三角形的个数为（ D ）.A 4B 8C 12D 24.3．把15个相同的足球分给4个人，使得每人至少分得3个足球，不同的分法共有（ 16 ）种 A 45 B 36 C 28 D 204．从n 3个相邻的正整数中选出三个数，使它们的和能被3整除，共有不同选法种数为（ C ）.A 33n C ； B 313)(C ； C 333n C ； D 313)(3n n C C +.5．仅由数字1, 2, 3组成的七位数中, 相邻数字均不相同的七位数的个数是 ( D ). A 576 B 504 C 343 D 1926、8次射击，命中3次，其中恰有2次连续命中的情形共有（ A ）种. A 15； B 30 ； C 48 ； D 60.7．设x ，y 均为正整数且y x +≤20，则这样的有序数对),(y x 共有（ A ）个。
A 190B 200C 210D 2208．百位数字不是1且各位数字互异的三位数的个数是 ( A ).A 576B 504C 720D 3369．6321)32(x x x +-中23231x x x 的系数是（B ） A 1440 B –1440 C . 0 D 1三、计算题1．求6321)532(x x x +-的展开式中23231x x x 的系数? 展开后合并同类项，则一共有多少项？2、求()7521...x x x +++的展开式中534321x x x x 的系数? 展开后合并同类项，则一共有多少项？3．求50!中2的最高次幂.4．求)(5x f 的展开式.5．在平面上,对任意自然数n ,连接原点O 与点(,3),n P n n +用)(n f 表示线段n OP 上除端点外的整点个数,试求(1)(2)(2004).f f f +++6．设{1,2,...,2001}A =,是判断是否存在集合A 的分划1234A A A A A =⋃⋃⋃,其中集合(14)i A i ≤≤中各数字的和组成等差数列，并说明理由。
7．试求两个最小正整数n ，使得集合{}n n 3,13,,2,1- 分划为n 个互不相交的,每个子集合只含三个数{},,,z y x 并且z y x 3=+.四、证明题1．证明：()011=-∑≥k n k k C k ,()010=-∑≥k k n r k kC C . 2．证明：在任意给出的1+n （n ≥2）个正整数中必有两个数，它们的差能被n 整除。
3.证明：0)1(02=-∑=nk k n k C k （2>n ） 4．在平面的任意5个整数点(横、纵坐标为整数的点)中,一定存在2个点,使其连线的中点也是整数点.5．证明：在任意给出的1998个自然数1a ，2a ，…，1998a 中，必存在若干个数，它们的和能被1998整除。
组合数学2一、填空题1．在1和2000之间能被6整除但不能被15整除的正整数共有 200 个。
2．令1110()n n n n f x a x a x a x a --=++++,则()f x 的差分表中第1n +(1)n ≥+行为 0 .3．已知递推关系)3(1243321≥-+=---n a a a a n n n n 的一个特征根为2，则其通解为 ),2,1,0(3)2(2321 =+-+=n c c c a n n n n4．设n 是一个正整数，令n Q 表示在},...,2,1{n 中不允许出现两个连续数字的排列方法数，则我们有n Q =()()()! 11-!- 2C ! 1!11121-n 11----+-+--n n n n C n n C n 5．当1≥n 时,我们有n D =()()!!11...!31!21!111n n n ⎪⎭⎫ ⎝⎛-++-+- (其中n D 表示集合},...,2,1{n 的更列的个数)。
6．从1至1000的整数中，有 167 个整数能被5整除但不能被6整除.7．在边长为1的正方形内任意放入5个点，则其中至少有两个点的距离小于22. 二、选择题1．在1和300之间的整数中能被3或5整除的整数共有（ D ）个。
A 100 B 120 C 140 D 1602．递推关系⎩⎨⎧=≥+=-3)1( 2201a n a a n n n 的解为（ D ） A 32+⋅=n n n a B 22)1(++=n n n aC 12)2(++=n n n aD n n n a 2)3(+=3．递推关系⎩⎨⎧=≥+=-3)1( 2201a n a a n n n 的解为（ D ） A 32+⋅=n n n a B 22)1(++=n n n aC 12)2(++=n n n aD n n n a 2)3(+=4．已知0)}({≥n n f 是Fibonacci 数列且21)7(=f ，34)8(=f ，则=)10(f （ A ）A 89B 110C 144D 2885．递推关系)3(4331≥-=--n a a a n n n 的特征方程是（ C ）A 0432=+-x xB 0432=-+x xC 04323=+-x xD 04322=-+x x6．已知),2,1,0(232 =⋅+=n a n n ，则当n ≥2时，=n a （ D ）A 2123--+n n a aB 2123---n n a aC. 2123--+-n n a a D 2123----n n a a7．在32⨯矩形方格纸上，各个小正方形的顶点称为格点，则以格点为顶点的等腰直角三角形的个数为（ C ）.A 24；B 38 ；C 46 ；D 50.8．设x ，y 均为正整数且y x +≤20，则这样的有序数对),(y x 共有（ A ）个。
A 190 B 200 C 210 D 2209．不定方程1722321=++x x x 的正整数解的个数是（ A ）A 26B 28C 30D 3210．设x ，y 均为正整数且y x +≤20，则这样的有序数对),(y x 共有（ A ）个。
A 190 B 200 C 210 D 220三、计算题1．从1至2000的整数中，至少能被2，3，5中的两个数整除的整数有多少个？解：设所求为N ，令}2000,,2,1{ =S ，以A ，B ，C 分别表示S 中能被32⨯，52⨯，53⨯整除的整数所成之集，则53466663133200333 532200053220003532000522000322000 =+⨯-++=⎥⎦⎤⎢⎣⎡⨯⨯+⎥⎦⎤⎢⎣⎡⨯⨯-⎥⎦⎤⎢⎣⎡⨯+⎥⎦⎤⎢⎣⎡⨯+⎥⎦⎤⎢⎣⎡⨯=+---++==CB AC B C A B A C B A CB A N 2．求从1至1000的整数中能被14或21整除的整数的个数。
解：设所求为N ，令}1000,,2,1{ =S ，以A ，B 分别表示S 中能被14和能被21整除的整数所成之集，则95234771 3141000211000141000 =-+=⎥⎦⎤⎢⎣⎡⨯+⎥⎦⎤⎢⎣⎡+⎥⎦⎤⎢⎣⎡=-+==BA B A B A N 4．从1至1000的整数中，有多少个整数能被6整除，但不能被9也不能被15整除？解：设所求为N ，令}1000,,3,2,1{ =S ，以A ，B ，C 分别表示S 中能被6，9，15整除的整数所成之集，则C B A N -=，由容斥原理得CB AC A B A A C A B A A C B A A N +--=-=-= )()( )(因为6与9的最小公倍数为8，6与15的最小公倍数为30，6、9、15这3个数的最小公倍数为90，故166661000=⎥⎦⎤⎢⎣⎡=A ，55181000=⎥⎦⎤⎢⎣⎡=B A ， 33301000=⎥⎦⎤⎢⎣⎡=C A ，11901000=⎥⎦⎤⎢⎣⎡=C B A 从而 89113355166=+--=N3．设0n ,求在平面区域{(,)0,0,}T x y x y xy n =≤且内的整数点(坐标为整数的点)的个数。
解： 令1{(,)0,0}n T x y x n y x =≤≤ 2{(,)0,0}n T x y y n x y=≤≤. 则12T T T =⋃,12{(,)0,0}T T x y x n y n ⋂=≤≤.于是由容斥原理有121212T T T T T T T =⋃=+-⋂ =200[][][]x n y n x N y N n n n x y ≤≤∈∈+-∑∑ =202[][]x n x Nn n x ≤∈-∑.4．一次宴会，7位来宾寄存他们的帽子，在取回他们的帽子时，问有多少种可能使得（1）没有一位来宾取回的是他自己的帽子？（2）至少有一位来宾取回的是他自己的帽子？解：记7个来宾为1A ，2A ，…，7A ，则7个来宾的取帽子方法可看成是由1A ，2A ，…，7A 作成的这样的全排列：如果i A （1≤i ≤7）拿了j A 的帽子，则把i A 排在第j 位，于是（1）没有一位来宾取回的是他自己的帽子的取法种数等于7元重排数7D ，即等于1854。
（2）至少有一位来宾取回的是他自己的帽子的取法种数等于由1A ，2A ，…，7A 作成的至少有一个元保位的全排列数，为318618545040!77=-=-D5．解递推关系：⎩⎨⎧===≥-+=---24,2,8)3( 842210321a a a n a a a a n n n n 解：所给递推关系的特征方程为084223=+--x x x ，特征根为21-=x ，22=x ，23=x 。
