组合数学数学奥赛教练员培训材料_六年级数学奥赛培训

组合数学数学奥赛教练员培训材料由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“六年级数学奥赛培训”。

（一）组合数学

1.几个常用的排列公式

（1）线排列：从n个不同的元素中任取m(mmn)个排成一列，其排列数为An.mAn.m（2）圆排列：从n个不同的元素中任取m(mn)个排成一圈，其排列数为（3）项链排列：从n粒不同的珍珠中任取m(mn)粒用线串成一根项链，得到的不同项链的条数Anm为.2m（4）可重复排列：从n个不同的元素中任取m(mm（可重复取）排成一列，其排列数为n.n)个元素（5）不全相异的元素的全排列：设n个元素可分为k组，每组分别有n1,n2,...,nk个元素，各组内的元素完全相同，不同组的元素互不相同，则这n个元素的全排列数为

n!.n1!n2!...nk!2.几个常用的组合公式

（1）单组组合：从n个不同的元素中任取m(mmn)个并成一组，其组合数为Cn.（2）多组组合：将n个不同的元素分成k组，每组分别有n1,n2,...,nk个元素，则不同的分组方法数为n!.n1!n2!...nk!n1（3）从n个不同元素中任意取m个元素（可重复取）的组合数为Cnm1.3.组合恒等式

下面是大家熟知的组合恒等式

（1）

kkkk1knkCnCn1Cn1 , CnCn.Cnnk1Cn1（nk1)k（2）CnnmkkmkCmCnCnk

(nmk).（3）Ck0nkn2n

(nk1)

（4）(1)k0nkkCn0

(n1)。

4．二项式定理： 设n是正整数，x,y是任意实数，则

kknk(xy)Cnxy.k0n

特别有：设n是正整数，x为任意实数，则(1合恒等式（3），（4））

kkx)Cnx.（分别令x1和x1就可得证组nk0n5.加法原理和乘法原理

加法原理：如果完成一件事情的方法可以分成有n个互不相交的类，且第i类中有mi种方法，则完成这件事情一共有m1m2mn种方法.乘法原理：如果完成一件事情需要分为n个步骤（每个步骤仅完成这件事情的一部分），且第i个步骤有mi种方法，则完成这件事情一共有m1m2mn种方法.6． 两个重要定理

S的子集，则 定理1（容斥原理）设A1,A2,,Am是有限集合|A1A2Am||Ai|i1m1ijm|AiAj|1ijkm|AiAjAk|(1)m1|A1A2Am|.定理2（配对原理）对于两个不具有同类元素的有限集合 A与B，如果存在集合A到集合B上的双射（即一一映射）f，则集合A与B的元素个数相等，即|A||B|.7.抽屉原则

把8件物品任意的放进7个抽屉种，不论怎么放置，则至少有一个抽屉中有两件或两件以上上述物品。这是日常生活中简单而直观的常识，这一常识反映了数学中十分深刻的分类原则。这就是抽屉原则。他是数学中的一个重要原则，把他推广导一般情形就得到如下几种表现形式：

1． 把n1个元素分到n个集合中，那么必有（至少有）一个集合中含有两个或两个以上的元素。

2． 把nm1个元素分到n个集合中，那么必有（至少有）一个集合中含有m1或m1个以上元素。

3． 把n个元素元素分到k个集合中，那么必有（至少有）一个集合中含有元素的个数[]，也必有（至少有）一个集合中含有元素的个数[]。

4． 把q1q2......qnn1个元素分到n个集合中，那么必有（至少有）一个nknki(1in)，在第i个集合中元素的个数qi。

5． 把无穷多个元素分为有限个集合，那么必有（至少有）一个集合中元素个数为无穷。

这几种表现形式很容易用反证法证明。

一般地说，适合应用抽屉原则来解决的数学问题具有如下特征：所给的元素具有任意性。问题的结论是存在性命题。题中常含有“至少有”“必有”“一定有”“不少于”等词语。其结论只是存在，不必确定。

应用抽屉原则解题的本质是把所讨论的问题利用抽屉原则将范围缩小，使之能在一个特定的范围内考虑问题，使问题变得简单而明确。应用抽屉原则解题得基本思想是根据问题的自身特征，洞察问题的本质。先弄清楚对哪些元素进行分类，再找出分类的规律。下面通过具体的例题来介绍构造抽屉的方法。

