排 列 组 合 公 式 及 排 列 组 合 算 法
- 格式:pdf
- 大小:156.60 KB
- 文档页数:8
高中数学排列组合公式大全_高中数学排列组合重点知识1.排列及计算公式从n个不同元素中,任取mm≤n个元素按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列;从n个不同元素中取出mm≤n个元素的所有排列的个数,叫做从n个不同元素中取出m个元素的排列数,用符号 pn,m表示.pn,m=nn-1n-2……n-m+1= n!/n-m!规定0!=1.2.组合及计算公式从n个不同元素中,任取mm≤n个元素并成一组,叫做从n个不同元素中取出m个元素的一个组合;从n个不同元素中取出mm≤n个元素的所有组合的个数,叫做从n个不同元素中取出m个元素的组合数.用符号cn,m 表示.cn,m=pn,m/m!=n!/n-m!*m!;cn,m=cn,n-m;3.其他排列与组合公式从n个元素中取出r个元素的循环排列数=pn,r/r=n!/rn-r!.n个元素被分成k类,每类的个数分别是n1,n2,...nk这n个元素的全排列数为n!/n1!*n2!*...*nk!.k类元素,每类的个数无限,从中取出m个元素的组合数为cm+k-1,m.排列Pnmn为下标,m为上标Pnm=n×n-1....n-m+1;Pnm=n!/n-m!注:!是阶乘符号;Pnn两个n分别为上标和下标=n!;0!=1;Pn1n为下标1为上标=n组合Cnmn为下标,m为上标Cnm=Pnm/Pmm ;Cnm=n!/m!n-m!;Cnn两个n分别为上标和下标 =1 ;Cn1n为下标1为上标=n;Cnm=Cnn-m加法乘法两原理,贯穿始终的法则。
与序无关是组合,要求有序是排列。
两个公式两性质,两种思想和方法。
归纳出排列组合,应用问题须转化。
排列组合在一起,先选后排是常理。
特殊元素和位置,首先注意多考虑。
不重不漏多思考,捆绑插空是技巧。
排列组合恒等式,定义证明建模试。
关于二项式定理,中国杨辉三角形。
两条性质两公式,函数赋值变换式。
1.计数原理知识点①乘法原理:N=n1·n2·n3·…nM 分步②加法原理:N=n1+n2+n3+…+nM 分类2. 排列有序与组合无序Anm=nn-1n-2n-3…n-m+1=n!/n-m! Ann =n!Cnm = n!/n-m!m!Cnm= Cnn-m Cnm+Cnm+1= Cn+1m+1 k•k!=k+1!-k!3.排列组合混合题的解题原则:先选后排,先分再排排列组合题的主要解题方法:优先法:以元素为主,应先满足特殊元素的要求,再考虑其他元素. 以位置为主考虑,即先满足特殊位置的要求,再考虑其他位置.捆绑法集团元素法,把某些必须在一起的元素视为一个整体考虑插空法解决相间问题间接法和去杂法等等在求解排列与组合应用问题时,应注意:1把具体问题转化或归结为排列或组合问题;2通过分析确定运用分类计数原理还是分步计数原理;3分析题目条件,避免“选取”时重复和遗漏;4列出式子计算和作答.经常运用的数学思想是:①分类讨论思想;②转化思想;③对称思想.4.二项式定理知识点:①a+bn=Cn0ax+Cn1an-1b1+ Cn2an-2b2+ Cn3an-3b3+…+ Cnran-rbr+…+ Cn n-1abn-1+ Cnnbn特别地:1+xn=1+Cn1x+Cn2x2+…+Cnrxr+…+Cnnxn②主要性质和主要结论:对称性Cnm=Cnn-m最大二项式系数在中间。
排列组合公式/排列组合计算公式排列P------和顺序有关组合C -------不牵涉到顺序的问题排列分顺序,组合不分例如把5本不同的书分给3个人,有几种分法. "排列"把5本书分给3个人,有几种分法"组合"1.排列及计算公式从n个不同元素中,任取m(m≤n)个元素按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列;从n个不同元素中取出m(m≤n)个元素的所有排列的个数,叫做从n个不同元素中取出m个元素的排列数,用符号 p(n,m)表示.p(n,m)=n(n-1)(n-2)……(n-m+1)= n!/(n-m)!(规定0!=1).2.组合及计算公式从n个不同元素中,任取m(m≤n)个元素并成一组,叫做从n个不同元素中取出m个元素的一个组合;从n个不同元素中取出m(m≤n)个元素的所有组合的个数,叫做从n个不同元素中取出m个元素的组合数.用符号c(n,m) 表示.c(n,m)=p(n,m)/m!=n!/((n-m)!*m!);c(n,m)=c(n,n-m);3.其他排列与组合公式从n个元素中取出r个元素的循环排列数=p(n,r)/r=n!/r(n-r)!.n个元素被分成k类,每类的个数分别是n1,n2,...nk这n个元素的全排列数为n!/(n1!*n2!*...*nk!).k类元素,每类的个数无限,从中取出m个元素的组合数为c(m+k-1,m).排列(Pnm(n为下标,m为上标))Pnm=n×(n-1)....(n-m+1);Pnm=n!/(n-m)!(注:!是阶乘符号);Pnn (两个n分别为上标和下标) =n!;0!=1;Pn1(n为下标1为上标)=n组合(Cnm(n为下标,m为上标))Cnm=Pnm/Pmm ;Cnm=n!/m!(n-m)!;Cnn(两个n分别为上标和下标) =1 ;Cn1(n为下标1为上标)=n;Cnm=Cnn-m2008-07-08 13:30公式P是指排列,从N个元素取R个进行排列。
排列组合1. 排列组合公式quad排列与组合二者的区别,排列计较次序而组合不计序。
quad从n从n从n个不同物件随机取rrr个物件,记排列数和组合数分别为AnrA_n^rAnr?和CnrC_n^rCnr?,则:Anr=n(n?1)?(n?r?1)=n!(n?r)!Cnr=Anrr!=n!r!(n?r)!begin{aligned}amp; A_n^r=n(n-1)cdots(n-r-1)=frac{n!}{(n-r)!}amp; C_n^r=frac{A_n^r}{r!}=frac{n!}{r!(n-r)!}end{aligned}Anr=n(n1)(nr1)=(nr)!n!Cnr=r!Anr=r!(nr)!n!quad注:Anr(n≥r≥1)A_n^r(ngeq r geq 1)Anr?(n≥r≥1),Cnr(n≥r≥0)C_n^r(ngeq r geq 0)Cnr?(n≥r≥0),0!=10!=10!=1,Cn0=1C_n^0=1Cn0?=12. 二项式及公式推广quad二项式展开公式为:(a+b)n=∑i=0nCniaibn?i(a+b)^n=sum_{i=0}^nC_n^ia^ib^{n-i}(a+b)n=i=0∑n?Cni?aibn?iquad系数CnrC_n^rCnr?常称为二项式系数。
由(a+b)n=(a+b)?(a+b)?n(a+b)^n=underbrace{(a+b)cdots(a+b)}_{n} (a+b)n=n(a+b)?(a+b)?,若独立nnn次实验从{a,b}{a,b}{a,b}中取数,则有CniC_n^iCni?种情况取到iii个aaa、n?in-in?i个bbb,故aibn?ia^ib^{n-i}aibn?i项的系数为CniC_n^iCni?。
quad(1) ∑i=0nCni=2nsum_{i=0}^n C_n^i=2^n∑i=0n?Cni?=2n quadquad 当a=b=1a=b=1a=b=1时,(a+b)n=2n=∑i=0nCni(a+b)^n=2^n=sum_{i=0}^nC_n^i(a+b)n=2n=∑i=0n?Cni?;quad(2)Cm+nk=∑i=0kCmiCnk?iC_{m+n}^k=sum_{i=0}^kC_m^iC_n^{k-i}Cm+n k?=∑i=0k?Cmi?Cnk?i?quadquad 因为(1+x)m+n=(1+x)m(1+x)n(1+x)^{m+n}=(1+x)^m(1+x)^n(1+x)m+n=(1+ x)m(1+x)n,即∑j=0m+nCm+njxj=(∑j=0mCmjxj)?(∑j=0nCnjxj)sum_{j=0}^{m+n}C _{m+n}^jx_j=(sum_{j=0}^mC_m^jx_j)cdot(sum_{j=0}^nC_n^jx_j)∑j=0m+n?Cm+nj?xj?=(∑j=0m?Cmj?xj?)?(∑j=0n?Cnj?xj?),由等式两边同幂项系数相同知Cm+nk=∑i=0kCmiCnk?iC_{m+n}^k=sum_{i=0}^kC_m^iC_n^{k-i}Cm+n k?=∑i=0k?Cmi?Cnk?i?。
小学数学排列组合计算公式如何把小学各门基础学科学好大概是很多学生都发愁的问题,本文库为大家提供了排列组合计算公式,希望同学们多多积累,不断进步! 排列 P------和顺序有关组合 C -------不牵涉到顺序的问题排列分顺序,组合不分例如把5本不同的书分给3个人,有几种分法. 排列把5本书分给3个人,有几种分法组合1.排列及计算公式从n个不同元素中,任取m(mn)个元素按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列;从n个不同元素中取出m(mn)个元素的所有排列的个数,叫做从n个不同元素中取出m个元素的排列数,用符号 p(n,m)表示.p(n,m)=n(n-1)(n-2)(n-m+1)= n!/(n-m)!(规定0!=1).2.组合及计算公式从n个不同元素中,任取m(mn)个元素并成一组,叫做从n个不同元素中取出m个元素的一个组合;从n个不同元素中取出m(mn)个元素的所有组合的个数,叫做从n个不同元素中取出m个元素的组合数.用符号c(n,m) 表示.c(n,m)=p(n,m)/m!=n!/((n-m)!*m!);c(n,m)=c(n,n-m);3.其他排列与组合公式从n个元素中取出r个元素的循环排列数=p(n,r)/r=n!/r(n-r)!. n个元素被分成k类,每类的个数分别是n1,n2,...nk这n个元素的全排列数为n!/(n1!*n2!*...*nk!).k类元素,每类的个数无限,从中取出m个元素的组合数为c(m+k-1,m).排列(Pnm(n为下标,m为上标))Pnm=n(n-1)....(n-m+1);Pnm=n!/(n-m)!(注:!是阶乘符号);Pnn(两个n分别为上标和下标) =n!;0!=1;Pn1(n为下标1为上标)=n组合(Cnm(n为下标,m为上标))Cnm=Pnm/Pmm ;Cnm=n!/m!(n-m)!;Cnn(两个n分别为上标和下标) =1 ;Cn1(n为下标1为上标)=n;Cnm=Cnn-m2008-07-08 13:30公式P是指排列,从N个元素取R个进行排列。
排列组合公式/排列组合计算公式排列A------和顺序有关(P和A是一个意思)组合 C -------不牵涉到顺序的问题排列分顺序,组合不分例如把5本不同的书分给3个人,有几种分法. "排列"把5本书分给3个人,有几种分法"组合"1.排列及计算公式从n个不同元素中,任取m(m≤n)个元素按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列;从n个不同元素中取出m(m≤n)个元素的所有排列的个数,叫做从n个不同元素中取出m个元素的排列数,用符号A(n,m)表示.A(n,m)=n(n-1)(n-2)……(n-m+1)= n!/(n-m)!(规定0!=1).2.组合及计算公式从n个不同元素中,任取m(m≤n)个元素并成一组,叫做从n个不同元素中取出m个元素的一个组合;从n个不同元素中取出m(m≤n)个元素的所有组合的个数,叫做从n个不同元素中取出m个元素的组合数.用符号c(n,m) 表示.c(n,m)=p(n,m)/m!=n!/((n-m)!*m!);c(n,m)=c(n,n-m);3.其他排列与组合公式从n个元素中取出r个元素的循环排列数=A(n,r)/r=n!/r(n-r)!.n个元素被分成k类,每类的个数分别是n1,n2,...nk这n个元素的全排列数为n!/(n1!*n2!*...*nk!).k类元素,每类的个数无限,从中取出m个元素的组合数为c(m+k-1,m). 排列(Pnm(n为下标,m为上标))Anm=n×(n-1)....(n-m+1);Anm=n!/(n-m)!(注:!是阶乘符号);Ann(两个n分别为上标和下标)=n!;0!=1;An1(n为下标1为上标)=n组合(Cnm(n为下标,m为上标))Cnm=Anm/Amm ;Cnm=n!/m!(n-m)!;Cnn(两个n分别为上标和下标)=1 ;Cn1(n为下标1为上标)=n;Cnm=Cnn-m2008-07-08 13:30公式P是指排列,从N个元素取R个进行排列。
排列组合公式/排列组合计算公式排列 P------和顺序有关组合 C -------不牵涉到顺序的问题排列分顺序,组合不分例如把5本不同的书分给3个人,有几种分法. "排列"把5本书分给3个人,有几种分法"组合" 1.排列及计算公式从n个不同元素中,任取m(m≤n)个元素按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列;从n个不同元素中取出m(m≤n)个元素的所有排列的个数,叫做从n个不同元素中取出m个元素的排列数,用符号 p(n,m)表示.p(n,m)=n(n-1)(n-2)……(n-m+1)= n!/(n-m)!(规定0!=1).2.组合及计算公式从n个不同元素中,任取m(m≤n)个元素并成一组,叫做从n个不同元素中取出m个元素的一个组合;从n个不同元素中取出m(m≤n)个元素的所有组合的个数,叫做从n个不同元素中取出m个元素的组合数.用符号c(n,m) 表示.c(n,m)=p(n,m)/m!=n!/((n-m)!*m!);c(n,m)=c(n,n-m);3.其他排列与组合公式从n个元素中取出r个元素的循环排列数=p(n,r)/r=n!/r(n-r)!.n个元素被分成k类,每类的个数分别是n1,n2,...nk这n个元素的全排列数为n!/(n1!*n2!*...*nk!).k类元素,每类的个数无限,从中取出m个元素的组合数为c(m+k-1,m).排列(Pnm(n为下标,m为上标))Pnm=n×(n-1)....(n-m+1);Pnm=n!/(n-m)!(注:!是阶乘符号);Pnn(两个n分别为上标和下标) =n!;0!=1;Pn1(n为下标1为上标)=n组合(Cnm(n为下标,m为上标))Cnm=Pnm/Pmm ;Cnm=n!/m!(n-m)!;Cnn(两个n分别为上标和下标) =1 ;Cn1(n为下标1为上标)=n;Cnm=Cnn-m2008-07-08 13:30公式P是指排列,从N个元素取R个进行排列。
欢迎阅读排列组合公式排列定义??? 从n个不同的元素中,取r个不重复的元素,按次序排列,称为从n个中取r个的无重排列。
排列的全体组成的集合用 P(n,r)表示。
排列的个数用P(n,r)表示。
当r=n时称为全排列。
一般不说可重即无重。
可重排列的相应记号为 P(n,r),P(n,r)。
组合定义从n个不同元素中取r个不重复的元素组成一个子集,而不考虑其元素的顺序,称为从n个中取r个的无重组合。
组合的全体组成的集合用C(n,r)表示,组合的个数用C(n,r)表示,对应于可重组合有记号(1)(2)准确理解;(3)(4)(1)12.加法原理的集合形式3.分类的要求每一类中的每一种方法都可以独立地完成此任务;两类不同办法中的具体方法,互不相同(即分类不重);完成此任务的任何一种方法,都属于某一类(即分类不漏)(2)乘法原理和分步计数法1.乘法原理2各步计例1:用集合A集合B把集合AS(A)S(B)例2:从编号为1-9的队员中选6人组成一个队,问有多少种选法?设不同选法构成的集合为C,集合B为数字不重复的六位数的集合。
把集合B分为子集的集合,规则为全部由相同数字组成的数组成一个子集,则每个子集都是某6个数的全排列,即每个子集有6!个元素。
这时集合C的元素与B的子集存在一一对应关系,则S(B)=S(C)*6!S(C)=9!/3!/6!这就是我们用以前的方法求出的C(9,6)以上都是简单的例子,似乎不用弄得这么复杂。
但是集合的观念才是排列组合公式的来源,也是对公式更深刻的认识。
大家可能没有意识到,在我们平时数物品的数量时,说1,2,3,4,5,一共有5个,这时我们就是在把物品的集合与集合(1,2,3,4,5)建立一一对应的关系,正是因为物品数量与集合(1, 2,3,4,5)的元素个数相等,所以我们才说物品共有5个。
我写这篇文章的目的是把这些潜在的思路变得清晰,从而能用它解决更复杂的问题。
例3:999所以集合D例4:用集合A中1排在2在集合B C 中相同数字。
排列组合公式/排列组合计算公式排列P------和顺序有关组合C -------不牵涉到顺序的问题排列分顺序,组合不分例如把5 本不同的书分给3 个人,有几种分法. "排列"把 5 本书分给 3 个人,有几种分法"组合"1.排列及计算公式从n 个不同元素中,任取m(m≤n)个元素按照一定的顺序排成一列,叫做从n 个不同元素中取出m 个元素的一个排列;从n 个不同元素中取出m(m≤n)个元素的所有排列的个数,叫做从n 个不同元素中取出m 个元素的排列数,用符号p(n,m)表示.p(n,m)=n(n-1)(n-2)……(n-m+1)= n!/(n-m)!(规定0!=1).2.组合及计算公式从n 个不同元素中,任取m(m≤n)个元素并成一组,叫做从n 个不同元素中取出m 个元素的一个组合;从n 个不同元素中取出m(m≤n)个元素的所有组合的个数,叫做从n 个不同元素中取出m 个元素的组合数.用符号c(n,m) 表示.c(n,m)=p(n,m)/m!=n!/((n-m)!*m!);c(n,m)=c(n,n-m);3.其他排列与组合公式从n 个元素中取出r 个元素的循环排列数=p(n,r)/r=n!/r(n-r)!.n 个元素被分成k 类,每类的个数分别是n1,n2,...nk 这n 个元素的全排列数为n!/(n1!*n2!*...*nk!).k 类元素,每类的个数无限,从中取出m 个元素的组合数为c(m+k-1,m).排列(Pnm(n 为下标,m 为上标))Pnm=n×(n-1)....(n-m+1);Pnm=n!/(n-m)!(注:!是阶乘符号);Pnn(两个n 分别为上标和下标)=n!;0!=1;Pn1(n 为下标1 为上标)=n组合(Cnm(n 为下标,m 为上标))Cnm=Pnm/Pmm ;Cnm=n!/m!(n-m)!;Cnn(两个n 分别为上标和下标)=1 ;Cn1(n 为下标1 为上标)=n;Cnm=Cnn-m2008-07-08 13:30公式P 是指排列,从N 个元素取R 个进行排列。
排列组合公式排列组合计算公式文件编码(008-TTIG-UTITD-GKBTT-PUUTI-WYTUI-8256)排列组合公式/排列组合计算公式2008-07-08 13:30公式P是指排列,从N个元素取R个进行排列。
公式C是指组合,从N个元素取R个,不进行排列。
N-元素的总个数R参与选择的元素个数!-阶乘,如9!=9*8*7*6*5*4*3*2*1从N倒数r个,表达式应该为n*(n-1)*(n-2)..(n-r+1);因为从n到(n-r+1)个数为n-(n-r+1)=r举例:Q1:有从1到9共计9个号码球,请问,可以组成多少个三位数A1: 123和213是两个不同的排列数。
即对排列顺序有要求的,既属于“排列P”计算范畴。
上问题中,任何一个号码只能用一次,显然不会出现988,997之类的组合,我们可以这么看,百位数有9种可能,十位数则应该有9-1种可能,个位数则应该只有9-1-1种可能,最终共有9*8*7个三位数。
计算公式=P(3,9)=9*8*7,(从9倒数3个的乘积)Q2: 有从1到9共计9个号码球,请问,如果三个一组,代表“三国联盟”,可以组合成多少个“三国联盟”A2: 213组合和312组合,代表同一个组合,只要有三个号码球在一起即可。
即不要求顺序的,属于“组合C”计算范畴。
上问题中,将所有的包括排列数的个数去除掉属于重复的个数即为最终组合数C(3,9)=9*8*7/3*2*1排列、组合的概念和公式典型例题分析例1设有3名学生和4个课外小组.(1)每名学生都只参加一个课外小组;(2)每名学生都只参加一个课外小组,而且每个小组至多有一名学生参加.各有多少种不同方法解(1)由于每名学生都可以参加4个课外小组中的任何一个,而不限制每个课外小组的人数,因此共有种不同方法.(2)由于每名学生都只参加一个课外小组,而且每个小组至多有一名学生参加,因此共有种不同方法.点评由于要让3名学生逐个选择课外小组,故两问都用乘法原理进行计算.例2 排成一行,其中不排第一,不排第二,不排第三,不排第四的不同排法共有多少种解依题意,符合要求的排法可分为第一个排、、中的某一个,共3类,每一类中不同排法可采用画“树图”的方式逐一排出:∴ 符合题意的不同排法共有9种.点评按照分“类”的思路,本题应用了加法原理.为把握不同排法的规律,“树图”是一种具有直观形象的有效做法,也是解决计数问题的一种数学模型.例3判断下列问题是排列问题还是组合问题并计算出结果.(1)高三年级学生会有11人:①每两人互通一封信,共通了多少封信②每两人互握了一次手,共握了多少次手(2)高二年级数学课外小组共10人:①从中选一名正组长和一名副组长,共有多少种不同的选法②从中选2名参加省数学竞赛,有多少种不同的选法(3)有2,3,5,7,11,13,17,19八个质数:①从中任取两个数求它们的商可以有多少种不同的商②从中任取两个求它的积,可以得到多少个不同的积(4)有8盆花:①从中选出2盆分别给甲乙两人每人一盆,有多少种不同的选法②从中选出2盆放在教室有多少种不同的选法分析(1)①由于每人互通一封信,甲给乙的信与乙给甲的信是不同的两封信,所以与顺序有关是排列;②由于每两人互握一次手,甲与乙握手,乙与甲握手是同一次握手,与顺序无关,所以是组合问题.其他类似分析.(1)①是排列问题,共用了封信;②是组合问题,共需握手(次).(2)①是排列问题,共有(种)不同的选法;②是组合问题,共有种不同的选法.(3)①是排列问题,共有种不同的商;②是组合问题,共有种不同的积.(4)①是排列问题,共有种不同的选法;②是组合问题,共有种不同的选法.例4证明.证明左式右式.∴ 等式成立.点评这是一个排列数等式的证明问题,选用阶乘之商的形式,并利用阶乘的性质,可使变形过程得以简化.例5 化简.解法一原式解法二原式点评解法一选用了组合数公式的阶乘形式,并利用阶乘的性质;解法二选用了组合数的两个性质,都使变形过程得以简化.例6 解方程:(1);(2).解(1)原方程解得.(2)原方程可变为∵ ,,∴ 原方程可化为.即,解得第六章排列组合、二项式定理一、考纲要求1.掌握加法原理及乘法原理,并能用这两个原理分析解决一些简单的问题.2.理解排列、组合的意义,掌握排列数、组合数的计算公式和组合数的性质,并能用它们解决一些简单的问题.3.掌握二项式定理和二项式系数的性质,并能用它们计算和论证一些简单问题.二、知识结构三、知识点、能力点提示(一)加法原理乘法原理说明加法原理、乘法原理是学习排列组合的基础,掌握此两原理为处理排列、组合中有关问题提供了理论根据.例15位高中毕业生,准备报考3所高等院校,每人报且只报一所,不同的报名方法共有多少种解:5个学生中每人都可以在3所高等院校中任选一所报名,因而每个学生都有3种不同的报名方法,根据乘法原理,得到不同报名方法总共有3×3×3×3×3=35(种)(二)排列、排列数公式说明排列、排列数公式及解排列的应用题,在中学代数中较为独特,它研究的对象以及研究问题的方法都和前面掌握的知识不同,内容抽象,解题方法比较灵活,历届高考主要考查排列的应用题,都是选择题或填空题考查.例2由数字1、2、3、4、5组成没有重复数字的五位数,其中小于50 000的偶数共有()个个个个解因为要求是偶数,个位数只能是2或4的排法有P1;小于50 000的五位数,2万位只能是1、3或2、4中剩下的一个的排法有P13;在首末两位数排定后,中间3个位数的排法有P33,得P13P33P12=36(个)由此可知此题应选C.例3将数字1、2、3、4填入标号为1、2、3、4的四个方格里,每格填一个数字,则每个方格的标号与所填的数字均不同的填法有多少种解:将数字1填入第2方格,则每个方格的标号与所填的数字均不相同的填法有3种,即214 3,3142,4123;同样将数字1填入第3方格,也对应着3种填法;将数字1填入第4方格,也对应3种填法,因此共有填法为3P13=9(种).例四例五可能有问题,等思考三)组合、组合数公式、组合数的两个性质说明历届高考均有这方面的题目出现,主要考查排列组合的应用题,且基本上都是由选择题或填空题考查.例4从4台甲型和5台乙型电视机中任意取出3台,其中至少有甲型与乙型电视机各1台,则不同的取法共有()种种种种解:抽出的3台电视机中甲型1台乙型2台的取法有C14·C25种;甲型2台乙型1台的取法有C24·C15种根据加法原理可得总的取法有C24·C25+C24·C15=40+30=70(种 )可知此题应选C.例5甲、乙、丙、丁四个公司承包8项工程,甲公司承包3项,乙公司承包1 项,丙、丁公司各承包2项,问共有多少种承包方式解:甲公司从8项工程中选出3项工程的方式 C38种;乙公司从甲公司挑选后余下的5项工程中选出1项工程的方式有C15种;丙公司从甲乙两公司挑选后余下的4项工程中选出2项工程的方式有C24种;丁公司从甲、乙、丙三个公司挑选后余下的2项工程中选出2项工程的方式有C 22种.根据乘法原理可得承包方式的种数有C 3 8×C 15×C 24×C 22= ×1=1680(种). (四)二项式定理、二项展开式的性质说明二项式定理揭示了二项式的正整数次幂的展开法则,在数学中它是常用的基础知识 ,从1985年至1998年历届高考均有这方面的题目出现,主要考查二项展开式中通项公式等,题型主要为选择题或填空题. 例6在(x- )10的展开式中,x 6的系数是() -27CB.27C 410-9CD.9C 410解设(x- )10的展开式中第γ+1项含x 6, 因T γ+1=C γ10x 10-γ(- )γ,10-γ=6,γ=4于是展开式中第5项含x 6,第5项系数是C 410(- )4=9C 410 故此题应选D.例7(x-1)-(x-1)2+(x-1)3-(x-1)+(x-1)5的展开式中的x 2的系数等于解:此题可视为首项为x-1,公比为-(x-1)的等比数列的前5项的和,则其和为 在(x-1)6中含x 3的项是C 36x 3(-1)3=-20x 3,因此展开式中x 2的系数是-2 0. (五)综合例题赏析例8若(2x+ )4=a 0+a 1x+a 2x 2+a 3x 3+a 4x 4,则(a 0+a 2+a 4)2-(a 1+a 3)2的值为()解:A.例92名医生和4名护士被分配到2所学校为学生体检,每校分配1名医生和2 名护士,不同的分配方法共有() 种种种种解分医生的方法有P 22=2种,分护士方法有C 24=6种,所以共有6×2=12种不同的分配方法。
排列组合算法总结(基于C++实现)
全排列n!
1.1 递归法
设一组数p = {r1, r2, r3, … ,rn}, 全排列为perm(p),pn = p –{rn}。
则perm(p) = r1perm(p1), r2perm(p2), r3perm(p3), … , rnperm(pn)。
当n = 1时perm(p} = r1。
如:求{1, 2, 3, 4, 5}的全排列
1、首先看最后两个数4, 5。
它们的全排列为4 5和5 4, 即以4开头的5的全排列和以5开头的4的全排列。
由于一个数的全排列就是其本身,从而得到以上结果。
2、再看后三个数3, 4, 5。
它们的全排列为3 4 5、3 5 4、 4 3 5、4 5
3、 5 3
4、 5 4 3 六组数。
即以3开头的和4,5的全排列的组合、以4开头的和3,5的全排列的组合和以5开头的和3,4的全排列的组合.
#include iostream
using namespace std;
void Perm(int start, int end, int a[]) {
--得到全排列的一种情况,输出结果
if (start == end) {
for (int i = 0; i end; i++)
cout a[i] ' ';
cout endl;
for (int i = start; i end; i++) {
swap(a[start], a[i]); --交换
Perm(start + 1, end, a); --分解为子问题a[start+1.,end-1]的全排列
swap(a[i], a[start]); --回溯
int main() {
int i, n, a[10];
while (cin n, n) {
for (i = 0; i n; i++)
a[i] = i + 1;
Perm(0, n, a);
return 0;
C(n,k),n个数中任取k个数
2.1 递归法
实际上就是在n个数中,标记k个数,然后输出这k个数的过程。
使用一个visited数组来记录相应下标的数是否被选中。
#include iostream
using namespace std;
void dfs(int pos, int cnt, int n, int k, int a[],bool visited[]) {
--已标记了k个数,输出结果
if (cnt == k) {
for (int i = 0; i n; i++)
if (visited[i]) cout a[i] ' ';
cout endl;
--处理到最后一个数,直接返回
if (pos == n) return;
--如果a[pos]没有被选中
if (!visited[pos]) {
--选中a[pos]
visited[pos] = true;
--处理在子串a[pos+1, n-1]中取出k-1个数的子问题 dfs(pos + 1, cnt + 1, n, k, a,visited);
visited[pos] = false;
--处理在子串a[pos+1, n-1]中取出k个数的问题
dfs(pos + 1, cnt, n, k, a, visited);
int main() {
int i, n, k;
while (cin n k, n || k)
int *a = new int[n];
bool *visited = new bool[n];
for (i = 0; i n; i++)
a[i] = i + 1;
visited[i] = false;
dfs(0, 0, n, k, a, visited);
delete[] a;
delete[] visited;
getchar();
return 0;
2.2 ‘01’转换法
本程序的思路是开一个数组,其下标表示1到n个数,数组元素的值为1表示其代表的数被选中,为0则没选中。
首先初始化,将数组前n个元素置1,表示第一个组合为前n个数。
然后从左到右扫描数组元素值的“10”组合,找到第一个“10”组合后将其变为“01”组合,同时将其左边的所有“1”全部移动到数组的最左端。
当第一个“1”移动到数组的n-m的位置,即n个“1”全部移动到最右端时,就得到了最后一个组合。
例如求5中选3的组合:
1 1 1 0 0 --1,2,3
1 1 0 1 0 --1,2,4
1 0 1 1 0 --1,3,4
0 1 1 1 0 --2,3,4
1 1 0 0 1 --1,2,5
1 0 1 0 1 --1,3,5
0 1 1 0 1 --2,3,5
1 0 0 1 1 --1,4,5
0 1 0 1 1 --2,4,5
0 0 1 1 1 --3,4,5
#include iostream
using namespace std;
--输出结果
void printRes(int* a, bool* index, int n) for (int i=0;in;i++)
if (index[i])
cout a[i] " ";
cout endl;
--检查最后k个位置是否已全变成0
bool hasDone(bool* index, int n, int k) for (int i=n-1;i=n-k;i--)
if (!index[i])
return false;
return true;
void Comb(int* a, int n, int k)
bool *index = new bool[n]();
--选中前k个位置
for (int i = 0; i k; i++)
index[i] = true;
printRes(a, index, n);
while (!hasDone(index, n, k))
--从左到右扫描数组
for (int i = 0; i n - 1; i++)
--找到第一个“10”组合将其变成"01"组合 if (index[i] !index[i + 1])
index[i] = false;
index[i + 1] = true;
--将"01"组合左边的1移到最左边
int count = 0;
for (int j = 0; j i; j++)
if (index[j])
index[j] = false;
index[count++] = true;
printRes(a, index, n);
delete[] index;
int main()
while (cinnk)
int *a = new int[n]();
for (int i = 0; i n; i++)
a[i] = i+1;
Comb(a, n, k);
delete[] a;
return 0;
Permutation(data, 0, 4, nCount);
比如,如果数组num初始化为2,3,1,那么输出就变为了:{2 3 1} {3
1 2} {3
2 1}
⒊分类的要求:每一类中的每一种方法都可以独立地完成此任务;两类不同办法中的具体方法,互不相同(即分类不重);完成此任务的任何一种方法,都属于某一类(即分类不漏)。
首先从各大IT公司的题中总结出排列组合的对象都是整形数组或字符数组,排列问题可以按输入数据分为两大类:输入数据有重复和无重复,又可以按输出数据分为两大类:输出数据有重复和无重复;而排列问题也偶尔会考非递归。
第二类stirling数:S(n,m)=S(n-1,m-1)+m*S(n-1,m).
for(int j=1; j=maxn; j++)
if(temp (1j)) --对应位上为1,则输出对应的字符
value[i]=i+1;--此处是赋初值,以1,2,3,4,5为例,当然任何数字都可以
组合的定义:从n个不同元素中,任取m(m≤n)个元素并成一组,叫做从n个不同元素中取出m个元素的一个组合;从n个不同元素中取出m(m≤n)个元素的所有组合的个数,叫做从n个不同元素中取出m个元素的组合数。
用符号 C(n,m) 表示:
区别:分类计数原理是加法原理,不同的类加起来就是我要得到的总数;分步计数原理是乘法原理,是同一事件分成若干步骤,每个步骤的方法数相乘才是总数。