组合问题

组合问题主要分三个方面讲解：知识篇、方法篇和问题篇。

知识篇：计数原理和计数公式、抽屉原理和平均均值原理、母函数、递推数列。

方法篇：分类和分布、对应方法、算二次方法、递推方法、染色和赋值方法、反证法和利用极端原理、局部调整方法、构造法。

问题篇：组合计数问题、存在性问题及组合中的不等式证明、组合最值问题。

无重复的排列：从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.

第二篇：数学奥赛辅导_第九讲_组合恒等式、组合不等式

数学奥赛辅导   第九讲     

组合恒等式、组合不等式

知识、方法、技能

Ⅰ．组合恒等式

竞赛数学中的组合恒等式是以高中排列组合、二项式定理为基础，加以推广、补充而形成的一类组合问题.组合恒等式的证明要借助于高中常见的基础组合等式.例如

组合恒等式的证明方法有：

①恒等变形，变换求和指标；

②建立递推关系；

③数学归纳法；

④考虑组合意义；

⑤母函数.

Ⅱ．组合不等式

组事不等式以前我们见的不多，在其他一些书籍中组合不等式的著述也很少，但是近年来组合不等式的证明却出现在国内、国际大赛上.例如1993年中国高中数学联赛二试第二大题为：

设A是一个有n个元素的集合，A的m个子集A₁，A₂…，A_m两两互不包含，试证：

（1）

（2）

其中|A_i|表示A_i所含元素的个数，表示n个不同元素取|A_i|的组合数.

再如1998年第39届国际数学奥林匹克竞赛中第二大试题为：

在某一次竞赛中，共有a个参赛选手与b个裁判，其中b≥3，且为奇数.每个裁判对每个选手的评分中只有“通过”或“不及格”两个等级，设k是满足条件的整数；任何两个裁判至多可对k个选手有完全相同的评分. 证明：

因此我们有必要研究组合不等式的证明方法.组合不等式的证明方法有：

1．在集合间建立单射，利用集合阶的不等关系

定理，设X和Y都是有限集，f为从X到Y的一个映射，

（1）若f为单射，则|X|≤|Y|；

（2）若f为满射，则|X|≥|Y|.

2．利用容斥原理

例如：设元素a属于集族{A₁，A₂，…，A_n}的k个不同集合，则在中a被计算了k次，当k≥2时，集合两两的交集共有个.由于

中至少少被计算了k－1次，这样我们得到下面的不等式：

组合不等式（*）可由容斥公式：

删去右边第三个和式起的所有和式得到.

采用这种办法，我们可以从容斥公式得到另外一些组合不等式，只是要注意这些不等式的方向的变化.

3．利用抽屉原则

由于抽世原则的结论本身就是组合不等式关系，所以我们利用抽屉原则，巧妙构造抽屉的方法证明组合不等式.

4．利用组合分析

在复杂的组合计数问题、离散极值问题等问题中，会出现一些组合不等式，这时可运用组合分析方法证明之.

赛题精讲

例1  证明：

【分析】 把，变换求和指标.

【证明】，则

所以

即  ，从而有

.

例2  求证：

证明  设，则由基本恒等式得

    

【说明】注意到a_n中各项的系数均与n无关，且符号正负相同，由此想到a_n与a_n－1之间必定存在着某些联系，且是递推关系.

例3  求证：

【分析】考虑到恒等式，仿例2解决.

【证明】令

因为，，

令   ①

于是由①式得.

这说明{a_n}为等差数列，而a₀=1,a₁=2，故公差d=1，且a_n=n+1 .

【说明】此题运用变换求和指标的方法，找出了a_n，a_n－1，a_n－2之间的线性关系式，再由 初始条件求得a_n.这种利用递推关系求组合数的方法，在解决较复杂的计算或证明组事恒等式时经常用到.

例11：设是集合M的两个划分，又对任何两个不变的子集有求证：并说明等号能否成立？

【证明】令 ，不妨设 因 两两不交，故 中至多有 个 使   .设

        

