初等代数研究( 第7章 排列组合 )20111013

第七章排列与组合

§1加法原理与乘法原理§2

相异元素不许重复的排列与组合§3相异元素允许重复的排列与组合§4不尽相异元素的排列与组合§5二项式定理§6排列、组合的母函数1/31/20231名称内容分类计数原理分步计数原理定义不同点完成一件事有n类办法,完成一件事有n个步骤,加法原理

做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，在第n类办法中有mn种不同的方法。那麽完成这件事共有N=m1+m2+…

+

mn种不同的方法。乘法原理

做一件事，完成它需要分成n个步骤做第一步有m1种不同的方法，做第二步有m2种不同的方法,做第n步有mn

种不同的方法。那麽完成这件事共有N=m1×m2×…×mn

种不同的方法。只有每一步都完成才能达到目的.每类中的每一种办法,都能达到目的.§1加法原理和乘法原理2例1.书架上放有3本不同的数学书,5本不同的语文书,6本不同的英语书,(1)若从这些书中任取一本,有多少种不同的选法?(2)若从这些书中取数学书、语文书、英语书各一本,有多少种不同的选法?(3)若从这些书中取不同科目的书两本,有多少种不同的选法?（1）共14本书（2）3·5·6=90（3）3·5+5·6+3·6=631/31/20233（1）5名同学报名参加4项活动（每人限报1项），共有种不同的报名方法（2）5名同学争夺4项竞赛冠军，冠军获得者共有种可能基础练习1/31/20234例2.某车站有5个入口处，每个入口处每次只能进一个人，问一小组8个人进站的方案数有多少？1/31/20235§2相异元素不许重复的排列与组合一、相异元素的不重复排列定义1:排列排列数或

定理1:

分析:1/31/20236推论1约定推论2推论3（上标减1的变形）推论4（下标减1的变形）推论5（上、下标同时减1的变形）1/31/20237§2相异元素不许重复的排列与组合例1:求证:(1)(2)1/31/20238二、相异元素的不重复组合定义2组合、

组合数定理2推论3推论4

§2相异元素不许重复的排列与组合1/31/20239组合性质定理3.（1）

（2）

1/31/202310排列与组合的区别和联系：名称排列组合定义种数符号计算公式关系性质

，从n个不同元素中取出m个元素，按一定的顺序排成一列从n个不同元素中取出m个元素，把它并成一组所有排列的的个数所有组合的个数1/31/202311例2证明范德蒙德恒等式：1/31/202312练习：解方程（1）（2）1/31/202313三、相异元素的环状排列定义3从个不同元素中,不重复地任取个元素，不分首尾地依次排成一个环状（或一条封闭曲线），叫做从个不同元素中取出个元素的环状排列，这样取出的所有环状排列的个数叫做从个不同元素中取出的环状排列数.1/31/202314定理4个不同元素的环状全排列的种数是定理5

从个相异元素取出的元环形排列的种数是1/31/202315例4（课本P345）教师2人和学生6人围着一张圆桌就坐，有多少种不同的坐法？若（1）不附任何条件；（2）两位教师必须相邻；（3）两位教师不在相邻位置；（4）学生A在两教师之间。1/31/202316解排列组合问题遵循的一般原则:有序----;无序---2.分类---;分步---3.既有分类又有分步:4.既有排列又有组合:5.先后6.正难7.分类排列组合加法乘法先分类再分步先选后排要不重不漏则反特殊一般四、应用问题举例1/31/202317常见方法:1.(一般适于相邻问题)2.(一般适于不相邻问题)3.(至多、至少、不都等问题)捆绑法插空法排除法1/31/202318解题总结：注意区别“恰好”与“至少”例7从6双不同尺码的鞋子中任取4只，其中恰好有2只鞋子配成一双的不同取法共有（）

(A)480种（B）240种（C）180种（D）120种小结：“恰好有一个”是“只有一个”的意思。“至少有一个”则是“有一个或一个以上”，可用分类讨论法求解，它也是“没有一个”的反面，故可用“排除法”。解：练习：从6双不同尺码的鞋子中任取4只，其中至少有2只鞋子配成一双，不同取法共有

种1/31/202319解题总结：特殊元素（或位置）优先安排例

将5列火车停在5条不同的轨道上，其中列车a不停在第一轨道上，列车b不停在第二轨道上，那么不同的停放方法有（

）（A）120种

（B）96种

（C）78种

（D）72种解：练习：从7盆不同的盆花中选出5盆摆放在主席台前，其中有两盆花不宜摆放在正中间，则一共有_____种不同的摆放方法（用数字作答）。解：a在第二轨道a不在第二轨道1/31/202320解题总结：分组问题例99本不同的书，按下列条件分配，各有多少种分法？（1）分给甲乙丙三人，每人3本；（2）分成三组，每组3本；（3）分成3组，一组5本，另外两组各2本。——注意是否“有序”1/31/202321链接高考1.（2009北京卷文）用数字1，2，3，4，5组成的无重复数字的四位偶数的个数为（）A．8 B．24 C．48 D．120【答案】C2.（2009全国卷Ⅱ文）甲、乙两人从4门课程中各选修2门，则甲、乙所选的课程中恰有1门相同的选法有（A）6种（B）12种（C）24种（D）30种

【答案】：C3.（2010年四川文科）由1、2、3、4、5组成没有重复数字且1、2都不与5相邻的五位数的个数是（A）36（B）32（C）28（D）24【答案】A1/31/2023225.(2006年全国卷Ⅰ理第12题)

设I={1,2,3,4,5}，选择I的两个非空集合A、B，要使B中最小的数大于A中的最大数，则不同的选择方法共有（

）种

A．50B．49C．48D．47

