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

1、第七章 排列与组合 1 加法原理与乘法原理2 相异元素不许重复的排列与组合3 相异元素允许重复的排列与组合4 不尽相异元素的排列与组合5 二项式定理6 排列、组合的母函数9/21/20221名称内容分类计数原理分步计数原理定义不同点完成一件事有n类办法,完成一件事有n个步骤,加法原理 做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，在第n类办法中有mn种不同的方法。那麽完成这件事共有N = m1 + m2 + + mn种不同的方法。乘法原理 做一件事，完成它需要分成n个步骤做第一步有m1种不同的方法，做第二步有m2种不同的方法,做第n步有mn

2、 种不同的方法。那麽完成这件事共有N = m1 m2 mn 种不同的方法。只有每一步都完成才能达到目的.每类中的每一种办法,都能达到目的. 1 加法原理和乘法原理2例1. 书架上放有3本不同的数学书,5本不同的语文书,6本不同的英语书,(1)若从这些书中任取一本,有多少种不同的选法?(2)若从这些书中取数学书、语文书、英语书各 一本, 有多少种不同的选法?(3)若从这些书中取不同科目的书两本, 有多少种 不同的选法?（1）共14本书（2）356=90（3）35+56+36=639/21/20223（1）5名同学报名参加4项活动（每人限报1项），共有 种不同的报名方法（2）5名同学争夺4项竞赛冠

3、军，冠军获得者共有 种可能基 础 练习9/21/20224例2.某车站有5个入口处，每个入口处每次只能进一个人，问一小组8个人进站的方案数有多少？9/21/202252 相异元素不许重复的排列与组合一、相异元素的不重复排列 定义1: 排列 排列数 或 定理1: 分析:9/21/20226推论1 约定 推论2 推论3 （上标减1的变形）推论4 （下标减1的变形）推论5 （上、下标同时减1的变形） 9/21/202272 相异元素不许重复的排列与组合例1:求证:(1) (2)9/21/20228二、相异元素的不重复组合定义2 组合、 组合数定理2推论3推论4 2 相异元素不许重复的排列与组合9/2

4、1/20229 组合性质 定理3.（1） （2 ） 9/21/202210排列与组合的区别和联系：名 称排 列组 合定义种数符号计算公式关系性质 ，从n个不同元素中取出m个元素，按一定的顺序排成一列从n个不同元素中取出m个元素，把它并成一组所有排列的的个数所有组合的个数9/21/202211例2 证明范德蒙德恒等式：9/21/202212练习：解方程 （1） （2）9/21/202213三、相异元素的环状排列定义3 从 个不同元素中,不重复地任取 个元素，不分首尾地依次排成一个环 状（或一条封闭曲线），叫做从 个 不同元素中取出 个元素的环状排 列，这样取出的所有环状排列的个数 叫做从 个不同

5、元素 中取出的环 状排列数. 9/21/202214定理4 个不同元素的环状全排列的种数是定理5 从 个相异元素取出的 元环形排列的种数是9/21/202215例4 （课本P345） 教师2人和学生6人围着一张圆桌就坐，有多少种不同的坐法？若 （1）不附任何条件； （2）两位教师必须相邻； （3）两位教师不在相邻位置； （4）学生A 在两教师之间。9/21/202216解排列组合问题遵循的一般原则:有序- ; 无序- 2. 分类- ; 分步-3. 既有分类又有分步:4. 既有排列又有组合:5. 先 后6. 正难7.分类排列组合加法乘法先分类再分步先选后排要不重不漏则反特殊一般四、应用问题举例9

6、/21/202217常见方法:1. (一般适于相邻问题)2. (一般适于不相邻问题)3. (至多、至少、不都等问题)捆绑法插空法排除法9/21/202218解题总结： 注意区别“恰好”与“至少”例7 从6双不同尺码的鞋子中任取4只，其中恰好有2只鞋子配成一双的不同取法共有（ ） (A) 480种（B）240种 （C）180种 （D）120种小结：“恰好有一个”是“只有一个”的意思。“至少有一个”则是“有一个或一个以上”，可用分类讨论法求解，它也是“没有一个”的反面，故可用“排除法”。解：练习： 从6双不同尺码的鞋子中任取4只，其中至少有2只鞋子配成一双，不同取法共有 种9/21/202219解

