Discrete Mathematics for Computer Science

Terms Meaning Section

Aim, ni or A(m, it) Two dimensional array notation 6.5

W(G) = ZeeE(G) w(e) Weight of graph G 6.11.3

indeg(v) Indegree of vertex v 6.14.1

outdeg(v) Outdegree of vertex v 6.14.A

TnTournament on n vetes 6.20

6 (G) Minimum degree in G 6.21.3

A(G) Maximum degree in G 6.21.3

Counting and Combinatorics

P(n, r) Number of permutations of r of n elements 7.5

C(n, r) Number of r-sets of an n-set 7.5.4

P (n; ri, r2 ... , rk) Number of yermutations with 7.8.1

repeated objects
[xIt Stirling numbers of the first kind 7.11
s(n, t) Stirling numbers of the second kind 7.11

Discrete Probability

b(n; k, p) Binomial distribution 8.7.2

E*= £1 x ... x xEi x ... x U2n Event in cross product space 8.3.5

P(X = x) P(o: P(w) = x 1 ) 8.7.1

h(k; n, t, m) Hypergeometric distribution 8.7.3

E(X) Expectation of X 8.7.4

pA Mean 8.7.4

Var(X) Variance of X 8.9.1

a Standard deviation 8.9.1

Recurrence Relations

a. = can-I First order recurrence relation 9.2

an = Clan-1 + C2an-2 Second order recurrence relation 9.4.1

Pseudocode

if cond. then S, else S 2 1.8.1
for i = a to b do S 1.8.1
/ text / 1.8.1
for i = n downto mS 5.6.4

for each x E X do 6.7.2