Skip to main content
Logo image

Index Index

additive principle. See sum principle
adjacent
edges, Item
vertices, Paragraph Item
alternating path, Exercise
ancestor (in a rooted tree), Paragraph
and (logical connective), Item
truth condition for, Item
antecedent. See hypothesis
antisymmetric, Paragraph
arbitrary, Paragraph
arithmetic sequence, Summary
summing, Subsection
atomic statement, Paragraph
augmenting path, Exercise
balls and bins. See sticks and stones
base case, Paragraph Item Item
biconditional, Item
counting, Example
binary connective, Paragraph
binary digit. See bit
binary predicate, Exercise
binary relation, Paragraph
binary representation, Exercise
binomial coefficient, Subsection Paragraph Paragraph
closed formula for, Theorem
binomial identity, Paragraph
examples of, Paragraph
binomial theorem, Theorem
bipartite graph, Paragraph Item
birthday paradox, Worksheet
bit, Paragraph
combinatorial proof involving, Exercise
Boolean variable. See propositional variable
breadth-first search, Paragraph
Brooks’ theorem, Theorem
Canadians, set of, Paragraphs
cannonball stacking, Exercise
cardinality, Paragraph Paragraph
of a set, Item
of power set, Exercise
cards, Investigate!
Cartesian product, Item Paragraph
characteristic equation, Paragraph Summary
characteristic polynomial, Summary
characteristic roots, Subsection Summary Paragraph
repeated, Summary
chessboard
counting squares on, Paragraph
missing squares, Exercise Exercise
rook paths, Investigate!
tiling, Exercise
child (in a rooted tree), Paragraph
chordal graph, Paragraph
Christmas, Exercise
chromatic index, Paragraph
chromatic number, Item Paragraph
circuit, Paragraph Summary
Euler, Section
clique, Paragraph
closed formula, Definition
for a function, Paragraph Paragraph
for a sequence, Paragraph Theorem
for arithmetic sequence, Summary
for geometric sequence, Summary
coloring
edges, Subsection
vertices, Paragraph
vertices vs edges, Exercise
combination, Section
closed formula for, Theorem
combinatorial proof, Section Paragraph
common difference, Summary
common ratio, Summary
complement (of an event), Paragraph
complement of a set, Item Paragraph
complement, probability of, Theorem
complete bipartite graph, Paragraph Paragraphs Item
complete graph, Paragraph Paragraphs Item
complete inverse image, Paragraph Item
complex numbers (as characteristic roots), Paragraph
composition of functions, Exercise
conditional, Item Definition
conditional probability, Subsection Definition
congruence, Summary
arithmetic, Summary
divisibility, Summary
division, Summary
equality, Summary
equivalence relation, Summary
solving, Subsection
without solutions, Summary
conjunction, Item
connected graph, Paragraph Item
connectives, Paragraph Definition
consequent. See conclusion
contradiction, Subsection
contrapositive, Definition
proof by, Subsection
converse, Definition
convex polyhedron, Paragraph
cookie, Example
corollary, Paragraph
counting, Chapter
divisors, Exercise
edges in a graph, Lemma
functions, Example
cover (vertex), Exercise
cycle, Item Item
Hamilton, Section Paragraph
type of graph, Paragraphs
De Morgan’s laws, Theorem
deduction rule, Paragraph
degree, Paragraph Item
degree sequence, Paragraph
maximum, Paragraph
sum formula, Lemma
\(\Delta^k\)-constant, Paragraph Theorem
depth-first search, Paragraph
derangement, Paragraph
fraction of all permutations that are, Exercise
descendant (in a rooted tree), Paragraph
design, Paragraph
difference of sets, Item Paragraph
differences of a sequence, Paragraph
differentiable functions
generalized product rule, Exercise
generalized sum rule, Exercise
Diophantine equation, Subsection Paragraph Summary
solution, Summary
direct proof, Subsection
discrete structures. See structures
disjoint, Paragraph
disjoint events, Paragraph
disjunction, Item
equivalent implication, Summary
distribution (counting), Section Example
with upper bound restriction, Paragraph
divides, Paragraph Summary
divisibility, Summary
divisibility relation, Subsection Summary
division algorithm, Paragraph Summary
division with remainder. See division algorithm
Doctor Who, Exercise Paragraph
dodecahedron, Subsection
domain of discourse. Paragraph; universe set
double induction. See induction, double
double negation, Summary
element chasing, Paragraph
element of a set, Paragraph
empty set, Paragraph Item
enumeration. See counting
equality of graphs, Example
equivalence relation, Paragraph Paragraph Summary
Euclidean algorithm, Paragraph
Euler circuit, Item Section Paragraph Summary
Euler’s formula for planar graphs, Summary
event (counting), Paragraph
event (probability), Paragraph
exclusive or, Paragraph
existential quantifier, Definition
exists, Definition
face (planar graph), Investigate! Paragraph
factorial, Paragraph
Fibonacci sequence, Paragraph Example Summary Exercise
differences, Item
identity, Exercise
recurrence relation, Paragraph
finite differences, Theorem
finite geometry, Paragraph
finite sequence, Paragraph
football (American), Exercise Exercise
for all, Definition
forest, Item Definition
four color theorem, Theorem
free variable, Paragraph
how to describe, Subsection
increasing
counting, Exercise
non-decreasing
counting, Exercise
notation, Item
two-line notation, Paragraph Item
gcd. See greatest common divisor
generating function, Section
differencing, Subsection
multiplication and partial sums, Subsection
recurrence relation, Subsection
geometric sequence, Summary
summing, Subsection
girth, Paragraph
Goldbach, Paragraph
Goldbach conjecture, Paragraph
golden ratio, Paragraph
adjacent, Paragraph Item
bipartite, Paragraph Item
chordal, Paragraph
chromatic index, Paragraph
chromatic number, Item Paragraph Theorem
clique, Paragraph
coloring vertices vs edges, Exercise
complete bipartite, Paragraphs Item
connected, Paragraph Item
degree, Paragraph Item
degree sequence, Paragraph
drawing, Paragraph
equal vs isomorphic, Example
equality, Example
Euler circuit, Item
Euler trail, Item
forest, Item
girth, Paragraph
induced subgraph, Item
isomorphic (intuitive definition), Paragraph
isomorphic (precise definition), Definition
isomorphism class, Paragraph
leaf, Item
maximum degree, Paragraph
multigraph, Paragraph Item
Petersen, Exercise
planar, Item
simple, Paragraph
subgraph, Definition Item
trail, Item
tree, Item
vertex coloring, Item Paragraph
walk, Item
graph (of a function), Paragraph
greatest common divisor, Paragraph
Hall’s Marriage theorem, Theorem
Hamilton cycle, Section Paragraph
in bipartite graph, Exercise
Hamilton path, Section Paragraph
in bipartite graph, Exercise
handshake lemma, Lemma
handshakes, Exercise
connection to graphs, Exercise
Hanoi, Investigate!
hat check problem, Example
hockey stick theorem, Exercise
homogeneous
recurrence relation, Paragraph
hypothesis, Definition
icosahedron, Subsection
if and only if (logical connective), Item
truth condition for, Item
iff. See if and only if
if…, then… (logical connective), Item
truth condition for, Item
image, Subsection
of a set, Paragraph
of a subset, Item
of an element, Paragraph Paragraph Item Item
implication, Item Definition
equivalent disjunction, Summary
implicit quantifier, Paragraphs
implies (logical connective), Item
truth condition for, Item
inclusion/exclusion. See principle of inclusion/exclusion
inclusive or, Paragraph
independence, Definition
induced subgraph, Definition Item
base case, Item
for strong induction, Item
contrasting regular and strong, Paragraph
double, Exercise
incorrect use of, Paragraphs
inductive case, Item
for strong induction, Item
proof structure, Summary
strong, Summary
inductive case, Paragraph Item Item
inductive hypothesis, Item Paragraph
initial condition, Definition
for a function, Summary
counting, Example Paragraph
integer lattice, Paragraph
integer solutions to equation (counting), Example
integers, set of, Item Item
interior angles, Exercise Exercise
intersection, Paragraph
intersection of sets, Item Paragraph
inverse, Definition
inverse image, Subsection Paragraph Item
comparison to inverse function, Paragraph
of a subset, Item
irreflexive, Paragraph
isomorphic
intuitive definition, Paragraph
precise definition, Definition
isomorphism class, Paragraph
isomorphism of graphs, Definition
\(k\)-permutation of \(n\) elements, Paragraph Definition
\(K_n\), Paragraph
knights and knaves, Investigate! Exercise Exercise
Kruskal’s algorithm, Paragraph
Königsberg, Seven Bridges of, Investigate! Paragraph
lattice path, Paragraph
length of, Paragraph
lattice, integer. See integer lattice
law of logic, Example
length of a bit string, Paragraph Definition
linear Diophantine equation. See Diophantine equation
logical connectives, Paragraph Definition
logical equivalence, Definition
logically valid. See law of logic
magic chocolate bunnies, Exercise
main connective, Example
marriage problem. See matching
matching, Section Paragraph
partial, Exercise
matching condition, Summary Theorem
mathematical induction. See induction; induction
maximum degree, Paragraph
minimal criminal, Paragraph
minimum spanning tree, Paragraph
mod, Paragraph
modular arithmetic, Summary
modulo \(n\), Summary
modus ponens, Paragraph
molecular statement, Paragraph
monochromatic, Paragraphs
Monty Hall problem, Paragraph
multigraph, Paragraph Item
multiplicative principle. See product principle
multiset, Paragraph
counting, Exercise
relation to multigraph, Paragraph
multisets (counting), Section
natural numbers, set of, Item
necessary condition, Definition
negation, Item
interaction with quantifiers, Summary
neighbors of vertices, Exercise Paragraph Theorem
neighbors of verties, Summary
non-planar graph, Subsection
\(K_{3,3}\), Theorem
\(K_5\), Theorem
Petersen graph, Exercise
not (logical connective), Item
truth condition for, Item
NP-complete, Paragraph
number theory, Section
octahedron, Subsection
one-to-one function. See injection
onto function. See surjection
operations on sets, Subsection
or (logical connective), Item
inclusive vs exclusive, Paragraph
truth condition for, Item
outcome (counting), Paragraph
outcome (probability), Paragraph
parent (in a rooted tree), Paragraph
partial matching, Exercise
partial sums. See sequence of partial sums
partition, Paragraph
Pascal’s triangle, Paragraph Item Item
patterns in, Subsection
sum of row in, Exercise
path, Item Item
alternating, Exercise
augmenting, Exercise
Euler (see Euler trail)
Hamilton, Section Paragraph
type of graph, Paragraphs
perfect graph, Paragraph Exercise
perfect matching. See matching
of \(k\) elements chosen from \(n\) (see \(k\)-permutation of \(n\) elements)
of \(n\) elements, Theorem
to count functions, Example
to count words, Example
Petersen graph, Exercise
PIE. See principle of inclusion/exclusion
pigeonhole principle, Example
planar graph, Item Investigate! Paragraph
chromatic number of, Theorem
non-planar graph, Subsection
\(K_{3,3}\), Theorem
\(K_5\), Theorem
Petersen graph, Exercise
planar region. See face (planar graph)
planar representation, Paragraph
Platonic solid. See regular polyhedron
playing cards, Exercise Investigate!
polyhedron, Paragraph Paragraph
regular, Investigate!
polynomial fitting, Section Theorem
power set, Item Item Paragraph
cardinality of, Exercise
powers of 2, Summary Example
predicate, Paragraph
binary, Exercise
premise, Definition
premises, Definition
prime numbers, Exercise Exercise Example
Prim’s algorithm, Paragraph
principle of inclusion/exclusion, Section Subsection
for 2 sets, Theorem
for 3 sets, Theorem
for 4 or more sets, Paragraph
probability, Definition
product notation, Exercise Exercise
product principle, Section Principle
proof, Definition
by contradiction, Subsection
by contrapositive, Subsection
by induction, Section Summary
by strong indcution, Section
combinatorial, Section Paragraph
proper vertex coloring, Item
propositional variable, Paragraph Paragraph
puzzle, Exercise
birthday, Worksheet
cardinality, Exercise
chocolate bar, Worksheet Exercise
domino trail, Exercise
knights and knaves, Investigate! Exercise
seven bridges, Investigate!
square division, Exercise
Tower of Hanoi, Investigate!
Pythagorean theorem, Paragraph
Pythagorean triple, Paragraph Paragraph
quantifier, Definition
implicit, Paragraphs
interaction with negation, Summary
scope, Example
racetrack principle, Paragraph
Ramsey theory, Paragraphs
random experiment, Paragraph
range of a function, Paragraph Item
rational numbers, set of, Item
real numbers, set of, Item
recurrence relation, Definition
finding for sequence, Example
for a function, Summary
for number of bit strings, Paragraph
generating function, Subsection
recursive definition, Definition
for a function, Paragraph
for a sequence, Paragraph
for arithmetic sequence, Summary
for geometric sequence, Summary
recursively defined function, Summary
reference, self. See self reference; self reference
reflexive, Paragraph
region (graph). See face (planar graph)
regular polyhedron, Investigate!
relation, Subsection
remainder class, Subsection
residue class. See remainder class
rook paths, Investigate!
root (in a tree), Paragraph
rooted tree, Paragraph Subsection
rule of four, Paragraph
sample space, Paragraph
scope (of quantifier), Example
scope of a quantifier, Example
search
breadth-first, Paragraph
depth-first, Paragraph
self reference. See reference, self; reference, self
sentence (compared to statement), Paragraph
sentential variable. See propositional variable
as function, Paragraph
closed formula for, Definition Example
inductive definition for, Definition
notation for, Paragraph
recursive definition for, Definition Example
sequence of partial sums, Paragraph Example Exercise Exercise
for Fibonacci sequence, Item
for triangular numbers, Paragraph
sequence, finite, Paragraph
cardinality, Item
complement, Item
difference, Item Paragraph
intersection, Item
notation for, Subsection
of all subsets (see power set)
of integers, Item Item
of natural numbers, Item
of rational numbers, Item
of real numbers, Item
operations, Subsection
product (see Cartesian product)
relationships between, Subsection
union, Item
Venn diagram, Subsection
set builder notation, Paragraph
Seven Bridges of Königsberg, Investigate! Paragraph
sibling (in a rooted tree), Paragraph
Sigma notation, Example Paragraph
simple graph, Paragraph
six color theorem, Exercise
size of a set
see cardinality, Item
solitary number, Exercise
sound, Definition
spanning tree, Subsection Definition
minimum, Paragraph
square numbers, Summary
stars and bars. See sticks and stones
statement, Definition Paragraph
sticks and stones, Section
vs combination, Item
string
binary (see bit string)
ternary, Exercise Exercise
strong induction, Section
structures, Paragraph
subgraph, Definition Item
counting, Subsection
sufficient condition, Definition
sum principle, Section Principle
using sets, Principle
sum principle (probability), Theorem
summation notation, Example Paragraph Exercise Exercise
symmetric, Paragraph
tautology, Paragraph Paragraph
term (of a sequence), Paragraph
ternary string, Exercise Exercise
tetrahedron, Subsection
tour, Euler. See Euler circuit
Tower of Hanoi, Investigate! Paragraph
trail, Item
transitive, Paragraph
transitive sets, Exercise
number of edges and vertices, Proposition
triangular numbers, Paragraph Summary Example Paragraph
truth condition, Definition
for and, Item
for if and only if, Item
for if…, then…, Item
for not, Item
for or, Item
truth table, Paragraph Subsection
truth value, Paragraph Paragraph
tuple. See sequence, finite
The Twelve Days of Christmas, Exercise
two-line notation, Paragraph Item
unary connective, Paragraph
uniform probability distribution, Paragraph
union, Paragraph
union of sets, Item Paragraph
cardinality of, Principle
universal generalization, Paragraphs Definition
universal quantifier, Definition
universe set, Item Paragraph
variable, propositional, Paragraph
Venn diagram, Subsection Paragraph
for counting, Subsection
intersection, Paragraph
set difference, Paragraph
vertex coloring, Item Paragraph
vertex cover, Exercise
vertex degree, Paragraph Item
degree sequence, Paragraph
Vizing’s theorem, Theorem
Euler (see Euler trail)
weight (bit string), Item
weight of a bit string, Paragraph Definition
word (counting), Example Example
zombies, Exercise