例题 例1． 求证 1k1C(2n11).nn1k0k1n分析：这是一个组合代数式的求和问题，考虑到和的特征导出相应的转化关系使问题得到解决。

证明：因为

1k1nn1kCnCnk1n1k1k0k01nk1Cn1n1k01n1j Cn1n1j11n1j(Cn11)n1j01(2n11).n1 n说明：这是一个组合恒等式的证明，应用组合数的基本性质证明组合恒等式是常用的方法，其他还有数学归纳法、组合分析法、递推法等。

例2． 求证：（1）Ck0rrknrkrCmCnm(nmr)；

（2）(Ck0knn)2C2n（范德蒙恒等式）

分析：这是一个组合代数式与相应的组合数的关系，从而联想到二项式展开式使问题得到解决。

证明：（1）因为(1x)(1x)所以(nm(1x)nm

nmr0Ck0rnknrrx)(Cx)Cnmx kjmjj0m比较上式两边x的系数得

Ck0rknrkrCmCnm 结论成立。

（2）在上式中令 mrn 即可得证

(Ck0rknn)2C2n。

说明：这是两个有名的组合代数恒等式，该式的证明运用了二项式展开式以及代数运算巧妙的证出结论。事实上有时运用二项式定理及适当的赋值也是证明组合代数式的一种有效的方法。例3．（1996年全国联赛试题）从给定的六种不同颜色中选用若干种颜色，将一个正方体的六个面染色，每面恰染一种颜色，每两个具有公共棱的面染成不同的颜色.则不同的染色方法共有_______种.(注：如果我们对两个相同的正方体染色后，可以通过适当的翻转，使得两个正方体的上、下、左、右、前、后六个对应面的染色都相同，那么，我们就说这两个正方体的染色方案相同.)分析 本题是几何计数问题，可按照一定的标准分类来进行计数，关键是做到不重复、不遗漏.解 因为有公共顶点的三个面互不同色，故至少要用3种颜色，下面分四种情形来考虑.（1）6种颜色都用时，现将染某种固定颜色的面朝上，从剩下5种颜色中取一种颜色1染下底面有C5种方法，余下4种颜色染四个侧面（应是4种颜色的圆排列）有3！种方法.1所以不同的染色方案有C53!30种.5（2）只用5种颜色时，从6种颜色中取5种颜色有C6种方法，这时必有一组对面同色.1从5种颜色中取一种颜色染一组对面，并将它们朝上和朝下，有C5种方法，其余4种颜色染四个侧面（应是4种不同颜色的链排列）有115C53!90种.C6213！种方法.所以不同的染色方案有24（3）只用4种颜色时，从6种颜色中取4种颜色有C6种方法，这时必有两组对面同色，另一组对面不同色，将不同色的一组对面朝上和朝下，并从4种颜色中取两种颜色染上、下底面，有C4种方法，其余两种颜色染四个侧面且使两组对面同色（应是两种不同颜色的4链排列），只有1种方法.所以不同的染色方案有C6C4190种.3（4）只用3种颜色时，从6种颜色中取3种颜色有C6种方法，这时三组对面都同色，3120种.用三种颜色去染它们只有1种方法.所以不同的染色方案有C622综上可知，不同的染色方案共有30＋90＋90＋20＝230种.说明 该问题的处理方法就是要抓住图形特征来进行分类考虑.例4．今有7种颜色的珍珠，共14颗，其中每种颜色的珍珠各2颗；今把这些珍珠分装在7

个珠盒中，使得每个珠盒中各有一个不同颜色的珍珠。证明：不论各盒的珍珠怎样搭配，总可以将这7个珠盒分别放置在一个正7边形的7个顶点上，使得7边形的任意两个相邻顶点处放置的盒中四颗珍珠互不同色。分析：这是一个复杂的组合问题，首先是不管怎样组合，都可找到符合题目要求的一种排列，所以解决问题的关键是对所有的组合情况进行分类考虑，得出相应的结论。

证明：（1）由题目条件，用点v1,v2,.....,v7分别表示这7种颜色，如果一个vi和vj色的珍珠放置在一个盒子中，则在vi和vj间连边，这样得到一个图G。由于同一色的珍珠有两颗，每一颗珍珠都与另一色的一个珍珠放置在同一个盒子中，则图G中的每点恰好发出两条边。从G中的任意一点A出发，沿一条边到B，再由B沿另一条边到C，......依次下去，最后必回到出发点A，这样在图G中必有圈。去掉这个圈，若剩下还有点，依上方法知又将得到新的圈，若称两点圈为“两边形”，则图G的结构只有如下四种情况：