由 的选取知 从而  

又因        

故       

即       

所以   

    

       若因故

      

       若则 从而 

       下面说明是可以取到的.显然这时为偶数，取则，令

       易验证M的两个划分.

       D₁={{1,2}{3,4}{5,6}{7,8}},  D₂={{1,2}{3,5}{4,6}{7,8}},

       满足题目条件.

       例12：设是正整数，我们说集合{1，2，…，2}的一个排列（）具有性质P，是指在{1，2，…，2－1}当中至少有一个，使得求证，对于任何，具有性质P的排列比不具有性质P的排列的个数多.

（1989，第30届IMO试题6）

【证明】设A为不具有性质P的排列的集合，B为具有性质P的排列的集合，显然为了证明，只要得到就够了.使作容斥原理.

设()中,与相邻的排列的集合为则由容斥原理得

   = 

例13：平面上给定个点，其中任何三点不共线，任意地用线段连接某些点（这些线段称为边），则确保图形中出现以给定点为顶点的阶完全图的条件是图形中的边的条数

       【证明】构造抽屉：每个抽屉里有个相异点，共可得个抽屉，又由于同一条边会在个抽屉里出现，根据抽屉原则知，当时，才能确保有一个抽屉里有条边，而这条边恰好与其中不共线的相异点构成一个阶完全图.

       这就是说，确保图形中出现阶完全图的条件是其中边的条数

       【评述】“完全图”，是图论中的基本概念.（此处从略）

       例14：设为实数，满足求证：对于每一整数，存在不全为零的整数使得并且

       （1987年第28届IMO试题3）

       【证】由柯西不等式得

            

       即

       所以，当时，有

       把区间[0，]等分成个小区间，每个小区间的长度，由于每个能取个整数，因此

共有个正数，由抽屉原则知必有二数会落在同一小区间内，设它们分别是

           与    因此有       ①

很明显，我们有      现在取

这里于是①可表示为这里为整数，适合

       例15：设A是一个有个元素的集合，A的个子集两两互不包含，试证：（1）（2）

其中表示所含元素的个数，表示个不同元素取个的组合数.

（1993年，全国高中数学联赛二试第二大题）

       【分析】若（1）式已证，由柯西不等式立即可得（2）式，因此，关键是证（1）式，又据组合公式知，（1）式等价于

                   ①      所以我们用组合的方法来证明不等式①.

       【证明】（1）对于A的子集我们取补集并取的元素在前，元素在后，作排列

，.       ②  这样的排列共有个.

       显然,②中每一个排列,也是A中的一个排列,若时，对应的排列与对庆的排列互不相同，则所对应的排列总数便不会超过A中排列的总数现假设中对应的某一排列，.    ③

与（）中对应的某一排列②相同（指出现的元素及元素位置都相同），则当时，；当时，，这都与两两互不包含，矛盾.

       由于对应的排列对②互不相同，而A中个元素的全排列有！个，故得

  即

       （2）由上证及柯西不等式，有

       【评述】本题取自著名的Sperner定理：

       设Z为元素，为Z的子集，互不包含，则的最大值为.

       例16：设S={0，1，2，…，N²－1}，A是S的一个N元子集.证明存在S的一个N元子集B,使得集合A+B={中的元素模N²的余数的数目不少于S中元素的一半.                                                         （第40届IMO预选题）

       【证明】设|X|为子集中元素的个数；又为，是的补集；是对个参赛选手有相同的判决，证明 

（1998年第39届IMO试题二）

       【解】设裁判对参赛选手的判决为，其中

             

       则（）中对个参赛选手判决的记录，它是一个长度为的（0—1）序列.

       我们来考虑这个序列中每两个序列的相同的项的总数M.

       一方面,由已知条件每两个序列的相同的项不超过个,故

              ①

       另一方面，设得到个0（通过），个1（不通过），即（）的第个分量中个0，个1，则+=

       由这个分量产生的序列的相同的项有

      

       但且为奇数，因此

      

       故

                 =

       从而        ③

       综合①、②得       即