奥赛组合数学1

组合问题组合问题主要分三个方面讲解：知识篇、方法篇和问题篇。知识篇：计数原理和计数公式、抽屉原理和平均均值原理、母函数、递推数列。方法篇：分类和分布、对应方法、算二次方法、递推方法、染色和赋值方法、反证法和利用极端原理、局部调整方法、构造法。问题篇：组合计数问题、存在性问题及组合中的不等式证明、组合最值问题。无重复的排列：从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，也有一个数不大于