Index Index
absorbing
Markov chain, Paragraph
state of a Markov chain, Paragraph
addition
formal definition of, Paragraph
adjacent vertices, Paragraph
algorithm
on-line, Section
polynomial time, Subsection
alphabet, Paragraph
antichain, Paragraph
antisymmetric, Item
arithmetic progression, Paragraph
array, Paragraph
automorphism
of poset, Paragraph
basis step, Paragraph
Bernoulli trials, Paragraph
big Oh notation, Paragraph
bijection, Paragraph
formula for, Proposition
generalized, Definition
recursive formula for, Paragraph
binomial theorem, Theorem
Newton’s, Theorem
bit string. See string, binary
capacity
of a cut, Paragraph
of an edge, Paragraph
cardinality, Paragraph
cartesian product, Paragraph
Catalan number, Example
Cayley’s formula, Theorem
certificate, Subsection
chain, Paragraph
chain partition, Paragraph
characters, Paragraph
circuit, Paragraph
clique, Paragraph
maximum size, Paragraph
clique number, Paragraph
Collatz sequence, Example
coloring
proper, Paragraph
combination, Paragraph
number of
formula for, Proposition
comparable, Paragraph
complex number
formal definition of, Paragraph
component, Paragraph
of poset, Paragraph
connected
poset, Paragraph
cover, Paragraph
cut, Paragraph
Dedekind, Paragraph
cycle, Paragraph
directed, Paragraph
cycle index, Paragraph
degree of a vertex, Paragraph
denominator, Paragraph
derangement, Paragraph
digraph, Paragraph
Dijkstra’s algorithm, Algorithm
Dilworth’s theorem, Theorem
dual of, Theorem
dimension, Exercise
distance, Paragraph
divides, Paragraph
division theorem, Theorem
divisor, Paragraph
common, Paragraph
greatest common, Paragraph
down set, Paragraphs
drawing of a graph, Paragraph
planar, Paragraph
dual, Paragraph
edge, Paragraph
directed, Paragraph
multiple, Paragraph
element, Paragraph
embedding, Paragraph
equivalence classes, Paragraph
Erdős-Ko-Rado Theorem, Theorem
Euclidean algorithm, Theorem
Euler \(\phi\) function, Paragraph
eulerian
circuit, Paragraph
trail, Exercise
Euler’s formula, Theorem
event, Paragraph
dependent, Paragraph
independent, Paragraph
expectation, Paragraph
expected value. See expectation
face, Paragraph
factorial
definition, Paragraph
recursive definition, Paragraph
Fibonacci
numbers, Subsection
flow, Paragraph
value of, Item
Ford-Fulkerson labeling algorithm, Algorithm
full house (poker hand), Example
function, Paragraph
injective, Paragraph
onto, Paragraph
Gale-Ryser theorem, Theorem
generating function, Paragraph
and solving recurrences, Section
exponential, Paragraph
ordinary, Paragraph
graph, Paragraph
\(2\)-colorable, Paragraph
acyclic, Paragraph
bipartite, Paragraph
matching in, Paragraph
complete, Paragraph
connected, Paragraph
directed (see digraph)
disconnected, Paragraph
eulerian, Paragraph
hamiltonian, Paragraph
incomparability, Paragraph
independent, Paragraph
intersection, Paragraph
interval, Paragraph
labeled, Paragraph
oriented, Paragraph
perfect, Paragraph
planar, Paragraph
regular, Item
shortest path in, Algorithm
simple, Paragraph
unlabeled, Paragraph
greatest common divisor. See divisor, greatest common
Euler \(\phi\) function, Section
ground set, Paragraph
group, Paragraph
permutation, Paragraph
symmetric, Paragraph
hamiltonian
cycle, Paragraph
Hasse diagrams, Paragraph
hat check problem, Paragraph
height, Paragraph
homeomorphic, Paragraph
incident to, Paragraph
incomparable, Paragraph
independent
event, Paragraph
random variables, Example
induction
strong, Paragraph
inductive hypothesis, Paragraph
inductive step, Paragraph
input size, Subsection
integers
formal definition of, Paragraph
positive, Paragraph
intersection, Paragraph
interval order, Paragraph
interval representation, Paragraph
distinguishing, Paragraph
inverse, Paragraph
isomorphism
of graphs, Paragraph
of posets, Paragraph
Kruskal’s algorithm, Algorithm
labeling algorithm, Algorithm
lattice, Paragraph
subset, Paragraph
lattice path, Paragraph
counting, Example
number not crossing \(y=x\), Example
leaf, Paragraph
length, Paragraph
of arithmetic progression, Paragraph
of path or cycle, Paragraph
letter, Paragraph
linear diophantine equation, Theorem
little oh notation, Paragraph
loop, Paragraph
Lovász Local Lemma, Paragraph
asymmetric, Lemma
symmetric, Lemma
Markov chain, Paragraph
matching, Paragraph
maximum, Paragraph
stable, Paragraph
matrix
stochastic, Paragraph
transition, Paragraph
maximal
antichain, Paragraph
chain, Paragraph
points of a poset, Paragraph
maximum
antichain, Paragraph
chain, Paragraph
mean. See expectation
membership, Paragraph
minimal
point of a poset, Paragraph
minimum weight spanning tree
Kruskal’s algorithm for, Algorithm
minimum weight spanning trees
Prim’s algorithm for, Algorithm
multigraph, Paragraph
multinomial coefficient, Paragraph
multinomial theorem, Theorem
multiplicative inverse, Paragraph
natural numbers, Item
neighbor, Paragraph
neighborhood (of a vertex), Paragraph
network, Paragraph
network flow, Paragraph
nondeterministic polynomial time, Paragraph
notes
musical, Paragraph
numerator, Paragraph
octave, Paragraph
operation
binary, Paragraph
operations, Paragraph
operator
advancement, Paragraph
linear, Paragraph
or
exclusive, Paragraph
inclusive, Paragraph
order
linear, Paragraph
on natural numbers, Section
ordered pairs, Paragraph
outcomes, Paragraph
partially ordered set, Paragraph
partition
dual, Paragraph
path, Paragraph
augmenting, Paragraph
directed, Paragraph
pattern inventory, Paragraph
Peano postulates, Paragraph
cycle notation for, Paragraph
function, Example
pigeon hole principle, Proposition
generalized, Proposition
planar drawing. See drawing of a graph, planar
poset, Paragraph
potential, Item
Prim’s algorithm, Algorithm
principle of inclusion-exclusion, Theorem
probability, Paragraph
conditional, Paragraph
measure, Paragraph
space, Paragraph
proof
combinatorial, Section
Prüfer code, Paragraph
pseudo-alphabetic order, Paragraph
small, Figure
symmetric, Section
random variable, Paragraph
rational numbers, Paragraph
real number
formal definition of, Paragraph
reciprocal, Paragraph
recurrence equation
constant coefficients, Paragraph Subsection
general solution, Paragraph
homogeneous, Paragraph
linear, Paragraph
nonconstant coefficients, Paragraph
nonlinear, Paragraph
particular solution, Example
repeated roots, Example
recurrence equations
nonhomogeneous, Subsection
recursive definition, Paragraph
reflexive, Item
regular
transition matrix, Paragraph
relation
symmetric, Exercise
sampling
without replacement, Example
scale, Paragraph
sequence, Paragraph
series
finite geometric, Paragraph
sum of, Paragraph
infinite geometric, Example
set, Paragraph
empty, Paragraph
finite, Paragraph
infinite, Paragraph
Zermelo-Fraenkel axioms, Section
Sigma-notation
definition of, Paragraph
sink, Paragraph
sorting, Paragraph
source, Paragraph
stabilizer, Paragraph
standard deviation, Paragraph
statement
open, Paragraph
statements
meaning of, Section
string, Paragraph
column sum, Paragraph
row sum, Paragraph
subdivision
elementary, Paragraph
subgraph, Paragraph
induced, Paragraph
spanning, Paragraph
subposet, Paragraph
subset, Paragraph
proper, Paragraph
successor, Item
Sudoku puzzle, Example
surjection, Paragraph
symmetric, Paragraph
transitive, Item
transposition
of a scale, Paragraph
tree, Paragraph
binary, Paragraph
ordered, Paragraph
rooted, Paragraph
unlabeled, Paragraph
trees
labeled, Paragraph
union, Paragraph
up set, Paragraphs
