排列组合的生成

1、3.计数 Counting3.1 排列 Permutations(置换)3.1.1 乘积集合 P roduct Sets,卡氏积 Cartesian Product设A,B是两个集合，元素 aA, b亡B，称(a,b)为一个序对，或序偶 ordered pair。(a,b)=(c,d)当且仅当 a=CAb=d定义乘积集合AXB =(a,b)| a定理 1 乘法原理 Multi pl icati on P rici pie|AXB|=|A|>qB|假设依次实行Ti,T2两种任务，如果做 Ti有ni种不同的办法，做T2有门2种不同的办法，则 共有山呦2种方法完成任务T订2。定理2乘法原理推广

2、|AiXA2 XAk|=|AiP<|A2衣|Ak|假设依次实行任务Ti, T2,Tk,如果做Ti有ni种不同的办法，做T2有n2种不同的办法，做Tk有nk种不同的办法，贝y共有ni>cn2X.xnk种方法完成任务 丁订2Tk。例1. a)用1, 2, 3, 4, 5可以组成多少个不同的三位数？b)用0, 1, 2, 3, 4, 5可以组成多少个不同的三位数？解 a)第一位有5种取法，第二位，第三位也都有5种取法，共组成53=125 个不同的三位数。b)第一位有5种取法，第二位，第三位有6种取法，共组成 爭62=18O 个不同的三位数。例2. n个元素的集合A共有多少个子集?解由第一

3、章知可以用n个1的数组表示A, A的子集可以用长度为n的0,1序列表示。每一位可以取0或1,两种取法，共有2X2X2X 、2=2n种不同的01 串，对应2n个不同的子集。定理3.从n个元素的集合A中可重复地取出r个元素排成一列,共有nr种不同的取法。定理共有排列Permuations 有 Pn 种,4.从n个元素的集合A中不重复地取出r个元素排成一列,n(n-1)(n-叶1)种不同的取法。简称n个元素中取r个元素的排列 Pn = n（n-1）（n-r+1）=（门 _）！= n r全排列 从n个元素的集合A中不重复地取出n个元素排成一列,共有n!种不同的取法。简称n个元素的全排列Permuati

4、ons 有 R种，Pn =n!重集有重复元素的集合collectiona,a,a,b,c,a,b,b,c,c,c,a,a,a,b,b,c,c,c,c分别记作3a,b,c, a,2b,3c, 3a,2b,4c重集的全排列3a,b,c的全排列，看成5个元素的全排列共5!个。其中3个a与不同次序无关，每个排列重复出现3!次。去除重复共有不同的排列5!3! =20 个。6!关，每个排列重复出现 2! >3!次。去除重复共有不同的排列2!3! =60个。9! 3a,2b,4c的全排列，共有 3!2!4! =1260 个定理5. n个元素的重集kiai,k2a2,Ka的不同的全排列共有n!k1!k2

5、r k,!个。英文单词BANANA中所有字符组成的不同的全排列有多少个?6!3.2定理cncn例1.c523!2!1!=60个组合 Combinations1. n个物体中一次取出r个不同元素的组合，共有n!r!(n-r)!种不同取法。Pnrnrn!r!r!r!(n- r)!。52张扑克牌中一次取5张，有多少不同的取法垢2!52咒 51 50 49咒 485!54咒3乂2乂1=2,598,9603.2.1无穷重集的组合n个元素的集合ai,a2,an中可重复地取k个元素的组合数从n个元素的无穷重集 ca1,比32,严an中一次取k个元素的组合数a1a1| 32 a2 a2 | as | an a

