从小学到博士俱全数学公式手册打印版

Theoretical Computer Science Cheat Sheet De�nitions Series f(n) = O(g(n)) i� 9 positive c; n0 such that 0 � f(n) � cg(n) 8n � n0. nX i=1 i = n(n + 1) 2 ; nX i=1 i2 = n(n + 1)(2n + 1) 6 ; nX i=1 i3 = n2(n + 1)2 4 : In general: nX i=1 im = 1 m + 1 � (n + 1)m+1 − 1− nX i=1 ( (i + 1)m+1 − im+1 − (m + 1)im�� n−1X i=1 im = 1 m + 1 mX k=0 � m + 1 k � Bkn m+1−k: Geometric series: nX i=0 ci = cn+1 − 1 c− 1 ; c 6= 1; 1X i=0 ci = 1 1− c ; 1X i=1 ci = c 1− c ; jcj < 1; nX i=0 ici = ncn+2 − (n + 1)cn+1 + c (c− 1)2 ; c 6= 1; 1X i=0 ici = c (1− c)2 ; jcj < 1: Harmonic series: Hn = nX i=1 1 i ; nX i=1 iHi = n(n + 1) 2 Hn − n(n− 1)4 : nX i=1 Hi = (n + 1)Hn − n; nX i=1 � i m � Hi = � n + 1 m + 1 �� Hn+1 − 1 m + 1 � : f(n) = Ω(g(n)) i� 9 positive c; n0 such that f(n) � cg(n) � 0 8n � n0. f(n) = �(g(n)) i� f(n) = O(g(n)) and f(n) = Ω(g(n)). f(n) = o(g(n)) i� limn!1 f(n)=g(n) = 0. lim n!1 an = a i� 8� > 0, 9n0 such thatjan − aj < �, 8n � n0. supS least b 2 R such that b � s, 8s 2 S. inf S greatest b 2 R such that b � s, 8s 2 S. lim inf n!1 an limn!1 inffai j i � n; i 2 Ng. lim sup n!1 an lim n!1 supfai j i � n; i 2 Ng.( n k � Combinations: Size k sub- sets of a size n set.� n k � Stirling numbers (1st kind): Arrangements of an n ele- ment set into k cycles. 1. � n k � = n! (n− k)!k! ; 2. nX k=0 � n k � = 2n; 3. � n k � = � n n− k � ; 4. � n k � = n k � n− 1 k − 1 � ; 5. � n k � = � n− 1 k � + � n− 1 k − 1 � ; 6. � n m �� m k � = � n k �� n− k m− k � ; 7. nX k=0 � r + k k � = � r + n + 1 n � ; 8. nX k=0 � k m � = � n + 1 m + 1 � ; 9. nX k=0 � r k �� s n− k � = � r + s n � ; 10. � n k � = (−1)k � k − n− 1 k � ; 11. � n 1 � = � n n � = 1; 12. � n 2 � = 2n−1 − 1; 13. � n k � = k � n− 1 k � + � n− 1 k − 1 � ; � n k } Stirling numbers (2nd kind): Partitions of an n element set into k non-empty sets.〈 n k � 1st order Eulerian numbers: Permutations �1�2 : : : �n on f1; 2; : : : ; ng with k ascents.〈〈 n k �� 2nd order Eulerian numbers. Cn Catalan Numbers: Binary trees with n + 1 vertices. 14. � n 1 � = (n− 1)!; 15. � n 2 � = (n− 1)!Hn−1; 16. � n n � = 1; 17. � n k � � � n k � ; 18. � n k � = (n− 1) � n− 1 k � + � n− 1 k − 1 � ; 19. � n n− 1 � = � n n− 1 � = � n 2 � ; 20. nX k=0 � n k � = n!; 21. Cn = 1 n + 1 � 2n n � ; 22. � n 0 � = � n n− 1 � = 1; 23. � n k � = � n n− 1− k � ; 24. � n k � = (k + 1) � n− 1 k � + (n− k) � n− 1 k − 1 � ; 25. � 0 k � = n 1 if k = 0, 0 otherwise 26. � n 1 � = 2n − n− 1; 27. � n 2 � = 3n − (n + 1)2n + � n + 1 2 � ; 28. xn = nX k=0 � n k �� x + k n � ; 29. � n m � = mX k=0 � n + 1 k � (m + 1− k)n(−1)k; 30. m! � n m � = nX k=0 � n k �� k n−m � ; 31. � n m � = nX k=0 � n k �� n− k m � (−1)n−k−mk!; 32. �� n 0 �� = 1; 33. �� n n �� = 0 for n 6= 0; 34. �� n k �� = (k + 1) �� n− 1 k �� + (2n− 1− k) �� n− 1 k − 1 �� ; 35. nX k=0 �� n k �� = (2n)n 2n ; 36. � x x− n � = nX k=0 �� n k ��� x + n− 1− k 2n � ; 37. � n + 1 m + 1 � = X k � n k �� k m � = nX k=0 � k m � (m + 1)n−k; Theoretical Computer Science Cheat Sheet Identities Cont. Trees 38. � n + 1 m + 1 � = X k � n k �� k m � = nX k=0 � k m � nn−k = n! nX k=0 1 k! � k m � ; 39. � x x− n � = nX k=0 �� n k ��� x + k 2n � ; 40. � n m � = X k � n k �� k + 1 m + 1 � (−1)n−k; 41. � n m � = X k � n + 1 k + 1 �� k m � (−1)m−k; 42. � m + n + 1 m � = mX k=0 k � n + k k � ; 43. � m + n + 1 m � = mX k=0 k(n + k) � n + k k � ; 44. � n m � = X k � n + 1 k + 1 �� k m � (−1)m−k; 45. (n−m)! � n m � = X k � n + 1 k + 1 �� k m � (−1)m−k; for n � m, 46. � n n−m � = X k � m− n m + k �� m + n n + k �� m + k k � ; 47. � n n−m � = X k � m− n m + k �� m + n n + k �� m + k k � ; 48. � n ‘ + m �� ‘ + m ‘ � = X k � k ‘ �� n− k m �� n k � ; 49. � n ‘ + m �� ‘ + m ‘ � = X k � k ‘ �� n− k m �� n k � : Every tree with n vertices has n − 1 edges. Kraft inequal- ity: If the depths of the leaves of a binary tree are d1; : : : ; dn: nX i=1 2−di � 1; and equality holds only if every in- ternal node has 2 sons. Recurrences Master method: T (n) = aT (n=b) + f(n); a � 1; b > 1 If 9� > 0 such that f(n) = O(nlogb a−�) then T (n) = �(nlogb a): If f(n) = �(nlogb a) then T (n) = �(nlogb a log2 n): If 9� > 0 such that f(n) = Ω(nlogb a+�), and 9c < 1 such that af(n=b) � cf(n) for large n, then T (n) = �(f(n)): Substitution (example): Consider the following recurrence Ti+1 = 22 i � T 2i ; T1 = 2: Note that Ti is always a power of two. Let ti = log2 Ti. Then we have ti+1 = 2i + 2ti; t1 = 1: Let ui = ti=2i. Dividing both sides of the previous equation by 2i+1 we get ti+1 2i+1 = 2i 2i+1 + ti 2i : Substituting we �nd ui+1 = 12 + ui; u1 = 1 2 ; which is simply ui = i=2. So we �nd that Ti has the closed form Ti = 2i2 i−1 . Summing factors (example): Consider the following recurrence T (n) = 3T (n=2) + n; T (1) = 1: Rewrite so that all terms involving T are on the left side T (n)− 3T (n=2) = n: Now expand the recurrence, and choose a factor which makes the left side \tele- scope" 1 ( T (n)− 3T (n=2) = n� 3 ( T (n=2)− 3T (n=4) = n=2� ... ... ... 3log2 n−1 ( T (2)− 3T (1) = 2� Let m = log2 n. Summing the left side we get T (n) − 3mT (1) = T (n) − 3m = T (n) − nk where k = log2 3 � 1:58496. Summing the right side we get m−1X i=0 n 2i 3i = n m−1X i=0 ( 3 2 �i : Let c = 32 . Then we have n m−1X i=0 ci = n � cm − 1 c− 1 � = 2n(clog2 n − 1) = 2n(c(k−1) logc n − 1) = 2nk − 2n; and so T (n) = 3nk − 2n. Full history re- currences can often be changed to limited history ones (example): Consider Ti = 1 + i−1X j=0 Tj ; T0 = 1: Note that Ti+1 = 1 + iX j=0 Tj : Subtracting we �nd Ti+1 − Ti = 1 + iX j=0 Tj − 1− i−1X j=0 Tj = Ti: And so Ti+1 = 2Ti = 2i+1. Generating functions: 1. Multiply both sides of the equa- tion by xi. 2. Sum both sides over all i for which the equation is valid. 3. Choose a generating function G(x). Usually G(x) = P1 i=0 x igi. 3. Rewrite the equation in terms of the generating function G(x). 4. Solve for G(x). 5. The coe�cient of xi in G(x) is gi. Example: gi+1 = 2gi + 1; g0 = 0: Multiply and sum:X i�0 gi+1x i = X i�0 2gixi + X i�0 xi: We choose G(x) = P i�0 x igi. Rewrite in terms of G(x): G(x)− g0 x = 2G(x) + X i�0 xi: Simplify: G(x) x = 2G(x) + 1 1− x: Solve for G(x): G(x) = x (1− x)(1− 2x) : Expand this using partial fractions: G(x) = x � 2 1− 2x − 1 1− x � = x 0 @2X i�0 2ixi − X i�0 xi 1 A = X i�0 (2i+1 − 1)xi+1: So gi = 2i − 1. Theoretical Computer Science Cheat Sheet � � 3:14159, e � 2:71828, γ � 0:57721, � = 1+ p 5 2 � 1:61803, �^ = 1− p 5 2 � −:61803 i 2i pi General Probability 1 2 2 Bernoulli Numbers (Bi = 0, odd i 6= 1): B0 = 1, B1 = − 12 , B2 = 16 , B4 = − 130 , B6 = 142 , B8 = − 130 , B10 = 566 . Change of base, quadratic formula: logb x = loga x loga b ; −b�pb2 − 4ac 2a : Euler’s number e: e = 1 + 12 + 1 6 + 1 24 + 1 120 + � � � lim n!1 � 1 + x n �n = ex:( 1 + 1n �n < e < ( 1 + 1n �n+1 :( 1 + 1n �n = e− e 2n + 11e 24n2 −O � 1 n3 � : Harmonic numbers: 1, 32 , 11 6 , 25 12 , 137 60 , 49 20 , 363 140 , 761 280 , 7129 2520 ; : : : lnn < Hn < lnn + 1; Hn = ln n + γ + O � 1 n � : Factorial, Stirling’s approximation: 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, : : : n! = p 2�n � n e �n� 1 + � � 1 n �� : Ackermann’s function and inverse: a(i; j) = 8< : 2j i = 1 a(i− 1; 2) j = 1 a(i− 1; a(i; j − 1)) i; j � 2 �(i) = minfj j a(j; j) � ig: Continuous distributions: If Pr[a < X < b] = Z b a p(x) dx; then p is the probability density function of X. If Pr[X < a] = P (a); then P is the distribution function of X. If P and p both exist then P (a) = Z a −1 p(x) dx: Expectation: If X is discrete E[g(X)] = X x g(x) Pr[X = x]: If X continuous then E[g(X)] = Z 1 −1 g(x)p(x) dx = Z 1 −1 g(x) dP (x): Variance, standard deviation: VAR[X] = E[X2]− E[X]2; � = p VAR[X]: For events A and B: Pr[A _B] = Pr[A] + Pr[B]− Pr[A ^B] Pr[A ^B] = Pr[A] � Pr[B]; i� A and B are independent. Pr[AjB] = Pr[A ^B] Pr[B] For random variables X and Y : E[X � Y ] = E[X] � E[Y ]; if X and Y are independent. E[X + Y ] = E[X] + E[Y ]; E[cX] = cE[X]: Bayes’ theorem: Pr[AijB] = Pr[BjAi] Pr[Ai]Pn j=1 Pr[Aj ] Pr[BjAj ] : Inclusion-exclusion: Pr h n_ i=1 Xi i = nX i=1 Pr[Xi] + nX k=2 (−1)k+1 X ii<��� b are in- tegers then gcd(a; b) = gcd(a mod b; b): If Qn i=1 p ei i is the prime factorization of x then S(x) = X djx d = nY i=1 pei+1i − 1 pi − 1 : Perfect Numbers: x is an even perfect num- ber i� x = 2n−1(2n−1) and 2n−1 is prime. Wilson’s theorem: n is a prime i� (n− 1)! � −1 mod n: Mo¨bius inversion: �(i) = 8>< >: 1 if i = 1. 0 if i is not square-free. (−1)r if i is the product of r distinct primes. If G(a) = X dja F (d); then F (a) = X dja �(d)G �a d � : Prime numbers: pn = n ln n + n ln lnn− n + n ln lnnlnn + O � n lnn � ; �(n) = n lnn + n (lnn)2 + 2!n (ln n)3 + O � n (lnn)4 � : De�nitions: Loop An edge connecting a ver- tex to itself. Directed Each edge has a direction. Simple Graph with no loops or multi-edges. Walk A sequence v0e1v1 : : : e`v`. Trail A walk with distinct edges. Path A trail with distinct vertices. Connected A graph where there exists a path between any two vertices. Component A maximal connected subgraph. Tree A connected acyclic graph. Free tree A tree with no root. DAG Directed acyclic graph. Eulerian Graph with a trail visiting each edge exactly once. Hamiltonian Graph with a cycle visiting each vertex exactly once. Cut A set of edges whose re- moval increases the num- ber of components. Cut-set A minimal cut. Cut edge A size 1 cut. k-Connected A graph connected with the removal of any k − 1 vertices. k-Tough 8S � V; S 6= ; we have k � c(G− S) � jSj. k-Regular A graph where all vertices have degree k. k-Factor A k-regular spanning subgraph. Matching A set of edges, no two of which are adjacent. Clique A set of vertices, all of which are adjacent. Ind. set A set of vertices, none of which are adjacent. Vertex cover A set of vertices which cover all edges. Planar graph A graph which can be em- beded in the plane. Plane graph An embedding of a planar graph.X v2V deg(v) = 2m: If G is planar then n−m + f = 2, so f � 2n− 4; m � 3n− 6: Any planar graph has a vertex with de- gree � 5. Notation: E(G) Edge set V (G) Vertex set c(G) Number of components G[S] Induced subgraph deg(v) Degree of v �(G) Maximum degree �(G) Minimum degree �(G) Chromatic number �E(G) Edge chromatic number Gc Complement graph Kn Complete graph Kn1;n2 Complete bipartite graph r(k; ‘) Ramsey number Geometry Projective coordinates: triples (x; y; z), not all x, y and z zero. (x; y; z) = (cx; cy; cz) 8c 6= 0: Cartesian Projective (x; y) (x; y; 1) y = mx + b (m;−1; b) x = c (1; 0;−c) Distance formula, Lp and L1 metric:p (x1 − x0)2 + (y1 − y0)2;�jx1 − x0jp + jy1 − y0jp�1=p; lim p!1 �jx1 − x0jp + jy1 − y0jp�1=p: Area of triangle (x0; y0), (x1; y1) and (x2; y2): 1 2 abs ���� x1 − x0 y1 − y0x2 − x0 y2 − y0 ���� : Angle formed by three points: � (0; 0) (x1; y1) (x2; y2) ‘2 ‘1 cos � = (x1; y1) � (x2; y2) ‘1‘2 : Line through two points (x0; y0) and (x1; y1):������ x y 1 x0 y0 1 x1 y1 1 ������ = 0: Area of circle, volume of sphere: A = �r2; V = 43�r 3: If I have seen farther than others, it is because I have stood on the shoulders of giants. { Issac Newton Theoretical Computer Science Cheat Sheet � Calculus Wallis’ identity: � = 2 � 2 � 2 � 4 � 4 � 6 � 6 � � � 1 � 3 � 3 � 5 � 5 � 7 � � � Brouncker’s continued fraction expansion: � 4 = 1 + 12 2 + 32 2+ 5 2 2+ 7 2 2+��� Gregrory’s series: � 4 = 1− 13 + 15 − 17 + 19 − � � � Newton’s series: � 6 = 1 2 + 1 2 � 3 � 23 + 1 � 3 2 � 4 � 5 � 25 + � � � Sharp’s series: � 6 = 1p 3 � 1− 1 31 � 3 + 1 32 � 5 − 1 33 � 7 + � � � � Euler’s series: �2 6 = 1 12 + 1 22 + 1 32 + 1 42 + 1 52 + � � � �2 8 = 1 12 + 1 32 + 1 52 + 1 72 + 1 92 + � � � �2 12 = 1 12 − 122 + 132 − 142 + 152 − � � � Derivatives: 1. d(cu) dx = c du dx ; 2. d(u + v) dx = du dx + dv dx ; 3. d(uv) dx = u dv dx + v du dx ; 4. d(un) dx = nun−1 du dx ; 5. d(u=v) dx = v ( du dx �− u( dvdx� v2 ; 6. d(ecu) dx = cecu du dx ; 7. d(cu) dx = (ln c)cu du dx ; 8. d(ln u) dx = 1 u du dx ; 9. d(sin u) dx = cos u du dx ; 10. d(cos u) dx = − sin udu dx ; 11. d(tan u) dx = sec2 u du dx ; 12. d(cot u) dx = csc2 u du dx ; 13. d(sec u) dx = tan u sec u du dx ; 14. d(csc u) dx = − cot u csc udu dx ; 15. d(arcsin u) dx = 1p 1− u2 du dx ; 16. d(arccos u) dx = −1p 1− u2 du dx ; 17. d(arctan u) dx = 1 1 + u2 du dx ; 18. d(arccot u) dx = −1 1 + u2 du dx ; 19. d(arcsec u) dx = 1 u p 1− u2 du dx ; 20. d(arccsc u) dx = −1 u p 1− u2 du dx ; 21. d(sinh u) dx = cosh u du dx ; 22. d(cosh u) dx = sinh u du dx ; 23. d(tanh u) dx = sech2 u du dx ; 24. d(coth u) dx = − csch2 udu dx ; 25. d(sech u) dx = − sech u tanhudu dx ; 26. d(csch u) dx = − csch u coth udu dx ; 27. d(arcsinh u) dx = 1p 1 + u2 du dx ; 28. d(arccosh u) dx = 1p u2 − 1 du dx ; 29. d(arctanh u) dx = 1 1− u2 du dx ; 30. d(arccoth u) dx = 1 u2 − 1 du dx ; 31. d(arcsech u) dx = −1 u p 1− u2 du dx ; 32. d(arccsch u) dx = −1 jujp1 + u2 du dx : Integrals: 1. Z cu dx = c Z u dx; 2. Z (u + v) dx = Z u dx + Z v dx; 3. Z xn dx = 1 n + 1 xn+1; n 6= −1; 4. Z 1 x dx = lnx; 5. Z ex dx = ex; 6. Z dx 1 + x2 = arctan x; 7. Z u dv dx dx = uv − Z v du dx dx; 8. Z sinx dx = − cos x; 9. Z cos x dx = sinx; 10. Z tan x dx = − ln j cos xj; 11. Z cot x dx = ln j cos xj; 12. Z sec x dx = ln j sec x + tan xj; 13. Z csc x dx = ln j csc x + cot xj; 14. Z arcsin xadx = arcsin x a + p a2 − x2; a > 0; Partial Fractions Let N(x) and D(x) be polynomial func- tions of x. We can break down N(x)=D(x) using partial fraction expan- sion. First, if the degree of N is greater than or equal to the degree of D, divide N by D, obtaining N(x) D(x) = Q(x) + N 0(x) D(x) ; where the degree of N 0 is less than that of D. Second, factor D(x). Use the follow- ing rules: For a non-repeated factor: N(x) (x− a)D(x) = A x− a + N 0(x) D(x) ; where A = � N(x) D(x) � x=a : For a repeated factor: N(x) (x− a)mD(x) = m−1X k=0 Ak (x− a)m−k + N 0(x) D(x) ; where Ak = 1 k! � dk dxk � N(x) D(x) �� x=a : The reasonable man adapts himself to the world; the unreasonable persists in trying to adapt the world to himself. Therefore all progress depends on the unreasonable. { George Bernard Shaw Theoretical Computer Science Cheat Sheet Calculus Cont. 15. Z arccos xadx = arccos x a − p a2 − x2; a > 0; 16. Z arctan xadx = x arctan x a − a2 ln(a2 + x2); a > 0; 17. Z sin2(ax)dx = 12a