7、题总结： 特殊元素（或位置）优先安排例 将5列火车停在5条不同的轨道上，其中列车a不停在第一轨道上，列车b不停在第二轨道上，那么不同的停放方法有（ ）（A）120种 （B）96种 （C）78种 （D）72种解：练习：从7盆不同的盆花中选出5盆摆放在主席台前，其中有两盆花不宜摆放在正中间，则一共有_种不同的摆放方法（用数字作答）。解：a在第二轨道a不在第二轨道9/21/202220解题总结： 分组问题例9. 9本不同的书，按下列条件分配，各有多少种分法？（1）分给甲乙丙三人，每人3本；（2）分成三组，每组3本；（3）分成3组，一组5本，另外两组各2本。注意是否“有序”9/21/202221链接高

8、考1.（2009北京卷文）用数字1，2，3，4，5组成的无重复数字的四位偶数的个数为 （ ）A8B24C48D120【答案】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【答案】A9/21/2022225. (2006 年全国卷理第12题) 设I=1,2,3,4,5，选择I的两个非空集合A、B，要使B中最小的数大于A中的最大数，则不

9、同的选择方法共有（ ）种 A50 B49 C48 D47 难题！【答案】B【答案】B9/21/202223课堂练习 习题七： 25题 9/21/202224一、相异元素允许重复的排列3 相异元素允许重复的排列与组合引例： 用1,2,3这三个数字组成5位数，一共可以组成多少个？9/21/202225一、相异元素允许重复的排列定义4 从n个不同元素中，允许重复地任取m个按一定顺序排成一列，叫做从n个不同元素中取出的m元素可重复排列（简称重复排列）这样取出的重复排列的个数，可用符号 表示定理6 3 相异元素允许重复的排列与组合9/21/202226例2 （课本P351） 由数码1，2，3，4，5五个

10、数字，可以组成多少个大于23400的五位数？9/21/202227二、相异元素允许重复的组合引例： 展开(x+y+z)5，并合并同类项，一共可以得到多少项？例如：9/21/202228二、相异元素允许重复的组合定义5 从n个不同元素里，允许重复地任取 m个元素，不计順序地并成一组，叫做从n个不同元素中取出的m元可重复组合（简称重复组合）.这样取出的m 元素重复组合的个数，可用符号 表示.9/21/202229定理7 分析: A B9/21/202230例4 (课本P353)展开(x+y+z)5，并合并同类项，一共可以得到多少项？9/21/202231例6 (课本P354)（1）将6个相同的有正

11、反面的圆片任意一掷，可能出现多少种不同结果？（2）如果将它们各涂上不同的颜色，仍有正反面，可能掷出多少种不同结果？（1）7种（2）269/21/202232例7（课本P355）四元一次不定方程 x1+x2+x3+x4=6（1）有多少组正整数解？（2）有多少组非负整数解？一般地，一次不定方程 x1+x2+xr=n（1）正整数解有 组(nr)；（2）非负整数解有 组。9/21/202233例8 方程 3x1+x2+x3+x4+x5+x6=3 的非负整数解有多少组？9/21/202234一、不尽相异元素的排列定义6 把n个不尽相异的元素按照一定的顺 序排成一列，叫做n个不尽相异元素 的全排列4 不尽