6、n an an0 0 1 0 0 0 1 10 0 0相当于k个0, n-1个1的不同排列共有(n+ k-1)! c n-1 pkn(n +1)"' (n 中 k 1)nkk!k!一一ck定理2. n个元素的集合a1,a2,an中可重复地取k个元素的组合数为 Cn +k-1 =丘！。例2.一个电台有奖竞猜奖品为十佳 CD中可重复地任选三张，问有多少种不同 的选法？c3c310 卩 12"仆10Cl0+3T=Ci2=-r=FFr=220排列：与先后次序有关。组合：与次序无关。n个元素的集合ai,a2,an中可重复地取k个元素，每个元素至少取一个的组合数,相当于n个元素

7、的集合ai,a2,an中可重复地取k-n个元素的组合数:Qk-nk-n nTCn + (k-n)T = CkT =CkT(k-n)!-n(n+1)(k-1) k - 1(k- n)! = (n - 1)!(k - n)!k-lLi推论3. n个元素的集合a1,a2,an中可重复地取k个元素，每个元素至少取一个的组合数为Cn-1k-1。例3.四种月饼装盒，每盒8块，每种月饼至少一块，一共可装多少种不同的月 饼盒？解 相当于每盒4块月饼，共可装厂37咒6咒5C7 = 3咒 2天 1 =35种。322有穷重集的组合定理3. 设k< ki,k2,kn,从n种元素的重集kiai,k2a2,knan

8、中取k个元素的不同的组Ck合数为J'n + k-1。如果k不一定小于ki,k2,kn,则要用容斥原理。例4.求重集3a, 4b, 5c中取10个元素的组合数。解法 1. 令 A=Ka, Kb, Kc.A的10组合数P(a): A 的10组合中多于A的6组合数P(b): A 的10组合中多于P(c): A 的A的5组合数10组合中多于A的4组合数Ci22 = g =6623个a :蛍4个b :5个c :C 6P(a) n P(b): A的10组合中多于3个a ,C 24个b: A的1组合数 C3P(a)n P(c): A的10组合中多于3个a ,5个c: A的0组合数 C；P(b) n

9、P(c): A的10组合中多于4个b,5个c: A的-1组合数 0P(a)n P(b) n P(c): A的10组合中多于3个a ,4个b, 5个c:A的-5组合数 0Q 2 c2 Q 2 Q 2 C 2 共有 66 C 8 C7 C 6 + C 3 + C 2 =6 重集3a, 4b, 5c中取10个元素的组合数等于6。解法2.重集3a, 4b, 5c的10组合数等于2组合数：C3+2-1 = C4 =6.方程Xi+X2+Xn=k的非零整数解的个数相当于从重集kiai,k2a2,knan中取Ckk个元素的不同的组合数 J n + k-1。求方程X1+X2+xn=k的正整数解的个数相当于从重集

10、kiai,k2a2,knan中取C n -1k个元素,每个元素至少取一个的不同的组合数Ck-1例5.求方程X1+X2+X3鸟的正整数解的个数。解 Xi+X2+X3=3解数C2X1+X2+X3=4解数C3X1+X2+X3=5Xi+X2+X3=6解数C52共有C2 + C： + c|=C6=3JJ=204563咒2咒1个解。例6.三个小孩分 法。2n+1个苹果，任意两个之和都不少于第三人，共有多少种分C2三个小孩分2n+1个苹果，共有 C2n + 3种分法。有两个之和少于第三人，例如 X1+X2<X3,从而 X1+X2+ X3< 2X3,2n + 1X3>并12Xn+1 或 X2

11、帀+1 或 xi3n+1相当于三人分n个苹果:于是，任意两个之和都不少于第三人的分法有,C2 厂2 n(n+1) 匕2n+3 飞 Cn +2 =? 种。3.3 鸽笼原理 Pigeonhole PrincipieTheorem 1(The pigeon hole principle)n个鸽子放进m个鸽笼里，如果mvn则至少有一个鸽笼放两个或两个以上鸽子。例1 .信息学院一二年级学生中一定有生日相同的学生。解 信息学院一二年级共有学生400人，400>366,所以至少有两人同一生日。例2.从1到8中任选5个数，其中必有相加得9的两个数。证明 将 1-8 分成四个不同集合A1=1,8, A 2

