內(nèi)容課件案例復(fù)習(xí)

1、安排 時(shí)間：1月13日晚6點(diǎn)半-9點(diǎn)地點(diǎn)：建館報(bào)告廳 答疑時(shí)間：1月10日下午2pm-5pm，東主樓8-4021月13日下午2pm-4:30pm，東主樓8-402題型 5道解答或者證明題,一題中可能有多問五章內(nèi)容不排列生成: myc 考卷上請(qǐng)寫明學(xué)號(hào)，姓名，號(hào)碼，1第一章 排列與組合計(jì)數(shù)基本原理 加法法則:若 |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個(gè)不同的元素中，取r個(gè)不重復(fù)的元素，按次序排列，稱為從n個(gè)中取r個(gè)的無重排列。排列的全體組成的集合用P(n,r)表示。排列的個(gè)數(shù)用P(n,r)表示。當(dāng)r=n時(shí)稱為全排列。P(n,r)=n(n-1)(n-r+1)組合從n個(gè)不同元素中取r個(gè)不重復(fù)的元素組成一個(gè)子集，而不考慮其元素的順序，稱為從n個(gè)中取r個(gè)的無重組合。組合的全體組成的集合用C(n,r)表示，組合的個(gè)數(shù) 用C(n,r)表示， C(n,r)=P(n,r)/r!=n!/(r!(n-r)!) 重復(fù)的排列(多重集排列): 求r1個(gè)1，r2個(gè)2，

3、rt個(gè)t的排列數(shù)，設(shè)r1+r2+rt=n,設(shè)此排列數(shù)為P(n;r1,r2,rt),對(duì)1，2，t分別加下標(biāo)，得到 P(n；r1,r2,rt)·r1!·r2!··rt! = n!nn! P(n；r1,r2,rt)= =( r)r2 rt r1!r2!rt!1 圓周排列 從n個(gè)中取r個(gè)的圓排列的排列數(shù)為 P(n,r)/r ,項(xiàng)鏈排列2rnP(n,r)/2r ,3rn 在圓排列的基礎(chǔ)上，正面向上和向上兩種方式放置各 個(gè)數(shù)是同一個(gè)排列。重復(fù)的組合(多重集的組合) n個(gè)不同的元素中取r個(gè)做重復(fù)的組合,其組合數(shù)為C(n+r-1,r) 線性方程非負(fù)整數(shù)解x1+x2+xn

4、=b的非負(fù)整數(shù)解的個(gè)數(shù)C(n+b-1,b)不相鄰的組合 n個(gè)數(shù)中取r個(gè)作不相鄰的組合,組合數(shù)為C(n-r+1,r)多重集的組合給三個(gè)孩子發(fā)水果,一共12個(gè)一樣的,每個(gè)孩子至少有一個(gè)水果,問有多少種分法?解:設(shè)分給第i個(gè)孩子的水果數(shù)為xi, xi1x1+x2+x3=12令y1=x1-1,y2=x2-1,y3=x3-1 y1+y2+y3=9 yi0 非負(fù)整數(shù)解的個(gè)數(shù)為C(9+3-1,9)=55不考的內(nèi)容 排列，組合的生成 Stirling公式第二章 遞推與母函數(shù) 二項(xiàng)式定理 (x+y)n=C(n,k)xn-kykk=0-n (1+x)n= C(n,k)xn-kk=0-n多項(xiàng)式定理 (x1+x2+x

5、t)n=C(n;r1,r2,.rt)x1r1x2r2xtrtr1+r2+rt=n因式分解一元二次方程求解 多項(xiàng)式長除法求解組合母函數(shù)對(duì)于序列a0 , a1 , a2 ,L, 構(gòu)造一函數(shù)：G(x) = a + a x + a+L,x2012稱函數(shù)G(x)是序列a0 , a1, a2 ,L的母函數(shù) 指數(shù)求解排列函數(shù)a0 , a1 , a2 ,L對(duì)于序列，函數(shù)+ a1x + a2+ a3G (x) = ax2x3e01!2!3!+L+ ak+Lxk k!a0 , a1 , a2 ,L稱為是序列的指數(shù)函數(shù)常用母函數(shù)數(shù)列 1n 0 母函數(shù)1/(1- x)= 1+x+x2+函數(shù)ex指數(shù)數(shù)列 母函數(shù)1/(1

6、- cx)= 1+cx+c2x2+0函數(shù)ecx指數(shù)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數(shù)列 鋪磚 N位序列中符合某些性質(zhì)的排列數(shù) 放球 .線性常系數(shù)遞推定義 如果序列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階常系數(shù)線性遞推(2 - 5 - 2)稱為an 的初始條件， + C xk -1C(x) = xk+L+ Cx + Ck -11k稱為an 的特征多項(xiàng)式線性常系數(shù)遞推 確定特征多項(xiàng)式 特征方程根的情況非重根共軛復(fù)根多重根 利用系數(shù)an的前若干項(xiàng)求解待定系數(shù) 確定an總結(jié)線性常系數(shù)遞推根據(jù)特征多項(xiàng)式C(x)的非零解的情況( ) =x(-a1 )(a- x2 )L( a-)1)有k個(gè)不同非零實(shí)數(shù)解Cxxk= ln+L+nlana其中l(wèi) ,1aln1122kkl ,2Lk,是l待

