内容课件案例复习

1、安排 时间：1月13日晚6点半-9点地点：建馆报告厅 答疑时间：1月10日下午2pm-5pm，东主楼8-4021月13日下午2pm-4:30pm，东主楼8-402题型 5道解答或者证明题,一题中可能有多问五章内容不排列生成: myc 考卷上请写明学号，姓名，号码，1第一章 排列与组合计数基本原理 加法法则:若 |A| = m , |B| = n , AÇB = Æ , 则|AÈB| = m + n 在加法法则中要注意A 和B 的互斥 乘法法则:若 |A| = m , |B| = n ,A´B = (a,b) | a ÎA,b Î B,

2、 则 |A ´ B| =m · n 在乘法法则中要注意A 和B 的相互性排列从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的无重排列。排列的全体组成的集合用P(n,r)表示。排列的个数用P(n,r)表示。当r=n时称为全排列。P(n,r)=n(n-1)(n-r+1)组合从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合。组合的全体组成的集合用C(n,r)表示，组合的个数 用C(n,r)表示， C(n,r)=P(n,r)/r!=n!/(r!(n-r)!) 重复的排列(多重集排列): 求r1个1，r2个2，

3、rt个t的排列数，设r1+r2+rt=n,设此排列数为P(n;r1,r2,rt),对1，2，t分别加下标，得到 P(n；r1,r2,rt)·r1!·r2!··rt! = n!nn! P(n；r1,r2,rt)= =( r)r2 rt r1!r2!rt!1 圆周排列 从n个中取r个的圆排列的排列数为 P(n,r)/r ,项链排列2rnP(n,r)/2r ,3rn 在圆排列的基础上，正面向上和向上两种方式放置各 个数是同一个排列。重复的组合(多重集的组合) n个不同的元素中取r个做重复的组合,其组合数为C(n+r-1,r) 线性方程非负整数解x1+x2+xn

4、=b的非负整数解的个数C(n+b-1,b)不相邻的组合 n个数中取r个作不相邻的组合,组合数为C(n-r+1,r)多重集的组合给三个孩子发水果,一共12个一样的,每个孩子至少有一个水果,问有多少种分法?解:设分给第i个孩子的水果数为xi, xi1x1+x2+x3=12令y1=x1-1,y2=x2-1,y3=x3-1 y1+y2+y3=9 yi0 非负整数解的个数为C(9+3-1,9)=55不考的内容 排列，组合的生成 Stirling公式第二章 递推与母函数 二项式定理 (x+y)n=C(n,k)xn-kykk=0-n (1+x)n= C(n,k)xn-kk=0-n多项式定理 (x1+x2+x

5、t)n=C(n;r1,r2,.rt)x1r1x2r2xtrtr1+r2+rt=n因式分解一元二次方程求解 多项式长除法求解组合母函数对于序列a0 , a1 , a2 ,L, 构造一函数：G(x) = a + a x + a+L,x2012称函数G(x)是序列a0 , a1, a2 ,L的母函数 指数求解排列函数a0 , a1 , a2 ,L对于序列，函数+ a1x + a2+ a3G (x) = ax2x3e01!2!3!+L+ ak+Lxk k!a0 , a1 , a2 ,L称为是序列的指数函数常用母函数数列 1n 0 母函数1/(1- x)= 1+x+x2+函数ex指数数列 母函数1/(1

6、- cx)= 1+cx+c2x2+0函数ecx指数1+ 2x + 3)2k + 2¥¥11å)x= å(1 +x+L=(k + 1)(k + 2) =3k1 - x)3(22 k =0 k =03e- x= 1- +L, 3!5+L5!sin x =递推 Hanoi Fibonacci数列 铺砖 N位序列中符合某些性质的排列数 放球 .线性常系数递推定义 如果序列an 满足= 0,(2 - 5 -1)+ C1an-1 + C2 an-2+L+ Ck an-kan(2 - 5 - 2)a0 = d0 , a1 = d1 ,L, ak -1 = dk -1

7、,，Ck ¹ 0 ，则C1, C2 ,LCk及 d0 , d1,Ldk-1是(2 - 5 -1)称为 an 的k阶常系数线性递推(2 - 5 - 2)称为an 的初始条件， + C xk -1C(x) = xk+L+ Cx + Ck -11k称为an 的特征多项式线性常系数递推 确定特征多项式 特征方程根的情况非重根共轭复根多重根 利用系数an的前若干项求解待定系数 确定an总结线性常系数递推根据特征多项式C(x)的非零解的情况( ) =x(-a1 )(a- x2 )L( a-)1)有k个不同非零实数解Cxxk= ln+L+nlana其中l ,1aln1122kkl ,2Lk,是l待

