奥赛组合数学1.doc

组合问题组合问题主要分三个方面讲解：知识篇、方法篇和问题篇知识篇：计数原理和计数公式、抽屉原理和平均均值原理、母函数、递推数列方法篇：分类和分布、对应方法、算二次方法、递推方法、染色和赋值方法、反证法和利用极端原理、局部调整方法、构造法问题篇：组合计数问题、存在性问题及组合中的不等式证明、组合最值问题无重复的排列：从n个不同元素中取m（mn）个不同的元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列，因为这个排列中无重复元素，故又叫无重复排列记为：，其中mn，并约定0！=1，特别当m=n时，无重复的组合：从n个不同元素中取m（mn）个不同的元素并成一组，叫做从n个不同元素中取出m个元素的一个组合因为这个组合中无重复元素，故又叫做无重复的组合 记为：=例1：由1,2,3,4,5可以组成多少个无重复数字，并且大于21300的正整数？ 一、 可重复的排列和组合无重复的排列：从n个不同元素中取m个元素（同一个元素允许重复取），按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的可重复排列，这种排列的个数为。

用乘法原理证明可重复组合：从n个不同元素中取m个元素（同一个元素允许重复取），并成一组，叫做从n个不同元素中取出m个元素的可重复组合，这种组合的个数为不全相异元素的全排列：如果n个元素中，分别有个元素相同，且，则这n个元素的全排列称为不全相异元素的全排列，个数记为=例2、将3面红旗、4面蓝旗、2面黄旗依次悬挂在旗杆上，问可以组成多少种不同的标志？多组组合：把n个相异元素分成k（kn）个不同的组合，其中第i组有个元素（），则不同的分组方法的种数为=公式相同，但意义不同例3从n（n>5）名乒乓球选手中选拔出3对选手准备参加双打比赛，问共有多少种不同的方法？ 二、 相异元素的圆排列和项链数圆排列：将n个不同元素不分首尾排成一圈，称为n个相异元素的圆排列，其中排列种数为项链数：将n个不同的珠子用线串成一副项链，则得到的不同项链数当n=1或2时为1，当时，项链数应为对应的圆排列数的一半，即为例4、6位女同学和15位男同学围成一圈跳集体舞，要求每两名女同学之间至少有两名男同学，那么共有多少种不同的围圈跳舞的方法？ 三、 一类不定方程的非负整数解的个数不定方程的非负整数解的个数为例5、求各位数字之和等于11的3位数的个数。

四、 容斥原理容斥原理：设为有限集合，用||表示集合中的元素个数，那么 逐步淘汰原理（筛法公式）设S是有限集合，在S中的补集为 则例6、在小于1000的正整数中，既不被5整除，又不被7整除的数有多少个？（第四届莫斯科奥林匹克试题）例7（伯努利装错信笺问题）有n封不同的信和n个配套的写有收信人地址的信封，现将n封信一对一地套入到n个信封中去，结果发现没有一封信对，问有多少种不同的套法注：本例通常又称为乱序排列问题，所谓乱序排列问题指的是：将n个不同的元素重新排列，使每个元素都不在原来的位置上 置换及其不动点 给定集合X={1,2，···，n},是从X到X上的一一映射，通常记为 ，则称是X上的置换，其中（i）是元素i在映射下的象因为是一一映射，所以实际上是1,2，···,n的一个排列满足的数i称为的一个不动点，由上例立即可得下列结论： 推论：集合X={1,2，···，n }上没有任何不动点的置换的个数是 例8、设是集合X={1,2，···，n }上的置换，将X上没有不动点的置换个数记为，恰有一个不动点的置换个数记为，证明：15届加拿大数学奥林匹克试题）例9、从全体正整数1，2，3，···，中划去3和4的倍数，但其中凡是5的倍数都保留（例如15,20,60，···等都保留），划完后，将剩下的数从小到大排成一个数列：求之值。

例10 、把n个不同的球放入个盒子中去，每盒内的球数不限，求下列情况下无空盒的放法种数： （1）r个盒子互不相同（可辨） （2）r个盒子相同（不可辨） 平均值原理 （1）设是实数，，则中必有一个数不小于A，也有一个数不大于A；（2）设是正实数，，则中必有一个数不小于G，也有一个数不大于G例11、将10个数1,2,3，···，10按任意顺序排列成一个圆圈，证明：其中必有连续相邻的3个数之和不小于18.。