Theoretical Computer Science Cheat Sheet
Definitions Series
f(n)=O(g(n)) iff ∃ positive c, n
0
such that
0 ≤ f(n) ≤ cg(n) ∀n ≥ n
0
.
n
i=1
i =
n(n +1)
2
,
n
i=1
i
2
=
n(n + 1)(2n +1)
6
,
n
i=1
i
3
=
n
2
(n +1)
2
4
.
In general:
n
i=1
i
m
=
1
m +1
(n +1)
m+1
− 1 −
n
i=1
(i +1)
m+1
− i
m+1
− (m +1)i
m
n−1
i=1
i
m
=
1
m +1
m
k=0
m +1
k
B
k
n
m+1−k
.
Geometric series:
n
i=0
c
i
=
c
n+1
− 1
c − 1
,c=1,
∞
i=0
c
i
=
1
1 − c
,
∞
i=1
c
i
=
c
1 − c
, |c| < 1,
n
i=0
ic
i
=
nc
n+2
− (n +1)c
n+1
+ c
(c − 1)
2
,c=1,
∞
i=0
ic
i
=
c
(1 − c)
2
, |c| < 1.
Harmonic series:
H
n
=
n
i=1
1
i
,
n
i=1
iH
i
=
n(n +1)
2
H
n
−
n(n − 1)
4
.
n
i=1
H
i
=(n +1)H
n
− n,
n
i=1
i
m
H
i
=
n +1
m +1

H
n+1
−
1
m +1
.
f(n)=Ω(g(n)) iff ∃ positive c, n
0
such that
f(n) ≥ cg(n) ≥ 0 ∀n ≥ n
0
.
f(n)=Θ(g(n)) iff f(n)=O(g(n)) and
f(n)=Ω(g(n)).
f(n)=o(g(n)) iff lim
n→∞
f(n)/g(n)=0.
lim
n→∞
a
n
= a iff ∀>0, ∃n
0
such that
|a
n
− a| <, ∀n ≥ n
0
.
sup S least b ∈ R such that b ≥ s,
∀s ∈ S.
inf S greatest b ∈ R such that b ≤
s, ∀s ∈ S.
lim inf
n→∞
a
n
lim
n→∞
inf{a
i
| i ≥ n, i ∈ N}.
lim sup
n→∞
a
n
lim
n→∞
sup{a
i
| i ≥ n, i ∈ N}.
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.
n
k=0
n
k
=2
n
, 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.
n
k=0
r + k
k
=
r + n +1
n
,
8.
n
k=0
k
m
=
n +1
m +1
, 9.
n
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
=2
n−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
{1, 2,...,n} with k ascents.
n
k
2nd order Eulerian numbers.
C
n
Catalan Numbers: Binary
trees with n + 1 vertices.
14.
n
1
=(n − 1)!, 15.
n
2
=(n − 1)!H
n−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.
n
k=0
n
k
= n!, 21. C
n
=
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
=
1ifk =0,
0 otherwise
26.
n
1
=2
n
− n − 1, 27.
n
2
=3
n
− (n + 1)2
n
+
n +1
2
,
28. x
n
=
n
k=0
n
k

x + k
n
, 29.
n
m
=
m
k=0
n +1
k
(m +1− k)
n
(−1)
k
, 30. m!
n
m
=
n
k=0
n
k

k
n − m
,
31.
n
m
=
n
k=0
n
k

n − k
m
(−1)
n−k−m
k!, 32.
n
0
=1, 33.
n
n
= 0 for n =0,
34.
n
k
=(k +1)
n − 1
k
+(2n − 1 − k)
n − 1
k −1
, 35.
n
k=0
n
k
=
(2n)
n
2
n
,
36.
x
x − n
=
n
k=0
n
k

x + n − 1 −k
2n
, 37.
n +1
m +1
=
k
n
k

k
m
=
n
k=0
k
m
(m +1)
n−k
,