8、定,系数2)有一对共轭复根a= reiq 和a= re-iq 时，12= A rcosq +nrsinqannBnn 其中A，B是待定。3)有k重根。不妨设a1是k重根。-1)Aa+A+nL +kn或nA(k -1011æ n öæ n öæ n öæönçA1÷ + A2 ç÷ + A3 ç÷+.+Ak -1 ç÷a+nA()01è k - 1ø1è2ø3øèè&#

9、248;14其中A,A ,L A,是k个待定。 01k -1母函数法求多重集的组合 给三个孩子发水果,一共12个一样的,每个孩子至少有一个水果,问有多少种分法? 解:母函数为,G(x)=(x+x2+x3+x4+)(x+x2+x3+x4+)(x+x2+x3+x4+)=(x/(1-x)3求x12的系数,即1/(1-x)3中的x9的系数.x=1是三重根an=A+Bn+Cn2 a0=1,a1=3,a2=3+3=6A=1; A+B+C=3,A+2B+4C=6A=1 B=1.5 C=0.5 an=1+1.5n+0.5n2a9=1+1.5*9+0.5*81=55n位数/字母组成排列求n位二进制数相邻两位不出

10、现11的数的个数。第n位为0或1: 是0，有an-1；是1，则n-1位为0,有an-2.an -1设n-1位不出现11的个数为n-2位不出现11的个数为an - 2n位不出现11的个数为 an= an -1 + an - 2an则- an -1 - an - 2= 0,= 1, a1 = 2, a2= 3ana0- x - 1 = 0x2特征方程为= 1 += 1 -5 ,5 xx1222nn+ BxAx设12代入得 ì5 + 35ï A =105 - 3í5ïB =î10= 5 + 35 × 1 +5)n + 5 - 35 

11、5; 1 -5)na(n102102母函数和递推 例题：铺砖题方砖1*1，长砖1*2，给1*n的路铺路面，求1）方案数，2）总砖数1）设方案数为an,以最后一块砖分类= 1，a = 1，a= 2，a= 3，a= 5，a= 8，a0123451(a- ba= F=n+1n+1 )n+1n5an-2an = an-1 + an-2an-11 (a= a+n+b1a =F =-n+1aa)n-1n-2n+1nn52）总砖数。设总砖数为bn,以最后一块砖分类bn-1。an-1b=n-+1a n-1+ n-b2+n-2 b=an-1 + bn-2+bn anAn) a n(Cn b)n+特解(是,是特征

12、根，m=1+Ba n-1)b(n-n1=(+(n-1+( C- 1+ DA()+Ba n-2)b(n- 2+( Cn-n2-2)+ DA()1a(+1 b-+ )n 1+n5b 的形式是(An) a n + (Cn b)n +Ba n +Db nn(An + B) a n + (Cn + D b)nb=0，=b=b=， b =， =b。bn-2 。a45 代立方程组太复杂(An + B) a n + (Cn + D b)n。n-2- 2= 1+5 ,2= 1-5a =b =1-1+5252( An + B)a n + (Cn + D)bn= ( A(n -1) + B)a n-1 + (C(n

13、 -1) + D)bn-1+ ( A(n - 2) + B)a n-2+ (C(n - 2) + D)bn-21a n = a n-1 + a n-2 , b n= b n-1 + b n-2(a n+1- bn+1 )+515Ana n= A(n -1)a n-1 + A(n - 2)a n-2 +a n+11Ana n - Ana n-1 + Aa n-1 - Ana n-2 + 2 Aa n-2 -a n+1= 051 a n+11 a 3A = 1a 2Aa n-1+ 2 Aa n-2 =Aa + 2 A =55511C = -b2Cb+ 2Cbb= -n-1n-2n+15b = 1代

14、入得1 = 1 (a 35+ ba - b )+ B(b = 0代入得B +D =3 )0105A = 1a 2B = 1 D = - 1 C = - 1 b 255 55 55b = (1a 2 n +1+ (- 1 b 2 n -1)a n)b nn55 555 5不考内容 第一类Stirling数 Catalan数第三章原理和鸽巢原理原理 棋盘多项式 有限制的排列: 如错排 广义原理鸽巢原理不考内容 Ramsey数 反演原理 原理:A1 UA2U . U Annnåi =1- å åi =1j >i=AiAiI Ajn+åå

15、9; - .Ai I AjI Aki=1 j>i k>j+(-1)n-1AAI . I AI12n(4)= N -A1 I A2 I . I AnA1 U A2 U . UAn -1AnUnn= N - åi =1+ å åi =1j >iAiAiI Ajni=1 j>ik>j(5)+ (-1)nA1 I A2 I . I An-ååå Ai I AjI Ak+ .整数整除求从1到500的整数中被3和5整除但不被7整除的数的个数.设A3：被3整除的数的集合解A5：被5整除的数的集合A7：被7整除的数的集合

16、所以A7A5A3A3A5 A7A5A3ë500/3*5ûë 500/3*5*7 û33429 求1-10,000中不是完全平方数,且不是完全立方数的所有整数个数 解:A1为完全平方数集合1002=10000,所以|A1|=100A2为完全立方数集合213=9261223=10648, 所以|A2|=21A1A2为完全6次方数集合46=4096, 56=15625,所以|A1A2|=4 所求数为 10000-(100+21)+4 = 9883三论多重集组合6个a,6个b,3个c中取12个的组合数?可以转化为xa+xb+xc=12, 0 xa6, 0 xb6

17、 0 xc3S为无限个a,b,c中取12个的集合,共C(12+3-1,12)=91A1=至少7个a; A2=至少7个b; A3=至少4个c|A1|=|A2|=C(5+3-1,5)=21; |A3|=C(8+3-1,8)=45|A1A2|=0; |A1A3|= |A2A3|=C(1+3-1,1)=3 所求组合数=91-(21+45+21)+(0+3+3) = 10 令r k（C）表示k个棋子布到棋盘C上的方案数。n设C为一棋盘，称R(C)= r (C) xk定义kk=0为C的棋盘多项式。规定 r0(C)=1，C=时。设 ri 为 i个棋子布入禁区的方案数，i定理=1,2,3,·

18、3;·,n。有禁区的方案数（即禁区内不的方案数）为n! r1(n1)! r2(n2)!···(1)nrnA、B、C三种材料用作I、II、III的原料，但要求I禁止用B、C作原料，II不能用B作原料，III不用A作原料，问有多少种安排方案？（假定每种材料只做一种产品的原料）解 可得如下的带禁区的棋盘其中有阴影的表示禁区ABC禁区的棋子多项式为：R()=R() R()=(1+x)(1+3x+x2 )=1+4x+4x2+ x3 故方案数3!4·2!+4 ·1!1 ·0!1“若有n个鸽子巢，n+1个鸽子，则至少有一个巢内有至少有&#

19、233;(n+1)/nù=2个鸽子。”出现ak+ ak+1+ ··· + al累加,多半要构造jSj = aii =1出现奇偶性,整除,多半要取mod整点反证法 内点多次利用鸽巢证明：在平面直角坐标系中，33个整点中必有9个整点的重心仍是整点。证：先证明9个整点中必有3个整点的重心的仍是整点。ppt）（证明请参照整点33个整点中必有9个3点组，每组的重心仍是整点。 33个中有3个整点整点，剩下30个，取3个整点整点，9组剩下27个，取3个整点。整点，剩下9个，取3个整点整点，而这9个重心中必有3个的重心仍是整点，从而就证明了33 个整点中必有9个整点的重

20、心仍是整点。在边长为1的正方形内5个点试证1其中至少有两点，其间距离小于22把×正方形分成四个1×1 的证22 正方形如下图： 2则这点中必有两点落在同一个小正方形内而小正方形内的的距离都小于12第四章Burnside引理:设G=a1,a2,ag是目标集1,n上的置换群每个置换都写成不相交循环的乘积。 G将1,n划分成l个等价类.c1(ak)是在置换ak的作用下不动点的个数。l=c1(a1)+c1(a2)+c1(ag)/|G|Pólya定理 设G=P1,P2,Pg是n个对象的一个置换群，C(Pk)是置换Pk的循环的个数，用m种颜色对n个对象着色,着色方案数为C(P

21、g)l=1 mC(P1)+m C(P2)+m.|G| 母函数型Pólya定理 Sk=(b1k+b2k+bmk),k=1,2n熟悉各种凸多面体的转动群欠角和的概念 平面多的转动群注意不动图象4.6 举例足球： 正5内角108o，正六内角120o欠角=360o (108o +2·120o)=12o720 /12 =60(个顶点)60·3/2=90(条棱)60/5=12(个5)60·2/6=20(个6)10根红、10根蓝、10根绿火柴搭一个正20面体， 有多少方案？ 解：正20面体有正3角形组成，12个顶点，30条棱，20个面 置换群为： 不动：(1)301个

22、(30!/10!10!10!)*230（30根火柴的可重排列,火柴头两个方向,相当于二着色） 顶点顶点: (5)624个(6!/2!2!2!)*26（12个顶点，6个轴，4个转动角度）( 5根火柴一组,共6组，每 组中5根火柴颜色必须相同，不动图象) 面心面心(3)1020个（20个面，10个轴，2个转动）（每组3根火柴,一共10个组，3根火柴颜色必须相同， 象,颜色无法平分,故无不动图象）不动图棱中棱中 (1)2(2)14 15个（火柴有方向，无不动图象）方案数：L=(30！/10！10！10！)*230+24*(6！/2！2！2！)*26)/60第六章 线性 标准形式二阶段法n 若第一阶段

23、结束时，人工变量仍在基变量中， 则原无（可行）解大M法如果是求极大值，需加-M；如果是求极小值，需 加M。M，就不能实现极值。如基变量中还约束åx£=ppxxbb加入松弛变量jjs条件：xåå加入人工变量先减去 xs 再加上ajjxa³pxbjjcccccLLLLj+1mm1nbicPPPPXPLLLLBB+ 101mmnb1M10Ma1,m +1Ma1nMc1MMcmx1MMxmb1MMbmLLLLMMM1Mam ,m +1MMb m0amnLLLLå c i a ijl=å cibic-Z00LLjjmaxmin最优解j 0j 0换入变量j>0或者max(j)找j<0或min(j)换出变量例： minì=-Z £11³3-ïïí 2 -+= 1xx ï3 ³, =- 3mZin+4=ìx11-ï-x+=3xïí-=ï21³ ,.两阶段法： 第一阶段：将人工变量迭代出去，从而找到原，构造如下模型：的基础可行解 若W=0,说明 否则，原基本可行解，可以进行第二个阶段；无可行解，停止运算。=+minW6x7 x+4=ìx