12、=2,7, A 3=3,6, A 1=4,5.由鸽笼原理，任选5个数至少有两个在一组，相加得 9。例3 .从1-20中任选11个数一定有一个是另一个的倍数。证明.任意一个数都可以分解为若干个n=2 kmm是奇数。设n1=2km,n2=2lm有相同的奇数因子，若2和一个奇数的乘积:k勺，贝y ni|n2,反之 n2|ni.1-20中任意一个数的奇数因子都小于 有相同的奇数因子。因此一个是另一个的倍数。20,至多10个。由鸽笼原理，11个数中至少有两个例4.任意6个人中一定有三个人互相认识，或有三个人互相不认识。证明 用6个点a1,a2,a6表示6个人，两人认识用一条红色边相连，两人不认识用一 条

13、蓝色边相连。我们证明这个图中一定有一个红色三角形，或蓝色三角形。从某一点a1出发有5条边，由鸽笼原理一定有一种颜色的三条边，比如有三条红色边，相连的三个点为a2,a3,a4。如果a2,a 3,a 4三点中有红色边，则他们与a1组成一个红色三角形。如果a2,a 3,a 4三点中没有红色边，则 a2,a 3,a 4组成一个蓝色三角形。广义鸽笼原理 The Exte nded Pigeo nhole Prin ci pien个鸽子放进m个鸽笼，则必有一个鸽笼至少放L(n-1)/m+1个鸽子。例5. 100个人中至少有9个人同月出生。解由广义鸽笼原理(100-1)/12>1=93.4 概率基础

14、Elements of Probability八羊本Sam pie一次测试得到的结果叫样本。羊本空间Sam pie Sp ace一个测试的所有结果组成的集合叫样本空间。例1掷两个硬币不同的观察方法可以得到的样本空间：看几个国徽：A =0,1,2分别两个正反面：A=HH,HT,TH,TT看两个硬币同正反：A3=M,N样本空间要先决定，可以无限。本书只考虑有限样本空间。例2.一个骰子掷两次，得到两个数字，样本空间：A=( n, m)|1 切,m§, |A|=36.例3.盒子里又四个一分和五个一毛硬币，依次从盒子里取出三个硬币，得到的样本空间：A= PPP,PPD,PDP,P DD,D P

15、P,DP D,DD P, DDD |A|=8.事件Events测试结果适合某种特定条件的陈述。 事件可以用适合条件的样本集合表示。例4. (a)例2中两次和为8的事件B=(2,6),(3,5),(4,4),(5,3),(6,2).|B|=5.(b)例2中两次和至少为10的事件C=(4,6),(5,5),(5,6),(6,4),(6,5),(6,6)|C|=6必然事件 certai n eve nt :事件的集合=样本空间不可能事件impo ssible eve nt事件的集合=空集事件的运算如果事件事件E,F是事件，则EU F, E n F, E也是事件。EU F发生U事件E或F发生。E发生二

16、事件E不发生。En F发生台 事件E和F都发生。事件例5掷骰子测试，事件E是读数为偶数E=2,4,6,事件F是读数为素数 F=2,3,5.EU F=2,3,4,5,6读数是偶数或素数。 E n F =2读数既是偶数又是素数。E =1，3，5读数不是偶数.互相排斥或互相独立事件事件E,F称为互相排斥或互相独立mutually exclusive ， or disjoint ，如果E n F=0, E,F不交.即E,F不能同时发生。事件 Ei,E2, ,En称为互相排斥，互相独立 mutually exclusive , or disjoint，如果其中任意两个互相排斥或互相独立。若Ei发生，则其