12、相异元素的排列与组合例： 用一个“1”,两个“2”,两个“3”可以组成多少个5位数？9/21/202235一、不尽相异元素的排列定义6 把n个不尽相异的元素按照一定的顺 序排成一列，叫做n个不尽相异元素 的全排列4 不尽相异元素的排列与组合引例： 用1,2,3这三个数字组成5位数，一共可以组成多少个？9/21/202236一、不尽相异元素的排列定义6 把n个不尽相异的元素按照一定的顺 序排成一列，叫做n个不尽相异元素 的全排列定理8 如果在 n个元素中，有n1个 a1 ， n2个 a2 ， nk个 ak ， 那么这 n个不尽相异元素的全排列数 是 4 不尽相异元素的排列与组合9/21/2022

13、37例1 (课本P357)一个球队与八个球队各比赛一场，问4胜、3负、1平的可能情形有多少种？9/21/202238例2 (课本P357)将5个相同的红球和5个相同的白球排成一列，首尾不许同色，共有多少种不同的排法？9/21/202239例3 (课本P357)某市有7条南北向的街，5条东西向的街，从西南角的A点到东北角的点B，经最短路程，有多少种不同走法？9/21/202240例4 (课本P358)求展开式(a1+ a2 + + an )r中，含 a1r1a2r2 anrn的系数（r为正整数， ）a1r1a2r2 anrn =a1 a1 a2 a2 an an9/21/202241例5（课本P

14、358）不定方程 x1+x2+x3+x4=7 有多少组正整数解？一般地，一次不定方程 x1+x2+xr=n（1）正整数解有 组(nr)；（2）非负整数解有 组。9/21/202242二、不尽相异元素的组合定义7 从n个不尽相异的元素中，取出r（rn）个元素而不考虑其次序时，叫做n个不尽相异元素中取出r个的组合4 不尽相异元素的排列与组合9/21/202243例9 (课本P361) 540不同的正因数有多少个？540=2233 5(2+1)(3+1 )(1+1)=24定理9（见课本P362）9/21/202244一、二项式定理5 二项式定理9/21/202245二项式定理的发现通过探索,13世纪

15、阿拉伯人已经知道两项和的n次方的展开结果:9/21/202246二项式定理的发现为了便于看出规律，我们把它补充完整:9/21/202247二项式定理的发现为了便于研究其中的规律, 1544年Stifel把公式中字母的系数提取出来,称为二项式系数.他发现其中每个数是其上方紧邻两数之和.用公式表示为:这个结果，中国数学家杨辉早在13世纪就发现了。9/21/202248二项式定理的发现通过进一步研究， 1654年Pascal发现二项式系数的规律,即通项公式:1713年,Bernoulli对上面的公式给出了证明。49一、二项式定理5 二项式定理定理10二项式展开的通项： 9/21/202250二、二项

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

17、.（x-2)9的展开式中，第6项的二项式系数 是（ ） A.4032 B.-4032 C.126 D.-126C4.(a+b)n展开式中，第6项的二项式系数最大，则n是多少? 误解 n=10. 正解 n=9，10或11.(为什么?)9/21/2022535 二项式定理5. =_.322n-1练习：P380.习题 23、25、279/21/202254对于三项和的n次幂，可以如下计算5 二项式定理四、多项式定理9/21/202255具体写出来是5 二项式定理四、多项式定理9/21/202256为了保持展开后的对称性，我们把展开式写成5 二项式定理四、多项式定理9/21/202257把公式中字母的

18、系数提取出来经过仔细观察，我们发现上一三角形可以摞在下一三角形的上方，构成一个正四面体。四面体中的每一个数等于其肩上三个数之和。5 二项式定理四、多项式定理9/21/202258同样的方法，我们可以得到四项和的n次幂的计算公式5 二项式定理四、多项式定理9/21/202259四、多项式定理定理11 其中 表示对所有满足 的非负整数组 求和. 5 二项式定理9/21/202260 应用举例 例10. 求 展开式中x4的系数.5 二项式定理例11. 设nN*，试证展开式按x升幂排列后，与首末两端等距离的两项系数相等.例12. 试求 展开式中各项系数的平方和。9/21/2022616 排列、组合的母函数一、组合数的母函数 的母函数例2. 求和9/21/2022626 排列、组合的母函数二、组合的母函数定