10.一个7边形；

20.一个5边形，一个两边形；

30.一个4边形，一个三角形； 40.一个三角形，两个两边形。

对每种情况进行编号分析：

10.表明每盒珍珠的颜色搭配是：(v1,v7)，(v1,v2)，(v2,v3)，(v3,v4)，(v4,v5)，(v5,v6)，(v6,v7)则依次将(v1,v7)，(v3,v4)，(v5,v6)，(v1,v2)，(v6,v7)，(v4,v5)，(v2,v3)放置在正7边形的7个顶点上是符合题目要求的放置；

20.表明每盒珍珠的颜色搭配是：(v1,v5)，(v1,v2)，(v2,v3)，(v3,v4)，(v4,v5)，(v6,v7)，(v7,v6)则依次将(v1,v5)，(v3,v4)，(v1,v2)，(v6,v7)，(v2,v3)，(v4,v5)，(v7,v6)放置在正7边形的7个顶点上是符合题目要求的放置；

30.表明每盒珍珠的颜色搭配是：(v1,v4)，(v1,v2)，(v2,v3)，(v3,v4)，(v5,v6)，(v6,v7)，(v7,v5)则依次将(v1,v4)，(v2,v3)，(v5,v6)，(v1,v2)，(v6,v7)，(v3,v4)，(v7,v5)放置在正7边形的7个顶点上是符合题目要求的放置；

40.表明每盒珍珠的颜色搭配是：(v1,v3)，(v1,v2)，(v2,v3)，(v4,v5)，(v5,v4)，(v6,v7)，(v7,v6)则依次将(v1,v3)，(v4,v5)，(v6,v7)，(v1,v2)，(v5,v4)，(v2,v3)，(v7,v6)放置在正7边形的7个顶点上是符合题目要求的放置。综上可得所证结论成立。

说明：本问题是将组合问题结合图的思想将其进行合理的分类，从而得到相应的排列方法。

例5．将24个志愿者名额分配给3个学校，则每校至少有一个名额且各校名额互不相同的分配方法共有多少种．

分析：将24个志愿者分配给3个学校可用4条棍子间的空隙代表3个学校，而用表示名额．如

|||| 表示第一、二、三个学校分别有4，18，2个名额。（这也就是通常称的占位法）。也可以用不定方程求解。[解法一] 用4条棍子间的空隙代表3个学校，而用表示名额．如

||||

表示第一、二、三个学校分别有4，18，2个名额．

若把每个“”与每个“|”都视为一个位置，由于左右两端必须是“｜”，故“每校至少有一个名额的分法”相当于在24个“”之间的23个空隙中选出2个空隙插入“｜”，故有C2种． 23253又在“每校至少有一个名额的分法”中“至少有两个学校的名额数相同”的分配方法有31种．

综上知，满足条件的分配方法共有253－31＝222种．

说明：该问题给出了两种解法都是运用了问题转化的方法，把不容易处理的问题转化成熟知的容易理解和处理的问题。这也是数学竞赛中经常使用的方法，要想熟悉运用这一思想方法必须多分析这样的一些相关问题。

例6．方程2x1x2......x103有多少个非负整数解（每个量都为非负整数）？ 分析：由题中条件知左边变量中至多有3个为1，特别是由于x1的系数为2可知x1只能取0，1两种情况，从而得到相应的解决方法。

解： 2x12x1x2......x103 所以 x10,1下面分两种情况考虑

（1）x10 则 x2x3......x103 且 xi0(i2,3,...,10)

取 yixi1，则原方程等价于 y2y3...y1012 且yi1(i2,3,...,10)则

8用隔板法知该方程的解的个数为C1111109165.321

（2）x11，则x2x3......x101 因此x2,x3,......,x10中必有一个为1，其他的是10，这样的解有C99

于是原方程组的非负解的个数为165+9=174（个）。

例7．已知A与B是集合{1,2,3,......,满足：A与B的元素个数相同，且AB100}的两个子集，为空集。若nA时总有2n2B，则集合AB的元素个数最多为多少？