8、定,系數(shù)2)有一對(duì)共軛復(fù)根a= reiq 和a= re-iq 時(shí)，12= A rcosq +nrsinqannBnn 其中A，B是待定。3)有k重根。不妨設(shè)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個(gè)待定。 01k -1母函數(shù)法求多重集的組合 給三個(gè)孩子發(fā)水果,一共12個(gè)一樣的,每個(gè)孩子至少有一個(gè)水果,問有多少種分法? 解:母函數(shù)為,G(x)=(x+x2+x3+x4+)(x+x2+x3+x4+)(x+x2+x3+x4+)=(x/(1-x)3求x12的系數(shù),即1/(1-x)3中的x9的系數(shù).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位數(shù)/字母組成排列求n位二進(jìn)制數(shù)相鄰兩位不出

10、現(xiàn)11的數(shù)的個(gè)數(shù)。第n位為0或1: 是0，有an-1；是1，則n-1位為0,有an-2.an -1設(shè)n-1位不出現(xiàn)11的個(gè)數(shù)為n-2位不出現(xiàn)11的個(gè)數(shù)為an - 2n位不出現(xiàn)11的個(gè)數(shù)為 an= an -1 + an - 2an則- an -1 - an - 2= 0,= 1, a1 = 2, a2= 3ana0- x - 1 = 0x2特征方程為= 1 += 1 -5 ,5 xx1222nn+ BxAx設(shè)12代入得 ì5 + 35ï A =105 - 3í5ïB =î10= 5 + 35 × 1 +5)n + 5 - 35 

