排列组合公式省名师优质课获奖课件市赛课一等奖课件.ppt

排列组合公式排列组合公式排列组合公式排列组合公式非降路径问题非降路径问题组合恒等式组合恒等式第1页排列与组合从五个候选人中选出选出两个代表把5本不一样书安排安排在书架上从五个候选人中选出两个代表时，有10种可能结果。把5本不一样书安排在书架上有120种方法选出-组合；安排-排列第2页一、排列排列组合组合公式排列问题：从某个集合中有序有序地选取若干个元素问题组合问题：从某个集合中无序无序地选取若干个元素问题注意：能够重复 不能重复第3页排列无重排列可重排列从1,2,9中选取数字组成四位数，使得每位数字都不一样，有多少个？从1,2,9中选取数字组成四位数，使得不一样数位上数字能够相同，有多少个？第4页1、无重排列n个元素r-无重排列无重排列数：排列长度r计算（普通情形）：乘法原理r=n时,n个元素全排列r=0时rn时第5页2、可重排列n个元素r-可重排列可重排列数计算（乘法原理）第6页例题在1和10,000,000,000之间一百亿个数中，有多少个数含有数码1？又有多少个数不含数码1？不含1:910含1:1010-910+1第7页放球问题设nr，把r个不一样球放入n个不一样盒子，这里每一盒最多只能装一物，允许空盒。放球方法数为多少？第一个球有n种选法，第二个球有n-1种，等等，乘法原理P(n,r)第10页放球问题把r个不一样球放入n个不一样盒子，一个盒中能够放多个球，也允许空盒。放球方法数为多少？第一个球有n种选法，第二个球有n种，等等，乘法原理nr这里n和r大小没有限制第11页例子将3封信向2个信箱投寄，有多少种投寄方法？23=8无序占位模型：不考虑盒子中排列次序第12页例子某车站有6个进站口，今有9人进站，有多少种不一样进站方法？69=6714七部汽车经过五间收费亭方式数？今欲在五根旗杆上悬挂七面不一样旗子，全部旗都得展示出来，但并非全部旗杆都得使用，问有多少种安排方法？第14页组合无重组合可重组合从a,b,c中选取2个不一样元素，选法数是多少？从a,b,c中选取5个元素，元素能够相同，选法数是多少？第16页3、无重组合（Combination）n个元素r-无重组合无重组合数无重组合数与无重排列数关系计算r=0时r=n时rn时第17页组合数推广第18页计算第20页例题假如一个凸十边形无三条对角线在这个十边形内部交于一点，问这些对角线被它们交点分成多少条线段？第21页多边形第22页例题对角线条数为C(10,2)-10=45-10=35任选两条对角线，可能相交在多边形内部，可能交点为多边形顶点，可能无交点（交点在多边形外）任选四个顶点，对应一个交点，每个对角线分成两段每个对角线是一段35+C(10,4)2=455第23页例题C(5,2)-5+C(5,4)2=15C(10,2)-10+C(10,4)2=455C(4,2)-4+C(4,4)2=4第24页4、可重组合n个元素r-可重组合可重组合例子计算一一对应思想第25页推论方程x1+x2+xn=r 非负整数解个数。nr时，此方程正整数解个数n元集合r-可重组合数，要求每个元素最少出现一次。正整数rn-长有序分拆个数求x1+x2+x3+x4=20整数解数目，其中x1 3,x2 1,x3 0,x4 5。第26页例题从为数众多一分币、二分币、一角币和二角币中，能够有多少种方法选出六枚来？F(4,6)=C(4+6-1,6)=C(9,6)=84第27页例题某糕点厂将8种糕点装盒，若每盒有一打糕点，求市场上能买到多少种该厂出品盒装糕点？某糕点厂将8种糕点装盒，若每盒有一打糕点，且要求每种糕点最少放一块。求市场上能买到多少种该厂出品盒装糕点？第28页例题摇三个不一样骰子时候，可能结果个数是多少？63=216。假如这三个骰子是没有区分，则可能结果个数是多少？从1,2,3,4,5,6这六个数中允许重复地选出三个数。F(6,3)=C(6+3-1,3)=56将r个骰子掷一次，总共能够掷出多少种不一样结果？F(6,r)=C(6+r-1,r)=C(r+5,r)=C(r+5,5)第29页有约束条件排列：引例用两面红旗、三面黄旗依次悬挂在一根旗杆上，问能够组成多少种不一样标志？第30页5、有约束条件排列设有k个元素a1，a2，ak，由它们组成一个n-长排列，其中对1ik，ai出现次数为ni，n1+n2+nk=n，求排列总数。求解方法1求解方法2第31页例题 五条短划和八个点能够安排成多少种不一样方式？假如只用这十三个短划和点中七个，则有多少种不一样方式？第32页例题证实对任意正整数k,(k!)!能被(k!)(k-1)!整除。提醒：k!个物体，其中k个物体属于第一类，k个物体属于第二类，k个物体属于第(k-1)!类。第33页推论多项式(x1+x2+xn)r展开式中有 项，其中项 系数为 。第34页例题数1400有多少个正因数？1400=23 52 7(3+1)(2+1)(1+1)=24第35页放球问题设nr，把r个相同球放入n个不一样盒子使得每盒至多装一个球，方法数？选盒子即可C(n,r)第36页放球问题把r个相同球放入n个不一样盒子，每盒能够装任意多个球，方法数？放这r个球，等价于从n个盒中选出r个来装这r个球而允许诸盒重复选取。F(n,r)=C(n+r-1,r)第37页放球问题把r个相同球放入n个不一样盒子，每盒能够装任意多个球，方法数？另解：把分配这r个球入n个盒子构想为这r个球和n-1个隔板一个排列。球是相同，隔板也是相同。C(n+r-1,r)第38页放球问题设r n，把r个相同球放入n个不一样盒子中，盒子中能够放入任意多个球，但不允许空盒，方法数？现在每个盒中放入一个球，再放剩下r-n个球C(r-n)+n-1,r-n)=C(r-1,r-n)=C(r-1,n-1)第39页放球问题设r n，把r个相同球放入n个不一样盒子中，要求每一盒最少包含q个球，方法数？现在每个盒中放入q个球，再放剩下r-qn个球C(r-qn)+n-1,r-qn)=C(n-nq+r-1,r-nq)=C(n-nq+r-1,n-1)第40页多重集合通常“集合”含有没有重性。在多重集中，同一个元素能够出现屡次。1,2,3是一个集合，而1,1,1,2,2,3不是一个集合，而是一个多重集，简记为31,22,13。计算多重集势时，出现屡次元素则需要按出现次数计算。上面多重集势为6。可重组合与可重排列能够看作是多重集组合与排列问题。第44页可重排列与可重组合n个元素a1,a2,anr-无重组合(排列)能够看做多重集1a1,1 a2,1 anr-组合(排列)。n个元素a1,a2,anr-可重组合(排列)能够看做多重集a1,a2,anr-组合(排列)。有限制排列问题能够看做多重集n1a1,n2 a2,nk ak全排列。第45页分组与分堆第46页限距组合：引例书架上有1-24共24卷百科全书，从其中选5卷使得任何两卷都不相继，这么选法有多少种？第54页6、限距组合设A=1,2,n，它任一r-无重组合均能够依自然次序排出a1,a2,ar，其中a1a2 ar。设k是非负整数，用f(k,n,r)表示A一切满足条件ai+1-aik+1(1ir-1)r-无重组合数，求f(k,n,r)。求解思想：一一对应k=0时第55页例题书架上有1-24共24卷百科全书，从其中选5卷使得任何两卷都不相继，这么选法有多少种？第56页7、圆排列n个元素r-无重圆排列数圆排列与线排列区分计算第57页例题例1把20个不一样钉子钉在鼓表面一周，订钉子方式有 种。例2把20个不一样珍珠串成项链，串项链方式有 种。项链问题项链问题第58页例 从1到300间取出3个不一样数，使它们和被3整除，有多少种取法？提醒：将1到300这300个整数按照除以3余数分成3组，考虑选出3个数属于哪些组。第59页例 下列图中有多少个矩形？第60页映射设映射f：1,2,n 1,2,m(nm)(1)若f是严格递增，则不一样f有多少个？(2)若f是不减，则不一样f有多少个？第63页例题1、从A=a,b,c中任取两个不一样字母组成字共有多少个？2、m元集合n元子集个数？3、平面上任三点都不共线25个点，可形成多少条直线？可形成多少个三角形？第64页例题用26个英文字母能组成多少个含有3个、4个或5个元音长为8位单词？（其中，一个字母出现在单词中次数不限）第65页例题用4个a，4个b，2个c和2个d这12个字母能组成多少个含有12个字母字？用字母a，b，c组成5个字母字，每个字中a至多出现2次，b至多出现1次，c至多出现3次。这种字个数是多少？第67页例题单词mississippi中字母排列数为？求多重集3a,2b,4c8排列个数？第68页例题求26个英文字母全排列中，任意两个元音字母都不相邻方案数？第69页例题Banach火柴盒问题：某数学家随身携带A,B两盒火柴，要用火柴时就随意从其中一盒中取出一根。假定开始两个火柴盒各放有n根火柴，问在某一次当数学家发觉拿出那一个火柴盒变空时，另一盒中尚剩p(pn)根火柴概率是多少？第70页例题10个人排成一排，其中有2个人不愿彼此挨着，求全部不一样排列数目。10！-29！或 8！A(9,2)=290304010个人围一圆桌入座，其中有2个人不愿彼此挨着就座，求全部不一样圆排列数目。9!-28!或7！A(8,2)=282240第71页例题安排10个男生和5个女生排成一排，使任意2个女生都不相邻排法有多少种？A(10,10)A(11,5)安排10个男生和5个女生围成圆圈入座，使任意2个女生都不相邻坐法有多少种？第72页例 从给定6种不一样颜色中选不一样颜色将一个正方体六个面染色，要求每个面染一个颜色，含有相同棱面染成不一样颜色，则不一样染色方案有多少种？分析：一个颜色？两种颜色？三种颜色？相正确面染成相同颜色,只有一个方式C(6,3)第73页四种颜色：五种颜色：六种颜色：C(6,4)C(4,2)C(6,5)C(5,1)3！/2C(6,6)C(5,1)3！第74页例 试求由1,3,5,7组成数字不重复出现整数总和。分析：一位数1，3，5，7两位数个(十)位数为1两位数个数三位数个(十、百)位数为1三位数个数四位数个(十、百、千)位数为1四位数个数第75页例 假定把全部5码数印刷在纸条上，而一张纸条上印一个数。所谓5码数是由0,1,2,9这十个数字中5个数字组成数，开头一个或者几个能够为0，比如00102,00000都是5码数，显然有100000个这么5码数。然而因为数字0,1,6,8,9被倒过来就成了0,1,9,8,6。而一张纸条能够从上下两个方向正看和倒看，所以有些5码数能够共用一张纸条，如89166与99168。于是我们问题是要用多少个不一样纸条才能做出这些5码数？第76页0 1 2 3 4 5 6 7 8 90 101 倒过来 8 8 6 9 9 6第77页1357813578倒过来 89166681898916668189不是5码数仍是5码数仍是5码数但不是自己而且是自己第78页5码数共105个倒过来仍是5码数有55个倒过来不再是5码数有10555个一个数一张纸条倒过来是自己有3x52个倒过来不是自己有553x52个一个数一张纸条两个数共用一张纸条第79页所以纸条个数为(10555)+3x52+(553x52)/2105(553x52)/2=98475第80页例 甲、乙两方各有7名队员，按事先排好次序出场参加围棋擂台赛。双方先由1号参加比赛，负者被淘汰，胜者再与对方2号队员比赛，直到有一方全部被淘汰，另一方取得胜利，形成一个比胜过程。那么全部可能出现比胜过程种数为多少？第81页甲乙箭头指向谁，表示谁负甲方赢：甲方赢：这是一个7-可重组合第82页甲乙第83页甲乙第84页甲乙第85页例 某车站有6个进站口，今有9人进站，有多少种不一样进站方法？进站口人2ABCDEF13456789任务：给每个人选择进站口，选择进站次序？第86页安排 ：ABCDEF16种方式1安排 ：27种方式222安排 ：38种方式3333安排 ：914种方式进站方式种数为方法一：第87页123456取213456789一个全排列，和5个213456789对应进站方式为：913456872方法二：第88页ABCDEF进站方式为：913456872213456789对应排列为：第89页进站方式种数为213456789排列5个或14个位置取5个放方框(不讲次序)，剩下放人(将次序)第90页方法三：先选车站，A B C D EF 9-可重组合AAACCDEEF再排人，213456789排列213456789对应进站方式为：ABCDEF913456872第91页例 8个人 两两配对分成4组有多少种方式？方法一 给每个人配对方法二 一对一对地选，注意会重复推广：2n个人两两配对分成n组有多少种方式？第93页非降路径问题从点 抵达点 非降路径非降路径第94页非降路径数由(0,0)到(m,n)非降路径数为 。由(a,b)到(m,n)非降路径数为 。由(0,0)到(m,n),再到(a,b)非降路径数 。第95页例题从点(0,0)抵达点(m,n)，其中mn，要求中间所经过旅程上点(a,b)都满足ab。问有多少种不一样路径？第96页分析从(0,0)到(m,n)非降路径 过对角线必过对角线一一对应：反射(0,0)(0,1)(m,n)(0,0)(1,0)(m,n)不过对角线第97页反射：从上向下看，找路径与对角线交点第一个点，关于对角线反射左下边路径，与右上路径组合成一条路径。第98页例题求从点(0,0)抵达点(n,n)且不与直线y=x相交非降路径数？分析：上一例题特殊情况第99页例题一场音乐会票价为50元/张，排队买票用户中有n位持有50元现金，m位持有100元现金，售票处没有准备50元零钱。试问有多少种排队方法，使购票能顺利进行，不出现找不开钱情况，假定每位用户限买一张，每位用户仅买票一张，而且nm。第100页例题用(m+n)维0,1-行向量(a1,a2,am+n)表示一个购票排队状态，其中ai=1表示第i位持50元现金，ai=0表示第i人持100元现金。这么行向量有m个0，n个1，所以这么行向量共有C(m+n,m)个，每个行向量能够对应从点(0,0)到点(m,n)非降路径。当ai=1时，对应路径中第i步沿y轴向上走一格，当ai=0时，对应路径中第i步沿x轴向右走一格。为了使购票顺利进行，每个路径中点(a,b)应满足ab。也就是每个路径在直线y=x上方且不穿过直线 y=x，能够有交点。第101页因为nm，也就是在直线y=x-1上方全部路径。从(0,0)到(m,n)在直线y=x-1上方非降路径从(0,1)到(m,n+1)在直线y=x上方非降路径从(0,0)到(m,n+1)在直线y=x上方非降路径第n个Catalan数第102页Catalan数第n个Catalan数第103页Catalan数组合学意义第104页例题n个+1和n个-1所组成序列中全部其前k项(k=1,2,2n)之和大于0序列数目是多少？满足条件序列为好序列，不满足条件为坏序列。好序列数=序列总数-坏序列数。n个+1和n个-1所组成坏序列与n+1个+1和n-1个-1所组成序列一一对应。第105页例题对每个坏序列，总能够找到最小正奇数，使得ak=-1且ak之前+1和-1个数相等。将这个坏序列中前k项每一项取反号，其余部分保持不变。所得序列为n+1个+1和n-1个-1组成序列。-1,-1,1,1,-1,1变为1,-1,1,1,-1,1反之，对任一由n+1个+1和n-1个-1组成序列，从左到右扫描，当+1个数第一次比-1个数多1时就把这些扫描到项全部取反号，其余项不变，结果得到满足要求坏序列。1,-1,1,1,-1,1变为-1,-1,1,1,-1,1第106页二项式定理第107页组合恒等式组合数组合恒等式：由组合数组成恒等式组合数大小关系n为奇数n为偶数第108页1.证实一：计算证实二：组合分析法第109页第110页第111页2.杨辉三角形计算Pascal三角形证实一：证实二：组合分析法第112页3.利用二项式代特殊值证实一：证实二：首先，按照子集个数分类求和n元集合全部子集个数另首先，按照元素与集合属于、不属于关系第113页4.二项式定理代特殊值证实一：证实二：组合分析法第114页5.第115页朱世杰恒等式第116页6.应用：第117页第118页7.证实一：倒写，然后两式相加证实二：计算，提出n证实三：求导数证实四：组合分析法证实五：数学归纳法第119页8.证实一：积分证实二：计算，分子分母同乘n+1第120页证实一：组合分析法证实二：利用多项式系数证实三：非降路径法第121页证实三：非降路径法从 到 非降路径过且仅过直线 上线段AB一个格点第122页证实一：计算证实二：组合分析法第123页证实一：计算证实二：组合分析法第124页证实一：数学归纳法证实二：普通项证实三：加减项证实四：组合分析法第125页例 设集合A=a1,a2,an，A m个子集A1,A2,Am 两两互不包含。试证：(1)(2)第126页例 给出 个位数字和十位数字。第127页例 证实r个连续自然数乘积可被r！整除。第128页例 假如p是素数，则都能被p整除。第129页