17、他事件都不会发生。事件 E 的概率 p(E), probability of the event E事件的频率freque ncy of occurre nee of the eve nt E总共测试n次，其中事件E发生nE次，事件E发生的频率nfE=n事件的概率 Probability of the event E测试次数充分大时，频率fE的极限叫E的概率p(E)例6.掷骰子测试，正面向上和反面向上的概率都是1/2概率的性质P1: 0 虫(E) <1,对任何 EGA.P2: p( A)=1, p( 0)=0 .P3：如果事件E1,E2,En互相排斥，互相独立，则p(E1U E2U U

18、En)= p(E 1)+P(E2)+ +p(En).称P1,P2,P3为概率公理。满足概率公理space。P1,P2,P3的一个概率叫做概率空间probability设A是一个概率空间， A= x i,x 2, ,x 每个x k叫做基本事件 elementary event probability ，由概率公理。令 pk=p(x k)叫基本概率 elementaryEP1: 0卑k兰EP2: p 1+P2+ Pn =1已知基本概率 p1，P2,，Pn，就可以计算任意事件E的概率。例&假设一个测试的样本空间 A=1,2,3,4,5,6,基本概率如下:P1=P2= = P6 = 1/12,

19、 P 3 = 1/3, P 4=1/6, P 5=1/4,事件 E=2,4,6,则 p(E)=1/12+1/6+1/12=1/3.等概率事件假设基本概率都相等，则 Pl=p 2=Pn=1/n.P (xii,Xi2,Xi3)=3/n.E=Xi1,Xi2,Xik|E|P(E)=面例9.从52张扑克牌中随机选取4张牌，选到4张k的概率是多少?解这是等概率事件，从52张扑克牌中选取4张牌的取法共有C52种，取得4张king的 概率 p(E)=1/ c52 .例10.从装有六个红球和四个绿球的盒子里随机选取四个球，选到两个红球两 个绿球的概率是多少？解 一盒10个球，选4个共有 C10种,6个红球中选出

20、2个，共有 C 6种，4个绿球中两个共有 C4种，由乘法原理10个球中C 2 X C 25C415 冥 6P(E)= C 4= 210 =0.428571.选出两红两绿共有 C6 X C4 种。C4C10例11.一个正六面体骰子掷三次，事件E为三个数字相同或一个都不是 4。求P(E).解.这也是等概率事件。一个骰子掷一次，可得 6个数，掷三次可得 63个可能的结果。E= F U GF:三次读数相同。G:没有4。|F|=6,|G|=125, |F n G|=5,|E|=|F|+|GHF n G|=126p(E)=126/216=7/12.例12从装有六个红球和四个绿球的盒子里随机选取四个球。(a

21、)事件E是红球不多于 2个，求P(E).(b)事件F是红球不多于 3个，求p(F). 解 (a)令 E= E0 U E1 U 巳E0表示不取红球|E 0|=1B表示取一个红球 |E 1|=24E2表示取二个红球 |E 2|=9OEd, E1，E2互相独立。|E|=|E oU E1U E2|=|E o|+|E 1|+|E 2|=115P(E)=115/21O=23/42(b)F = E4 ,|E 4|=15,p( F )=p(E)=15/21O=1/14p(F)=1-p(F )=1-1/14=13/14.概率常用于计算机算法平均时间复杂性的估计。例13.从长度为10的数组中查找一个关键词所需的平

22、均计算步骤为等概率事件(1+2+3+ +10) /10=5.53.5 递推关系 Recurrence Relations例1. Fibonacci Sequence菲波纳奇数列(a) an=an-1 + 1, a1=4等差数列.(b) fn=fn-1+f n-2, f1=f2=1.递推关系必须有(a)初始条件initial condition,要有(b)递推条件recurrence condition。令 A=0,1,推关系：C1=2:C2=3 :以cn表示A*中长度为n,不含连续两个0的串的个数，给出cn的递C3=5 :0，101， 10， 11010， 011， 101， 110， 111