分析：该问题是组合构造，由条件A与B的元素个数相同且若nA时总有2n2B，知|A||B|，且2n2100,从而可知A中的元素不超过49，为此需要进行分类考虑。

解：首先证明|AB|66，只需要证明 |A|33。由分析只需要证明若A是 {1,2,3,......,49}的任何一个34元子集，则必存在nA，使得2n2A。证明如下：将{1,2,3,...,49}分成如下33个集合：

{1,4},{3,8},{5,12}......,{23,48}共12个；{2,6},{10,22},{14,30},{18,38}共4个；{25},{27},{29},...,{49}共13个；{26},{34},{42},{46}共4个。则若A是{1,2,3,......,49}的任何一个34元的子集，从而由抽屉原理可知上述33个集合中至少有一个2元集合中的两个数均属于A，即存在nA，2n2A。所以|A|33。事实上，如取

A{1,3,5,...,23,2,10,14,18,25,27,29,...,49,26,34,42,46},B{2n2|nA}，则A,B满足题中要求，且|AB|66.所以集合AB的元素个数最多为66。

说明 这个问题与例1不一样，该问题是自己由题中条件和结论要构造出符合要求的集合，分类的方法完全不同，这说明研究解决这类问题的技巧很重要.本题根据题中集合A,B所满足的条件，将1，2，....,49进行分类使问题得到解决。.例8.设 x1,x2,......xn为实数，满足 x12x22......xn21。求证：对每一个整数 k2，存在不全为零的整数 a1,a2,......an 使得 |ai|k1.(i1,2,......n)且

|a1x1a2x2......anxn|证明：由柯西不等式

(k1)n nk1222(|x1||x2|......|xn|)2(1212......12)(x1x2......xn)

即 |x1||x2|......|xn|所以 当 0aik1 时有

n

