数学特训组合一导学

分类计数原理:nm1种方法，第二类方式有m2种方法，…,第n类方式有mn种方法.不管采取哪法都能完成这件事，则完成这件m1+m2+…+mn.分步计数原理:nm1m2种方nmn种方法，要完成这件事，必须通过每一步，则完成这件事的方法总m1m2…mn.1211344个不同的盒子中的方法数应为C3abcd12的正整数解的个数．(二).几种特殊的排列、组合定义：从n个不同元素中任取r个不同元素仅按元间的相对位置而不分首尾nr—圆排列（或叫环状排列）.r—圆排列数记nKrn（i）（ii）Krn nrrrr

r

Krn,证

nrn个不同元素r—可重复排列.定理：nr—rn种不同的选法，故由乘法原理有，rn.nk组，每一组中的元素是相同的，不同组间的元素是不ini(i=1,2,…,k),n1+n2+…+nk=n.n个元素的全排列称 nknn!，然后分别n!了n!n

!次，所以不全相异元素的全排列数 nknknk—组合nk—ini个元素（i=12, nkk个步骤.nn1Cn1n－n1n2个有

kn（n1+n2+…+nk－1）nk个元素，有

nknk1nn1n2nrn定理：nr—Crn+r－1证：设（a1a2…，ar）是取自{1，2，…，n}r—≤ar

b1=a1b2=a2+1b3=a3+2,…br=a+r－1r设A={（a1,a2…，ar）|ai∈{1，2，…，n}，a1≤a2≤…≤ar}，B={（b1b2,…，br）|bi∈{1，2，…，n+r－1}，b1b2<…<br}.A、B之间存在一一对应，故|A|=|B|=Crn+r－1.(三).组合计数常用方法AA的元素个数.母函数法是一种非常有用的方法.这种方法的最早系统叙述见于Lace在1812年简要地说，母函数方法是将一个有限或无限的数列{ak}={a0a1a2…ak,…}f(x)a0+a1xa2x2+…akxk+… 例如：组合数列C0, ,Cn的母函数是(1x) 因为由二项式定理可得:(1x)n=C0C1x Cnx 函数(1x)n是最常见的母函数,A2,A2

F={A1，A2，…，Ak}（1≤k≤2n10个苹果放入9个抽屉中，无论怎么放，一定有一个抽屉里放了2个或个苹果.这个简单的事实就是抽屉原理，是由德国数学家雷首先提出来的，因此，又称为原理（m>nmn类（m>n）n|mn

n|m时，至少有一类中含有至少m1个元素 n原理三：把m1m2 mnn1个元素分成n类，则存在一个k，使得第k类至少有mk个元素.一般来说，适合应用抽屉原理解决的数学问题具有如下特征：所给的元素具有任意性09个抽屉，可以随意地一个抽屉放几个，也可以让抽屉空着是存在性命题，题目中常含有至少有、一定有、“不少于、存在……”、必然有……”等词语，其结论只要存在，不必确定，即不需要知道第几个抽屉放多少个苹果.XA1A2,,An的并集，即X 集合{A1,A2 ,An}叫做集合X的一个覆盖一个特殊情况是，集族中的任意两个集合都不相交，这时我们称集族X的如果为集合X的划分，则对集合X的计数可通过下列熟知的加法进行|X||A1||A2||A3||An 但是，要找到一个划分并且其中所有子集易于计数并非易事.当集族中至少存在两X的不完全划分.X的不完全划分，显然|X||A1||A2||An

成这项工作的原理就是容斥原理.是十九世纪英国数学家.容斥原理有两个n ,n)为有限集，nn|

||Ai|

|

i|(1)n1|A i

1i

证明：当n1时，设 |结论成立

A2|| BA2|| Bn=k|

Ai||Ak1||

Ai||Ak1| (

A|j AA|j A|| ||kk iik (kj (kj )|k(1)k (k )ik

1i

k |Ai|

|

ki|(1)k|Ai

1ijk

nk1时结论成立AiPiXA1A2An就是至少具有与容斥讨论的计数问题相反，有时需要计算不具有某几个性质中的任何一个性的元素的个数，即|A1A2An|.为此，我们先引入下面的引理.引理1 设A关于全集I的补集为A，则|A||A||I|. n n n

AiAi,AiAi

利用两引理改写③便是筛法nAi(i1,2,nInn |

n

n||I||

||I||Ai|

|

ni|(1)n|A|i

1i

住全体对象中的情形或它们所具有的某种性质加以研究、解决问题的思想方法称为“原理”。性原理的几种表现形式：最小数原理、最大数原理命题一有限个实数中，必有一个最小数(也必有一个最大数)．命题二无限个正整数中一定有最小值。命题三无限个实数中不一定有最大数最小数对于自然数集，有最小数原理若M是自然数集N的任一非空子集(有限或无限均可)M中必有最小的数．最短长度原理最短长度原理1：任意给定两点，所有连接这两点的线中，以直线段的长度为最短；最短长度原理2：在连接一已知点和已知直线或已知平面的点的所有线中，以垂线段的长度为最短。1

CrCnr

Cr1CrCr

CrnCr

mrC CnC CCnn C0Cnn C0C1C2C3 (1)n

Cr

Cr r r rk2．2．二项式定理：(ab)C knkn

，其中n推广的二项式定理：对任意实数0，有(1

Cx(nCx(其中C01，Cn(

,,ak定义：设a0a1a2

式：f(x)aaxax2 axk axk

k

1

xn(

11

k

Cnk1

(x (3)

(x

sinx

(x(2n

cosx

(xX和YfX到YfXYfXYnAinAiAin1i112

定义设Ｇ和Ｆ是两个平面图形．如果图形Ｆ或由图形Ｆ经过有限次的平移、旋转、（１）（２）图形Ｇ覆盖图形Ｅ，图形Ｅ覆盖图形Ｆ，则图形Ｇ覆盖图形Ｆ．定理１如果能在图形Ｆ所在平面上找到一点Ｏ，使得图形Ｆ中的每一点与Ｏ的距离α若图形Ｆ中的每点都在ＡＢ同侧，且对Ａ、Ｂ视αα的弓形Ｇ所覆盖．定义对于图形Ｇ１，Ｇ２，…，Ｇｎ，若图形Ｆ中的每一点都被这组图形中的某个所覆所谓图形Ｆ能嵌入图形Ｇ,RMIR表示一组原像的关系结构（或原像系统xM表RR*，其中自然包含着未知原xx*x*IM1也就相应地把x确定下来。取对数计算、换元、引进坐标系、设计数学模型，构造发