23、0*,1*两种，不能00，只有01#和1*两种#是长n-2串，*是长n-1串 递推公式Cn=Cn-1 +Cn-2Cn初始条件C1=2，C2=3。Cn = fn+2回溯法从递推关系 recurrence relaion 求显示公式 exp licitformula例4.&=an-i+3, ai=2an=an-i+3 =an-2+2x3 an=an-3+3x3=ai+(n-i) x3=2+3(n-i) bn=2bn-什 i,bi=7bn+i=2bn-i +2=2(bn-i+i)=22 (bn-2+i) =2n-i(bi+i)= 2n+2 bn=2n+2-ik阶线性齐次递推关系an= r i

24、 an-i + r2an-2+ + rkan-k特征方程 characteristic equationnn-in-2n-kX = rix + r2X + + rkx定理1.(1)如果递归关系的an= rian-i + r2an-2特征方程x2= rix +2有两个不同的根xi, X2，则数列的显式通项公式是：nnan=ClXi +C2X2其中常数Ci,C2由初始条件确定。如果特征方程x2= rix +2只有一个重根X,则数列的显式通项公式是n nan=ClX +C2X其中常数Ci,C2由初始条件确定。口口dnnn-22n-22证明.an =ci Xi +C2X2 = C1X1Xi +C2X2

25、 X2n-2 .n-2.=CiXi(rixi+r2)+ C2X2 (riX2+r2)n-in-2n-in-2=ri Ci Xi+r2 CiXi+ri C2X2+r2 C2X2< n-i n-i > <n-2 n-2>=ri (CiXi+ C2X2) +r2(CiXi+ C2X2) =ri an-i+r2an-2例7.求递推关系cn= 3cn-i - 2an-2，ai=5, a2=3的显式通项公式。 解.特征方程x2=3x-2的两个根是i和2。丄n_nan =ci i +C22ci +2c2=5ci +4c2=3ci=7,C2=-1由此得到an =7-2n例9.求Fib

26、on acciSeque nee菲波纳奇数列的通项公式。Fibonacci Sequenc的递推公式:fn=fn-1 +fn-2, f1 =f2= 1 解 Fibonacci Sequenc 的特征方程 x2-x-1=0特征方程的解：1 + V51 V5x1= 2，X2=由定理1, Fibonacci Sequenc啲通项公式: fn=C1X1n+C2 X2n1 + 751-45 “C1+C2=12 2C1h+Q2h-45+C2丿 V.¥=11(1 + Qn 11-Q75 1 2 丿 751 2丿fn =例10.证明fnVProof.(by strong induction)P(n)

27、：fn< P(1):1V5/3 true(b)AssumeVi<kP(i):We show that P(k) is true:kJk-2k-2J f+=-+ 1 V£丿'3丿3l3丿1fk= fk-1 +fk-2V飞k5 3丿.The induction is finished com pletely.错位排歹y alternate permutation 例1. 4个汽车轮子换位，要求每个轮子都不在原位，有多少种方法?A=1,2,3,4214323412413341231423421431241234321例2.A=1,2,n A的错位排列有多少种？ A的错位

28、排列是A的一个排列, 每个k都不在k位，k=1,2,n.用Dn表示n个元素序列的错位排列的个数。D1=0, D2=1, D3=2, D4=9,第一位放k韵，共有n-1种取法；第一位放k，第k位放1, 其余n-2位错位排列有Dn-2种取法；第一位放k，第k位不放1,除第一位外，其余n-1位 错位排列有Dn-1种取法；Dn=( n-1)(Dn-2+Dn-1) Dn nDn-1=(n -1)D n-2Dn-1=(Dn-1 - (n-1)Dn-2)2=(1) (Dn-2 - (n-2)Dn-3)-1)n2 (D2 - 2Di)-1严DnD4D5n Dn-什(-1)n-24x2+1=95%9_1=44 用容斥原理求Dn用Ai表示i放在第i位。|Ai|=( n-1)!|AiG Aj|= (n-2)!|AiG AjP Ak |= (n-3)!Dn=| A n A2 nn 人 |=冋_|AqUu 代 | =|A|-2： I A 1+