数学公式

TheoreticalComputerScienceCheatSheetDenitionsSeriesf(n)=O(g(n))i9positivec;n0suchthat0f(n)cg(n)8nn0.nXi=1i=n(n+1)2;nXi=1i2=n(n+1)(2n+1)6;nXi=1i3=n2(n+1)24:Ingeneral:nXi=1im=1m+1(n+1)m+1−1−nXi=1(i+1)m+1−im+1−(m+1)im
n−1Xi=1im=1m+1mXk=0m+1kBknm+1−k:Geometricseries:nXi=0ci=cn+1−1c−1;c6=1;1Xi=0ci=11−c;1Xi=1ci=c1−c;jcj1;nXi=0ici=ncn+2−(n+1)cn+1+c(c−1)2;c6=1;1Xi=0ici=c(1−c)2;jcj1:Harmonicseries:Hn=nXi=11i;nXi=1iHi=n(n+1)2Hn−n(n−1)4:nXi=1Hi=(n+1)Hn−n;nXi=1imHi=n+1m+1Hn+1−1m+1:f(n)=Ω(g(n))i9positivec;n0suchthatf(n)cg(n)08nn0.f(n)=(g(n))if(n)=O(g(n))andf(n)=Ω(g(n)).f(n)=o(g(n))ilimn!1f(n)=g(n)=0.limn!1an=ai80,9n0suchthatjan−aj,8nn0.supSleastb2Rsuchthatbs,8s2S.infSgreatestb2Rsuchthatbs,8s2S.liminfn!1anlimn!1inffaijin;i2Ng.limsupn!1anlimn!1supfaijin;i2Ng.nk
Combinations:Sizeksub-setsofasizenset.nkStirlingnumbers(1stkind):Arrangementsofannele-mentsetintokcycles.1.nk=n!(n−k)!k!;2.nXk=0nk=2n;3.nk=nn−k;4.nk=nkn−1k−1;5.nk=n−1k+n−1k−1;6.nmmk=nkn−km−k;7.nXk=0r+kk=r+n+1n;8.nXk=0km=n+1m+1;9.nXk=0rksn−k=r+sn;10.nk=(−1)kk−n−1k;11.n1=nn=1;12.n2=2n−1−1;13.nk=kn−1k+n−1k−1;nk Stirlingnumbers(2ndkind):Partitionsofannelementsetintoknon-emptysets.nk1storderEuleriannumbers:Permutations12:::nonf1;2;:::;ngwithkascents.nk2ndorderEuleriannumbers.CnCatalanNumbers:Binarytreeswithn+1vertices.14.n1=(n−1)!;15.n2=(n−1)!Hn−1;16.nn=1;17.nknk;18.nk=(n−1)n−1k+n−1k−1;19.nn−1=nn−1=n2;20.nXk=0nk=n!;21.Cn=1n+12nn;22.n0=nn−1=1;23.nk=nn−1−k;24.nk=(k+1)n−1k+(n−k)n−1k−1;25.0k=n1ifk=0,0otherwise26.n1=2n−n−1;27.n2=3n−(n+1)2n+n+12;28.xn=nXk=0nkx+kn;29.nm=mXk=0n+1k(m+1−k)n(−1)k;30.m!nm=nXk=0nkkn−m;31.nm=nXk=0nkn−km(−1)n−k−mk!;32.n0=1;33.nn=0forn6=0;34.nk=(k+1)n−1k+(2n−1−k)n−1k−1;35.nXk=0nk=(2n)n2n;36.xx−n=nXk=0nkx+n−1−k2n;37.n+1m+1=Xknkkm=nXk=0km(m+1)n−k;TheoreticalComputerScienceCheatSheetIdentitiesCont.Trees38.n+1m+1=Xknkkm=nXk=0kmnn−k=n!nXk=01k!km;39.xx−n=nXk=0nkx+k2n;40.nm=Xknkk+1m+1(−1)n−k;41.nm=Xkn+1k+1km(−1)m−k;42.m+n+1m=mXk=0kn+kk;43.m+n+1m=mXk=0k(n+k)n+kk;44.nm=Xkn+1k+1km(−1)m−k;45.(n−m)!nm=Xkn+1k+1km(−1)m−k;fornm,46.nn−m=Xkm−nm+km+nn+km+kk;47.nn−m=Xkm−nm+km+nn+km+kk;48.n`+m`+m`=Xkk`n−kmnk;49.n`+m`+m`=Xkk`n−kmnk:Everytreewithnverticeshasn−1edges.Kraftinequal-ity:Ifthedepthsoftheleavesofabinarytreeared1;:::;dn:nXi=12−di1;andequalityholdsonlyifeveryin-ternalnodehas2sons.RecurrencesMastermethod:T(n)=aT(n=b)+f(n);a1;b1If90suchthatf(n)=O(nlogba−)thenT(n)=(nlogba):Iff(n)=(nlogba)thenT(n)=(nlogbalog2n):If90suchthatf(n)=Ω(nlogba+),and9c1suchthataf(n=b)cf(n)forlargen,thenT(n)=(f(n)):Substitution(example):ConsiderthefollowingrecurrenceTi+1=22i
T2i;T1=2:NotethatTiisalwaysapoweroftwo.Letti=log2Ti.Thenwehaveti+1=2i+2ti;t1=1:Letui=ti=2i.Dividingbothsidesofthepreviousequationby2i+1wegetti+12i+1=2i2i+1+ti2i:Substitutingwendui+1=12+ui;u1=12;whichissimplyui=i=2.SowendthatTihastheclosedformTi=2i2i−1.Summingfactors(example):ConsiderthefollowingrecurrenceT(n)=3T(n=2)+n;T(1)=1:RewritesothatalltermsinvolvingTareontheleftsideT(n)−3T(n=2)=n:Nowexpandtherecurrence,andchooseafactorwhichmakestheleftside\tele-scope1T(n)−3T(n=2)=n
3T(n=2)−3T(n=4)=n=2
.........3log2n−1T(2)−3T(1)=2
Letm=log2n.SummingtheleftsidewegetT(n)−3mT(1)=T(n)−3m=T(n)−nkwherek=log231:58496.Summingtherightsidewegetm−1Xi=0n2i3i=nm−1Xi=032
i:Letc=32.Thenwehavenm−1Xi=0ci=ncm−1c−1=2n(clog2n−1)=2n(c(k−1)logcn−1)=2nk−2n;andsoT(n)=3nk−2n.Fullhistoryre-currencescanoftenbechangedtolimitedhistoryones(example):ConsiderTi=1+i−1Xj=0Tj;T0=1:NotethatTi+1=1+iXj=0Tj:SubtractingwendTi+1−Ti=1+iXj=0Tj−1−i−1Xj=0Tj=Ti:AndsoTi+1=2Ti=2i+1.Generatingfunctions:1.Multiplybothsidesoftheequa-tionbyxi.2.Sumbothsidesoveralliforwhichtheequationisvalid.3.ChooseageneratingfunctionG(x).UsuallyG(x)=P1i=0xigi.3.RewritetheequationintermsofthegeneratingfunctionG(x).4.SolveforG(x).5.ThecoecientofxiinG(x)isgi.Example:gi+1=2gi+1;g0=0:Multiplyandsum:Xi0gi+1xi=Xi02gixi+Xi0xi:WechooseG(x)=Pi0xigi.RewriteintermsofG(x):G(x)−g0x=2G(x)+Xi0xi:Simplify:G(x)x=2G(x)+11−x:SolveforG(x):G(x)=x(1−x)(1−2x):Expandthisusingpartialfractions:G(x)=x21−2x−11−x=x0@2Xi02ixi−Xi0xi1A=Xi0(2i+1−1)xi+1:Sogi=2i−1.TheoreticalComputerScienceCheatSheet3:14159,e2:71828,γ0:57721,=1+p521:61803,^=1−p52−:61803i2ipiGeneralProbability122BernoulliNumbers(Bi=0,oddi6=1):B0=1,B1=−12,B2=16,B4=−130,B6=142,B8=−130,B10=566.Changeofbase,quadraticformula:logbx=logaxlogab;−bpb2−4ac2a:Euler'snumbere:e=1+12+16+124+1120+


limn!11+xnn=ex:1+1n
ne1+1n
n+1:1+1n
n=e−e2n+11e24n2−O1n3:Harmonicnumbers:1,32,116,2512,13760,4920,363140,761280,71292520;:::lnnHnlnn+1;Hn=lnn+γ+O1n:Factorial,Stirling'sapproximation:1,2,6,24,120,720,5040,40320,362880,:::n!=p2nnen1+1n:Ackermann'sfunctionandinverse:a(i;j)=8:2ji=1a(i−1;2)j=1a(i−1;a(i;j−1))i;j2(i)=minfjja(j;j)ig:Cont