难题！【答案】B【答案】B1/31/202323课堂练习

习题七：2∼5题

1/31/202324一、相异元素允许重复的排列定义4从个不同元素中，允许重复地任取个按一定顺序排成一列，叫做从个不同元素中取出的元素可重复排列（简称重复排列）．这样取出的重复排列的个数，可用符号表示．定理6§3相异元素允许重复的排列与组合1/31/202325例2（课本P351）由数码1，2，3，4，5五个数字，可以组成多少个大于23400的五位数？1/31/202326二、相异元素允许重复的组合定义5从个不同元素里，允许重复地任取个元素，不计順序地并成一组，叫做从个不同元素中取出的元可重复组合（简称重复组合）.这样取出的元素重复组合的个数，可用符号表示.1/31/202327定理7

分析:AB1/31/202328例4(课本P353)展开(x+y+z)5，并合并同类项，一共可以得到多少项？1/31/202329例6(课本P354)（1）将6个相同的有正反面的圆片任意一掷，可能出现多少种不同结果？（2）如果将它们各涂上不同的颜色，仍有正反面，可能掷出多少种不同结果？（1）7种（2）261/31/202330例7（课本P355）四元一次不定方程

x1+x2+x3+x4=6（1）有多少组正整数解？（2）有多少组非负整数解？一般地，一次不定方程x1+x2+…+xr=n（1）正整数解有

组(n≥r)；（2）非负整数解有

组。1/31/202331例8方程

3x1+x2+x3+x4+x5+x6=3

的非负整数解有多少组？1/31/202332一、不尽相异元素的排列定义6把个不尽相异的元素按照一定的顺序排成一列，叫做个不尽相异元素的全排列．定理8如果在n个元素中，有n1个a1

，n2个

a2

，…nk个ak

，那么这n个不尽相异元素的全排列数是§4不尽相异元素的排列与组合1/31/202333例1(课本P357)一个球队与八个球队个比赛一场，问4胜、3负、1平的可能情形有多少种？1/31/202334例2(课本P357)将5个相同的红球和5个相同的白球排成一列，首尾不许同色，共有多少种不同的排法？1/31/202335例3(课本P357)某市有7条南北向的街，5条东西向的街，从西南角的A点到东北角的点B，经最短路程，有多少种不同走法？1/31/202336例4(课本P358)求展开式(a1+

a2

+

···

+

an)r中，含a1r1a2r2

···

anrn的系数（r为正整数，）a1r1a2r2

···

anrn

=a1

···

a1·a2

···a2

···

an···

an1/31/202337例5（课本P358）不定方程

x1+x2+x3+x4=7有多少组正整数解？一般地，一次不定方程x1+x2+…+xr=n（1）正整数解有

组(n≥r)；（2）非负整数解有

组。1/31/202338二、不尽相异元素的组合定义7从n个不尽相异的元素中，取出r（r<n）个元素而不考虑其次序时，叫做n个不尽相异元素中取出r个的组合．§4不尽相异元素的排列与组合1/31/202339例9(课本P361)540不同的正因数有多少个？540=22·33·

5(2+1)·(3+1)·(1+1)=24定理9（见课本P362）1/31/202340一、二项式定理§5二项式定理1/31/202341二项式定理的发现通过探索,13世纪阿拉伯人已经知道两项和的n次方的展开结果:1/31/202342二项式定理的发现为了便于看出规律，我们把它补充完整:1/31/202343二项式定理的发现为了便于研究其中的规律,1544年Stifel把公式中字母的系数提取出来,称为二项式系数.他发现其中每个数是其上方紧邻两数之和.用公式表示为:这个结果，中国数学家杨辉早在13世纪就发现了。1/31/202344二项式定理的发现通过进一步研究，

1654年Pascal发现二项式系数的规律,即通项公式:1713年,Bernoulli对上面的公式给出了证明。45一、二项式定理§5二项式定理定理10二项式展开的通项：

1/31/202346二、二项展开式的性质§5二项式定理性质1：在二项展开式中，与首末两端等距离的任意两项的二项式系数相等----性质2：性质4：如果二项式的幂指数是偶数，中间一项的二项式系数最大；如果二项式的幂指数是奇数，中间两项的二项式系数最大。性质3：(a+b)n的展开式中，奇数项的二项式系数的和等于偶数项的二项式系数和。1/31/202347三、应用举例例2.在的展开式中，有多少个有理项？§5二项式定理例4.设求的值.例8.设n∈N*，求证：能被64整除.1/31/202348三、应用举例§5二项式定理1.在(1+x)10的展开式中，二项式系数最大为

；在(1-x)11的展开式中，二项式系数最大为

。3.（x-2)9的展开式中，第6项的二项式系数是（）

A.4032B.-4032C.126D.-126C4.(a+b)n展开式中，第6项的二项式系数最大，则n是多少?误解

n=10.正解

n=9，10或11.(为什么?)1/31/202349§5二项式定理5.2C02n+C12n+2C22n+C32n+…+2C2k2n+C2k+12n+…+C2n-12n+2C2n2n=________.3·22n-1练习：P380.习题23、25、271/31/202350对于三项和的n次幂，可以如下计算§5二项式定理四、多项式定理1/31/202351具体写出来是§5二项式定理四、多项式定理1/31/202352为了保持展开后的对称性，我们把展开式写成§5二项式定理四、多项式定理1/31/202353把公式中字母的系数提取出来经过仔细观察，我们发现上一三角形可以摞在下一三角形的上方，构成一个正四面体。四面体中的每一个数等于其肩上三个数之和。§5二项式定理四、多项式定理1/31/202354同样的方法，我们可以得到四项和的n次幂的计算公式§5二项式定理四、多项式定理1/31/202355四、多项式定理定理11