Formulario matematic

asTheoretical Computer Science Cheat Sheet Definitions f (n) = O(g(n)) f (n) = Ω(g(n)) f (n) = Θ(g(n)) f (n) = o(g(n))
n→∞

Series
n

iff ∃ positive c, n0 such that 0 ≤ f (n) ≤ cg(n) ∀n ≥ n0 . iff ∃ positive c, n0 such that f (n) ≥ cg(n) ≥ 0 ∀n ≥ n0 . iff f (n) = O(g(n)) and f (n) = Ω(g(n)). iff limn→∞ f (n)/g(n) = 0. iff ∀ > 0, ∃n0 such that |an − a| < , ∀n ≥ n0 . least b ∈ R such that b ≥ s, ∀s∈ S. greatest b ∈ R such that b ≤ s, ∀s ∈ S.
n→∞ n→∞

i=
i=1 n

n(n + 1) , 2

n i=1

i2 =

n(n + 1)(2n + 1) , 6
n

n i=1

i3 =

n2 (n + 1)2 . 4

In general: im =
i=1 n−1

1 (i + 1)m+1 − im+1 − (m + 1)im (n + 1)m+1 − 1 − m+1 i=1 1 m+1
m k=0

im =
i=1

m+1 Bk nm+1−k . k
∞

lim an = a sup S inf S lim inf an
n→∞

Geometric series: n cn+1 − 1 , ci = c−1 i=0
n

c= 1,
i=0

ci =

1 , 1−c

∞

ci =
i=1 ∞

c , 1−c c , (1 − c)2

|c| < 1, |c| < 1.

ici =
i=0

ncn+2 − (n + 1)cn+1 + c , (c − 1)2
n

c = 1,
i=0

ici =

lim inf{ai | i ≥ n, i ∈ N}. lim sup{ai | i ≥ n, i ∈ N}.

Harmonic series: Hn =
i=1 n

lim sup an
n→∞ n k n k

1 , i

n

iHi =
i=1 n i=1

n(n + 1) n(n − 1) Hn − . 2 4 n+1 m+1 3. = Hn+1 − n k = 1 m+1 .Combinations: Size k subsets of a size n set. Stirling numbers (1st kind): Arrangements of an n element set into k cycles. Stirling numbers (2nd kind): Partitions of an n element set into k non-empty sets. 1st order Eulerian numbers: Permutations π1 π2 . . . πn on {1, 2, . . . , n} with k ascents. 2nd order Eulerian numbers. Catalan Numbers: Binary trees with n + 1 vertices.

Hi = (n + 1)Hn − n,
i=1i Hi = m
n

1. 4. 6. 8.

n k n k n m
n k=0

=

n! , (n − k)!k!

2.
k=0

n k

= 2n , 5. n k
n

n , n−k

n k

n n−1 , = k k−1 m k k m = = n k

n−1 n−1 + , k k−1 = r+n+1 , n = = + r+s , n n n = 1,

n k

n−k , m−k

7.
k=0 n

r+k k r k 11.

n+1 , m+1
k

9.
k=0

s n−k n 1

n k

10. 12.

n k n 2

= (−1)

k−n−1 , k 13.

14. 18. 22. 25. 28. 31. 34.36.

n−1 , k−1 n n n n n = (n − 1)!, 15. = (n − 1)!Hn−1 , 16. = 1, 17. ≥ , 1 2 n k k n 2n n 1 n n−1 n−1 n n n , = n!, 21. Cn = = (n − 1) + , 19. = = , 20. n+1 n k k k k−1 n−1 n−1 2 k=0 n n n n n n−1 n−1 = = 1, 23. = , 24. = (k + 1) + (n − k) , 0 n−1 k n−1−k k k k−1 n n+1 0 n 1 if k = 0, 27. = 3n − (n + 1)2n + , = 26. = 2n − n − 1, 2 2 k 1 0 otherwise n m n n n x+k n n+1 n k 30. m! = , 29. = (m +1 − k)n (−1)k , , xn = m k n m k k n−m = 2n−1 − 1, n k =k
k=0

Cn

n−1 k

n m n k

n k=0

=

n k

n−k (−1)n−k−m k!, m n−1 k n k + (2n − 1 − k)

k=0

k=0

32. n−1 k−1 ,

n 0

= 1,

33. 35.

n n
n k=0 n

= 0 for n = 0, n k = (2n)n , 2n

= (k + 1)
n

x x−n

=
k=0

x+n−1−k , 2n

37.

n+1 m+1

=
k

n k

k m

=
k=0

k (m + 1)n−k , mTheoretical Computer Science Cheat Sheet Identities Cont. 38. 40. 42. 44. 46. 48. n+1 = m+1 n m =
k

Trees 39. 41. 43. x = x−n
n k=0

k

n k n k =
k=0

k m

n

=
k=0

k n−k = n! n m

n k=0

1 k , k! m

n k

x+k , 2n

k+1 (−1)n−k , m+1
m

n = m

k

n+1 k+1
m

k (−1)m−k , m n+k , k

m+n+1 m n m =
k

n+k k , k k (−1)m−k , m m+n n+k k
k

m+n+1 = m n+1 k+1

k(n +k)
k=0

n+1 k+1 =
k

n 45. (n − m)! m m+k , k n , k 47.

=
k

k (−1)m−k , m m−n m+k m+n n+k k
k

for n ≥ m, m+k , k n−k m n . k

Every tree with n vertices has n − 1 edges. Kraft inequality: If the depths of the leaves of a binary tree are d1 , . . . , dn :
n

n n−m n +m

m−n m+k =

2−di ≤ 1,

n = n−m n +m

i=1

+m

n−k m

k

49.

+m

=

and equality holdsonly if every internal node has 2 sons.

Recurrences Master method: T (n) = aT (n/b) + f (n), a ≥ 1, b > 1 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) − 3m T (1) = T (n) − 3m = T (n) − nk where k = log2 3 ≈ 1.58496. Summing the right side we get m−1 m−1 n i 3 i 3 =n . 2 2i i=0 i=0 Let c = 3...