a1|x1|a2|x2|......an|xn|(k1)(|x1||x2|......|xn|(k1)n把区间 [0,(k1)n] 等分为 kn1 个小区间，每个小区间的长度为

(k1)n。由于每个 ai 能取 k 个数，因此 nk1a1|x1|a2|x2|......an|xn| 共有 kn 个数。

由抽屉原则知，必有两个不同的数会落在同一个小区间内。设它们分别为

ai1n1i|xi| 与 ai|xi|

2i1n因此有 |(aiai)|xi||12i1n(k1)n nk1很显然，|aiai|k1,(i1,2,......n)

12aai现在取 ai{i21aiai于是可得 |n12xi0xi0

aixi|i1(k1)n 且 ai 适合 |ai|k1,(i1,2,......n)。结nk1论成立。

例12． 例9.一个国际社团的成员来自六个国家共1978人，用1，2，`````` 1977，1978来编号，试证明：该社团至少有一个成员的编号或与他的两个同胞的编号之和相等或者是其中一个同胞编号的两倍。

证明：可用反证法来证明与本题完全相当的下列问题：把数列1，2，``````，1977，1978 按任意一方式分成六组，则至少有一组具有这样的性质，其中必有一个数或等于同组的其他两个数的和或者等于其中某一个数的两倍。

假设这六组数中的每一组数都不具备上述性质，也就是说每一组数都具备下列性质（记作性质P）：同组中任意两个数的差必不在该组中。因为如果 a,b 连同

ab 都在一组，那么 ab(ab)与假设矛盾。

因 19786329 所以由抽屉原则可以肯定有一组其中至少有330 个数（不妨记为A）现在在A 中任取330个数来，记其中最大的为a1 把a1分别减去其余的329个数得到329个数，它们互不相等且大于0而小于1978。由性质（P）知这329个数不能在A中，即应该属于另外五组中，又329565 所以其余5组中必有一组至少含有上述329个数中的66个数（不妨记为B），从B中取出上述329个数中的任66个，其中最大的一个记为b1 再把b1减去其余的65个数得出65个数任然大于0而小于1978 显然 这65个数不属于 B，当然也不属于A

假如其中的某个数属于 A 即 b1bA，由于 b1,b 分别可写为

b1a1a'，ba1a 其中 a',a都属于A 于是

b1b(a1a')(a1a)aa'。这同A 具备性质（P）矛盾。

这就说明上述65个数必属于另外 四个数组中。

由于 65416 所以至少有一组其中含上述65个数中17个数（记为C）类似上述过程，最后可得一数组F，其中至少有两个数，大数与小数的差是大于0而小于1978的整数，可是它不在A,B,C,D,E,F的任一组中，这显然是一个矛盾的结果。从而说明假设不对，也就是这六组数至少有一组具备性质（P）。即题目结论正确。

例10.设S为凸15边形的所有对角线（就是互不相邻的点的连线）组成的集合，假若将S分成k个互不相交的非空子集合S1,S2,....,Sk适合对任意不同的i,j（1i,jk）至少存两对角线dSi，d'Sj在该凸15边形内部相交，则k的最大值为 解：45 首先15边形的对角线数为

15141590，若k45，则至少有一个集合中只有一条对2角线，不妨设S11，则其他顶点在S1的两侧，如果一边有v个顶点，另一边就有13v个顶点，从而能与S1这一对角线相交的对角线为v(13v)6742，则显然不可能分成题目要求的k个互不相交的非空子集合S1,S2,....,Sk适合对任意不同的i,j（1i,jk）至少存在两相交的对角线dSi，d'Sj，所以k45.现在构造每个集合两条对角线且满足条件，构造如下：

{AiAi2,Ai1Ai8} {AiAi3,Ai2Ai8} {AiAi4,Ai3Ai8}

15，如集合中顶点A的下标大于15就取15的剩余得到相应的顶上述三类集合中i1,2,...,点，显然共有45个子集，且满足要求，所以结论得证。

事实上n2，设S为4n1（或4n3可得相应的结果）个顶点的凸多边形所有对角线的集合，假设可将S分成S1,S2,...Sk互不相交的非空子集的并，且对任意不同的i,j（1i,jk）存在对角线dSi，和d'Sj，d,d'有公共的内交点，则k可取的最大值为什么？（这个问题就是上述问题的一般化）解：最大值是k(n1)(4n1)

事实上|S|2(n1)(4n1)，如果k(n1)(4n1)，则一定存在某个集合Si只有一条对角线设为d（也就是只有一个元素的集合），则不妨设v个顶点在d的一边，另外4n3v个顶点在另一边。，这时与d相交的对角线为v(4n3v)(2n2)(2n1)

由条件知 k(2n2)(2n1)1(n1)(4n1)(n2)(n1)(4n1).矛盾！现在构造满足k(n1)(4n1)的一种分划。把所有顶点标号A1,A2,A3,....,A4n1，令Ai(4n1)Ai 考虑t2,3,...,n，i1,2,3,...,4n1 St,i{AiAit,Ait1Ai2n}，显然其是S的满足k(n1)(4n1)的一种分划，现在我们要证明满足题中条件，也就是任意两个不同的子集中有两个元素相交。考虑两子集Si,t,Si',t'，由于园的对称性，假设i0，对角线d与St,0中对角线没有内交点，则d的两个顶点只能分别同时在如下的3个集合中

{A0,A1,...,At1}，{At,At1,...,A2n}，{A2n,A2n1,...,A4n1}（A0A4n1）

现在要证，对任意集 St',i'中两条对角线至少有一条其两个顶点不同属于上述3个集合中某一个中。事实上，上述三个集合中最多含有2n个连续的顶点，而任意集 St',i'中两条对角线分别为Ai'At'i',Ai't'1Ai'2n 在确定t'，在i'变化时至少有一条对角线上两个端点不在同一集合中。结论得证。

例11.有12k人参加会议，每人都卡好与3k6人握过手，并且对其中任意两人与这两人都握过手的人数皆相同，问有多少人参加会议？

解：设对任意两人与他们握过手的有n人，考虑某个人a，与a握过手的人的全体记为A，与a没握过手的人的全体记为B，由题意|A|3k6，|B|9k7.再考虑bA，则与a,b均握过手的n人都在A中，因此有与b握过手的n人在A中，与b握过手有3k5n人在B中。再考虑cB，则与a,c都握过手的n个人在A中，于是A与B之间的握手数为

(9k7)n(3k6)(3k5n)，则 n(3k6)(3k5)从而

12k1

16n(12k125)(12k121)

12k1由于(3,12k1)1，所以

12k1|257

2则 12k17, 12k157，12k157

经检验，只有 12k157 产生整数解

k3,n6.下面构造一个36点组成的图，图中每点引出15条边，且每一对点与他们相连的均为6个点 则可用 6个完全图K6，再从一个K6图中的每点向另外5个K6图中分别取一组相邻点连边即得。