排列组合公式

排列组合公式•排列组合公式•非降路径问题•组合恒等式排列与组合•从五个候选人中选出两个代表•把5本不同的书安排在书架上•从五个候选人中选出两个代表时，有10种可能的结果。•把5本不同的书安排在书架上有120种方法•选出-组合；安排-排列一、排列组合公式•排列问题：从某个集合中有序地选取若干个元素的问题•组合问题：从某个集合中无序地选取若干个元素的问题•注意：可以重复不能重复排列•无重排列•可重排列•从{1,2,…,9}中选取数字构成四位数，使得每位数字都不同，有多少个？•从{1,2,…,9}中选取数字构成四位数，使得不同数位上的数字可以相同，有多少个？1、无重排列•n个元素的r-无重排列数：•排列的长度r•计算（一般情形）：乘法原理•r=n时,n个元素的全排列•r=0时•rn时2、可重排列•n个元素的r-可重排列数•计算（乘法原理）例题•在1和10,000,000,000之间的一百亿个数中，有多少个数含有数码1？又有多少个数不含数码1？•不含1:910•含1:1010-910+1放球问题•设n≥r，把r个不同的球放入n个不同的盒子，这里每一盒最多只能装一物，允许空盒。放球的方法数为多少？•第一个球有n种选法，第二个球有n-1种，等等，乘法原理•P(n,r)放球问题•把r个不同的球放入n个不同的盒子，一个盒中可以放多个球，也允许空盒。放球的方法数为多少？•第一个球有n种选法，第二个球有n种，等等，乘法原理•nr•这里n和r的大小没有限制组合•无重组合•可重组合•从{a,b,c}中选取2个不同元素，选法数是多少？•从{a,b,c}中选取5个元素，元素可以相同，选法数是多少？3、无重组合（Combination）•n个元素的r-无重组合数•无重组合数与无重排列数的关系•计算•r=0时•r=n时•rn时组合数的推广rnC)!(!!rnrn!)1()1(rrnnnrnrnC)!(!!rnrn!)1()1(rrnnnrnCZrR,0,00,10,!)1()1(rrrrrr几个记号)1()1(][nxxxxn下阶乘函数上阶乘函数)1()1(][nxxxxn)1()1(][nn!)1()1(!][nnnnCnn计算32132102153例题•如果一个凸十边形无三条对角线在这个十边形的内部交于一点，问这些对角线被它们的交点分成多少条线段？多边形例题•对角线的条数为C(10,2)-10=45-10=35•任选两条对角线，可能相交在多边形内部，可能交点为多边形的顶点，可能无交点（交点在多边形外）•任选四个顶点，对应一个交点，每个对角线分成两段•每个对角线是一段•35+C(10,4)×2=455例题C(5,2)-5+C(5,4)×2=15C(10,2)-10+C(10,4)×2=455C(4,2)-4+C(4,4)×2=44、可重组合•n个元素的r-可重组合•例子•计算•一一对应的思想推论•方程x1+x2+…+xn=r的非负整数解的个数。•n≤r时，此方程的正整数解的个数•n元集合的r-可重组合数，要求每个元素至少出现一次。•正整数r的n-长有序分拆的个数•求x1+x2+x3+x4=20的整数解的数目，其中x1≥3,x2≥1,x3≥0,x4≥5。例题•从为数众多的一分币、二分币、一角币和二角币中，可以有多少种方法选出六枚来？•F(4,6)=C(4+6-1,6)=C(9,6)=84例题•某糕点厂将8种糕点装盒，若每盒有一打糕点，求市场上能买到多少种该厂出品的盒装糕点？•某糕点厂将8种糕点装盒，若每盒有一打糕点，且要求每种糕点至少放一块。求市场上能买到多少种该厂出品的盒装糕点？例题•摇三个不同的骰子的时候，可能的结果的个数是多少？•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)有约束条件的排列：引例•用两面红旗、三面黄旗依次悬挂在一根旗杆上，问可以组成多少种不同的标志？5、有约束条件的排列•设有k个元素a1，a2，…，ak，由它们组成一个n-长的排列，其中对1≤i≤k，ai出现的次数为ni，n1+n2+…+nk=n，求排列的总数。•求解方法1•求解方法2例题•五条短划和八个点可以安排成多少种不同的方式？•如果只用这十三个短划和点中的七个，则有多少种不同的方式？!8!5!13!7!0!7+!6!1!7+!5!2!7+!4!3!7+!3!4!7+!2!5!7例题•证明对任意正整数k,(k!)!能被(k!)(k-1)!整除。•提示：k!个物体，其中k个物体属于第一类，k个物体属于第二类，…，k个物体属于第(k-1)!类。推论•多项式(x1+x2+…+xr)n的展开式中有项，其中项的系数为。rnrnnxxx21216321)532(xxx23231xxxnrxxx)(21rrrnrnnnnnnnnnrxxxnnnn21212121,,,21为非负整数例题•数1400有多少个正因数？•1400=23×52×7•(3+1)(2+1)(1+1)=24放球问题•设n≥r，把r个相同的球放入n个不同的盒子使得每盒至多装一个球，方法数？•选盒子即可•C(n,r)放球问题•把r个相同的球放入n个不同的盒子，每盒可以装任意多个球，方法数？•放这r个球，等价于从n个盒中选出r个来装这r个球而允许诸盒重复选取。•F(n,r)=C(n+r-1,r)•另解：把分配这r个球入n个盒子设想为这r个球和n-1个隔板的一个排列。球是相同的，隔板也是相同的。•C(n+r-1,r)放球问题•设r≥n，把r个相同的球放入n个不同的盒子中，盒子中可以放入任意多个球，但不允许空盒，方法数？•现在每个盒中放入一个球，再放剩下的r-n个球•C((r-n)+n-1,r-n)=C(r-1,r-n)=C(r-1,n-1)放球问题•设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)放球问题：例题•今有五封不同的信要经由一个讯道传送。又有总共15个空白要插在这些信之间而使得每两封信之间至少有三个空白。有多少种方法安排这些信和空白？•信的安排5！•对一种信的安排，有4个信件位置，安排15个空白，要求每个信件位置至少有三个空白。•5！C(4-4×3+15-1,4-1)=5!×C(6,3)放球问题•有n个球，其中第一种颜色n1个，第二种颜色n2个，…，第k种颜色nk个。将这n个球放入n个不同的盒中，每一个盒装一个球。问分配方案数？•等价于这n个球的排列数。•另解：选盒子装每种颜色的球。放球问题•有r个球，其中第一种颜色n1个，第二种颜色n2个，…，第k种颜色nk个。将这r个球放入n个不同的盒中，每一个盒装一个球（r≤n）。问分配方案数？•方法一：先选盒子，再分配球。•方法二：针对每种颜色的球选盒子。多重集合•通常的“集合”具有无重性。•在多重集中，同一个元素可以出现多次。•{1,2,3}是一个集合，而{1,1,1,2,2,3}不是一个集合，而是一个多重集，简记为{3·1,2·2,1·3}。•计算多重集的势时，出现多次的元素则需要按出现的次数计算。上面多重集的势为6。•可重组合与可重排列可以看作是多重集的组合与排列问题。可重排列与可重组合•n个元素{a1,a2,…,an}的r-无重组合(排列)可以看做多重集{1·a1,1·a2,…,1·an}的r-组合(排列)。•n个元素{a1,a2,…,an}的r-可重组合(排列)可以看做多重集{∞·a1,∞·a2,…,∞·an}的r-组合(排列)。•有限制的排列问题可以看做多重集{n1·a1,n2·a2,…,nk·ak}的全排列。限距组合：引例•书架上有1-24共24卷百科全书，从其中选5卷使得任何两卷都不相继，这样的选法有多少种？6、限距组合•设A={1,2,…,n}，它的任一r-无重组合均可以依自然顺序排出a1,a2,…,ar，其中a1a2…ar。设k是非负整数，用f(k,n,r)表示A的一切满足条件ai+1-ai≥k+1(1≤i≤r-1)的r-无重组合数，求f(k,n,r)。•求解思想：一一对应•k=0时例题•书架上有1-24共24卷百科全书，从其中选5卷使得任何两卷都不相继，这样的选法有多少种？7、圆排列•n个元素的r-无重圆排列数•圆排列与线排列的区别•计算例题例1把20个不同的钉子钉在鼓表面一周，订钉子的方式有种。例2把20个不同的珍珠串成项链，串项链的方式有种。项链问题例从1到300间取出3个不同的数，使它们的和被3整除，有多少种取法？提示：将1到300这300个整数按照除以3的余数分成3组，考虑选出的3个数属于哪些组。例下图中有多少个矩形？映射•设映射f：{1,2,…,n}→{1,2,…,m}(n≤m)•(1)若f是严格递增的，则不同的f有多少个？•(2)若f是不减的，则不同的f有多少个？例题1、从A={a,b,c}中任取两个不同的字母构成的字共有多少个？2、m元集合的n元子集的个数？3、平面上任三点都不共线的25个点，可形成多少条直线？可形成多少个三角形？例题•用26个英文字母能构成多少个含有3个、4个或5个元音的长为8位的单词？（其中，一个字母出现在单词中的次数不限）例题•用4个a，4个b，2个c和2个d这12个字母能组成多少个具有12个字母的字？•用字母a，b，c组成5个字母的字，每个字中a至多出现2次，b至多出现1次，c至多出现3次。这种字的个数是多少？例题•单词mississippi中字母的排列数为？•求多重集{3·a,2·b,4·c}的8排列的个数？例题•求26个英文字母的全排列中，任意两个元音字母都不相邻的方案数？例题•Banach火柴盒问题：某数学家随身携带A,B两盒火柴，要用火柴时就随意从其中一盒中取出一根。假定开始两个火柴盒各放有n根火柴，问在某一次当数学家发现拿出的那一个火柴盒变空时，另一盒中尚剩p(pn)根火柴的概率是多少？例题•10个人排成一排，其中有2个人不愿彼此挨着，求所有不同的排列的数目。•10！-2×9！或8！A(9,2)=2903040•10个人围一圆桌入座，其中有2个人不愿彼此挨着就座，求所有不同的圆排列的数目。•9!-2×8!或7！A(8,2)=282240例题•安排10个男生和5个女生排成一排，使任意2个女生都不相邻的排法有多少种？•A(10,10)A(11,5)•安排10个男生和5个女生围成圆圈入座，使任意2个女生都不相邻的坐法有多少种？例从给定的6种不同的颜色中选不同的颜色将一个正方体的六个面染色，要求每个面染一种颜色，具有相同棱的面染成不同的颜色，则不同的染色方案有多少种？分析：一种颜色？两种颜色？三种颜色？相对的面染成相同的颜色,只有一种方式C(6,3)四种颜色：五种颜色：六种颜色：C(6,4)C(4,2)C(6,5)C(5,1)3！/2C(6,6)C(5,1)3！例试求由1,3,5,7组成的数字不重复出现的整数的总和。分析：一位数1，3，5，7两位数个(十)位数为1的两位数的个数三位数个(十、百)位数为1的三位数的个数四位数个(十、百、千)位数为1的四位数的个数例假定把全部的5码数印刷在纸条上，而一张纸条上印一个数。所谓5码数是由0,1,2,…,9这十个数字中的5个数字组成的数，开头的一个或者几个可以为0，例如00102,00000都是5码数，显然有100000个这样的