11、5; 1 -5)na(n102102母函數(shù)和遞推 例題：鋪磚題方磚1*1，長磚1*2，給1*n的路鋪路面，求1）方案數(shù)，2）總磚數(shù)1）設(shè)方案數(shù)為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）總磚數(shù)。設(shè)總磚數(shù)為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 代立方程組太復(fù)雜(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不考內(nèi)容 第一類Stirling數(shù) Catalan數(shù)第三章原理和鴿巢原理原理 棋盤多項(xiàng)式 有限制的排列: 如錯(cuò)排 廣義原理鴿巢原理不考內(nèi)容 Ramsey數(shù) 反演原理 原理: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+ .整數(shù)整除求從1到500的整數(shù)中被3和5整除但不被7整除的數(shù)的個(gè)數(shù).設(shè)A3：被3整除的數(shù)的集合解A5：被5整除的數(shù)的集合A7：被7整除的數(shù)的集合

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

17、 0 xc3S為無限個(gè)a,b,c中取12個(gè)的集合,共C(12+3-1,12)=91A1=至少7個(gè)a; A2=至少7個(gè)b; A3=至少4個(gè)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 所求組合數(shù)=91-(21+45+21)+(0+3+3) = 10 令r k（C）表示k個(gè)棋子布到棋盤C上的方案數(shù)。n設(shè)C為一棋盤，稱R(C)= r (C) xk定義kk=0為C的棋盤多項(xiàng)式。規(guī)定 r0(C)=1，C=時(shí)。設(shè) ri 為 i個(gè)棋子布入禁區(qū)的方案數(shù)，i定理=1,2,3,·

18、3;·,n。有禁區(qū)的方案數(shù)（即禁區(qū)內(nèi)不的方案數(shù)）為n! r1(n1)! r2(n2)!···(1)nrnA、B、C三種材料用作I、II、III的原料，但要求I禁止用B、C作原料，II不能用B作原料，III不用A作原料，問有多少種安排方案？（假定每種材料只做一種產(chǎn)品的原料）解 可得如下的帶禁區(qū)的棋盤其中有陰影的表示禁區(qū)ABC禁區(qū)的棋子多項(xiàng)式為：R()=R() R()=(1+x)(1+3x+x2 )=1+4x+4x2+ x3 故方案數(shù)3!4·2!+4 ·1!1 ·0!1“若有n個(gè)鴿子巢，n+1個(gè)鴿子，則至少有一個(gè)巢內(nèi)有至少有&#

19、233;(n+1)/nù=2個(gè)鴿子?！背霈F(xiàn)ak+ ak+1+ ··· + al累加,多半要構(gòu)造jSj = aii =1出現(xiàn)奇偶性,整除,多半要取mod整點(diǎn)反證法 內(nèi)點(diǎn)多次利用鴿巢證明：在平面直角坐標(biāo)系中，33個(gè)整點(diǎn)中必有9個(gè)整點(diǎn)的重心仍是整點(diǎn)。證：先證明9個(gè)整點(diǎn)中必有3個(gè)整點(diǎn)的重心的仍是整點(diǎn)。ppt）（證明請(qǐng)參照整點(diǎn)33個(gè)整點(diǎn)中必有9個(gè)3點(diǎn)組，每組的重心仍是整點(diǎn)。 33個(gè)中有3個(gè)整點(diǎn)整點(diǎn)，剩下30個(gè)，取3個(gè)整點(diǎn)整點(diǎn)，9組剩下27個(gè)，取3個(gè)整點(diǎn)。整點(diǎn)，剩下9個(gè)，取3個(gè)整點(diǎn)整點(diǎn)，而這9個(gè)重心中必有3個(gè)的重心仍是整點(diǎn)，從而就證明了33 個(gè)整點(diǎn)中必有9個(gè)整點(diǎn)的重

20、心仍是整點(diǎn)。在邊長為1的正方形內(nèi)5個(gè)點(diǎn)試證1其中至少有兩點(diǎn)，其間距離小于22把×正方形分成四個(gè)1×1 的證22 正方形如下圖： 2則這點(diǎn)中必有兩點(diǎn)落在同一個(gè)小正方形內(nèi)而小正方形內(nèi)的的距離都小于12第四章Burnside引理:設(shè)G=a1,a2,ag是目標(biāo)集1,n上的置換群每個(gè)置換都寫成不相交循環(huán)的乘積。 G將1,n劃分成l個(gè)等價(jià)類.c1(ak)是在置換ak的作用下不動(dòng)點(diǎn)的個(gè)數(shù)。l=c1(a1)+c1(a2)+c1(ag)/|G|Pólya定理 設(shè)G=P1,P2,Pg是n個(gè)對(duì)象的一個(gè)置換群，C(Pk)是置換Pk的循環(huán)的個(gè)數(shù)，用m種顏色對(duì)n個(gè)對(duì)象著色,著色方案數(shù)為C(P

21、g)l=1 mC(P1)+m C(P2)+m.|G| 母函數(shù)型Pólya定理 Sk=(b1k+b2k+bmk),k=1,2n熟悉各種凸多面體的轉(zhuǎn)動(dòng)群欠角和的概念 平面多的轉(zhuǎn)動(dòng)群注意不動(dòng)圖象4.6 舉例足球： 正5內(nèi)角108o，正六內(nèi)角120o欠角=360o (108o +2·120o)=12o720 /12 =60(個(gè)頂點(diǎn))60·3/2=90(條棱)60/5=12(個(gè)5)60·2/6=20(個(gè)6)10根紅、10根藍(lán)、10根綠火柴搭一個(gè)正20面體， 有多少方案？ 解：正20面體有正3角形組成，12個(gè)頂點(diǎn)，30條棱，20個(gè)面 置換群為： 不動(dòng)：(1)301個(gè)

22、(30!/10!10!10!)*230（30根火柴的可重排列,火柴頭兩個(gè)方向,相當(dāng)于二著色） 頂點(diǎn)頂點(diǎn): (5)624個(gè)(6!/2!2!2!)*26（12個(gè)頂點(diǎn)，6個(gè)軸，4個(gè)轉(zhuǎn)動(dòng)角度）( 5根火柴一組,共6組，每 組中5根火柴顏色必須相同，不動(dòng)圖象) 面心面心(3)1020個(gè)（20個(gè)面，10個(gè)軸，2個(gè)轉(zhuǎn)動(dòng)）（每組3根火柴,一共10個(gè)組，3根火柴顏色必須相同， 象,顏色無法平分,故無不動(dòng)圖象）不動(dòng)圖棱中棱中 (1)2(2)14 15個(gè)（火柴有方向，無不動(dòng)圖象）方案數(shù)：L=(30！/10！10！10！)*230+24*(6！/2！2！2！)*26)/60第六章 線性 標(biāo)準(zhǔn)形式二階段法n 若第一階段

23、結(jié)束時(shí)，人工變量仍在基變量中， 則原無（可行）解大M法如果是求極大值，需加-M；如果是求極小值，需 加M。M，就不能實(shí)現(xiàn)極值。如基變量中還約束åx£=ppxxbb加入松弛變量jjs條件：xåå加入人工變量先減去 xs 再加上ajjxa³pxbjjcccccLLLLj+1mm1nbicPPPPXPLLLLBB+ 101mmnb1M10Ma1,m +1Ma1nMc1MMcmx1MMxmb1MMbmLLLLMMM1Mam ,m +1MMb m0amnLLLLå c i a ijl=å cibic-Z00LLjjmaxmin最優(yōu)解j 0j 0換入變量j>0或者max(j)找j<0或min(j)換出變量例： minì=-Z £11³3-ïïí 2 -+= 1xx ï3 ³, =- 3mZin+4=ìx11-ï-x+=3xïí-=ï21³ ,.兩階段法： 第一階段：將人工變量迭代出去，從而找到原，構(gòu)造如下模型：的基礎(chǔ)可行解 若W=0,說明 否則，原基本可行解，可以進(jìn)行第二個(gè)階段；無可行解，停止運(yùn)算。=+minW6x7 x+4=ìx