Index Index
using sets, Summary
adjacent
edges, Item
alternating path, Exercise
ancestor (in a rooted tree), Paragraph
and (logical connective), Item
truth condition for, Item
antecedent. See hypothesis
argument, Summary
arithmetic sequence, Summary
summing, Subsubsection
atomic statement, Paragraph
augmenting path, Exercise
balls and bins. See stars and bars
bijection, Subsection Paragraph Item
counting, Example
binary connective, Paragraph
binary digit. See bit
binary predicate, Exercise
binary representation, Exercise
binomial coefficient, Subsection Paragraph Paragraph Summary
closed formula for, Summary
objects counted by, Summary
recurrence relation for, Summary
binomial identity, Paragraph
examples of, Paragraph
bit, Paragraph
bit string, Subsection Paragraph Summary Exercise
as code for a subset, Paragraph
combinatorial proof involving, Exercise
correspondence with lattice path, Paragraph
relation to stars and bars, Paragraph
Boolean variable. See propositional variable
breadth first search, Paragraph
Brooks' Theorem, Theorem
Canadians, set of, Paragraphs
cannonball stacking, Exercise
cardinality, Paragraph
of a set, Item
of Cartesian product, Summary
of power set, Exercise
cardinality of, Summary
cases, Subsection
characteristic polynomial, Summary
characteristic roots, Subsection Summary Paragraph
repeated, Summary
chessboard
counting squares on, Paragraph
rook paths, Investigate!
tiling, Exercise
child (in a rooted tree), Paragraph
chordal graph, Paragraph
Christmas, Exercise
chromatic index, Paragraph
Euler, Section
clique, Paragraph
closed formula, Summary
for a function, Paragraph
for a sequence, Summary
for arithmetic sequence, Summary
for geometric sequence, Summary
coloring
edges, Subsection
vertices, Paragraph
vertices vs edges, Exercise
combination, Section
closed formula for, Summary
common difference, Summary
common ratio, Summary
complete bipartite graph, Paragraph Paragraphs Item
complete graph, Paragraph Paragraphs Item
complex numbers (as characteristic roots), Paragraph
composition of functions, Exercise
congruence, Summary
arithmetic, Summary
divisibility, Summary
division, Summary
equality, Summary
equivalence relation, Summary
solving, Subsection
without solutions, Summary
conjunction, Item
consequent. See conclusion
contradiction, Subsection
contrapositive, Item
proof by, Subsection
converse, Item
convex polyhedron, Paragraph
counterexample, Subsection
counting, Chapter
divisors, Exercise
edges in a graph, Lemma
functions, Example
cover (vertex), Exercise
cube, Investigate!
type of graph, Paragraphs
De Morgan's laws, Summary
deduction rule, Paragraph
degree sequence, Paragraph
maximum, Paragraph
sum formula, Lemma
depth first search, Paragraph
derangement, Paragraph
fraction of all permutations that are, Exercise
descendant (in a rooted tree), Paragraph
difference equation. See recurrence relation
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
for implication, Summary
disjoint events, Paragraph
disjunction, Item
equivalent implication, Summary
with upper bound restriction, Paragraph
divisibility, Summary
divisibility relation, Subsection Summary
division with remainder. See division algorithm
dodecahedron, Subsection
domain of discourse. See universe set
domino, Investigate! Exercise Exercise
double induction. See induction, double
double negation, Summary
element of a set, Paragraph
empty set, Item
enumeration. See counting
equality of graphs, Example
Euclidean algorithm, Paragraph
Euler's formula for planar graphs, Summary
exclusive or, Paragraph
existential quantifier, Summary
face (planar graph), Investigate! Paragraph
factorial, Paragraph
differences, Item
identity, Exercise
finite differences, Summary
football (American), Exercise
for all (quantifier), Summary
Four Color Theorem, Theorem
free variable, Paragraph
counting, Example Paragraphs Subsection Paragraph Paragraph
how to describe, Subsection
increasing
counting, Exercise
non-decreasing
counting, Exercise
notation, Item
gcd. See greatest common divisor
generating function, Section
differencing, Subsection
multiplication and partial sums, Subsection
recurrence relation, Subsection
geometric sequence, Summary
summing, Subsubsection
girth, Paragraph
Goldbach conjecture, Paragraph
golden ratio, Paragraph
chordal, Paragraph
chromatic index, Paragraph
clique, Paragraph
coloring vertices vs edges, Exercise
complete, Paragraph Paragraphs Item
complete bipartite, Paragraphs Item
cycle, Paragraphs Item Item
degree sequence, Paragraph
drawing, Paragraph
equal vs isomorphic, Example
equality, Example
Euler circuit, Item
Euler path, Item
forest, Item
girth, Paragraph
induced subgraph, Item
isomorphic (intuitive definition), Paragraph
isomorphic (precise definition), Summary
isomorphism class, Paragraph
leaf, Item
maximum degree, Paragraph
path, Paragraphs Item Item
Petersen, Exercise
planar, Item
simple, Paragraph
trail, Item
tree, Item
walk, Item
graph (of a function), Paragraph
greatest common divisor, Paragraph
Hall's Marriage Theorem, Theorem
in bipartite graph, Exercise
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
houses and utilities puzzle, Example
hypothesis, Summary
icosahedron, Subsection
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
direct proof for, Summary
equivalent disjunction, Summary
implicit quantifier, Paragraphs
implies (logical connective), Item
truth condition for, Item
inclusion/exclusion. See principle of inclusion/exclusion
inclusive or, Paragraph
for strong induction, Item
double, Exercise
incorrect use of, Paragraphs
for strong induction, Item
proof structure, Summary
strong, Subsection Summary
strong, Paragraph
initial condition, Summary
for a function, Summary
injection, Item Subsection Paragraph Item
integer lattice, Paragraph
integer solutions to equation (counting), Example
interior angles, Exercise
inverse image, Subsection Paragraph Item
comparison to inverse function, Paragraph
of a subset, Item
isomorphic
intuitive definition, Paragraph
precise definition, Summary
isomorphism class, Paragraph
isomorphism of graphs, Summary
\(K_n\), Paragraph
knights and knaves, Investigate! Investigate! Exercise
Kruskal's algorithm, Paragraph
Königsberg, Seven Bridges of, Investigate! Paragraph
lattice path, Paragraph
correspondence with bit string, Paragraph
length of, Paragraph
lattice, integer. See integer lattice
law of logic, Example
linear Diophantine equation. See Diophantine equation
logical equivalence, Summary
logically valid. See law of logic
magic chocolate bunnies, Exercise
marriage problem. See matching
partial, Exercise
mathematical induction. See induction; induction
maximum degree, Paragraph
minimum spanning tree, Paragraph
mod, Paragraph
modular arithmetic, Summary
modulo \(n\), Summary
modus ponens, Paragraph
molecular statement, Paragraph
monochromatic, Paragraphs
using sets, Summary
multiset
counting, Exercise
relation to multigraph, Paragraph
\(n\) choose \(k\). See binomial coefficient
natural numbers, set of, Item
necessary condition, Summary
negation, Item
interaction with quantifiers, Summary
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
parent (in a rooted tree), Paragraph
partial matching, Exercise
partial sums. See sequence of partial sums
partition, Paragraph
Pascal's triangle, Subsection Paragraph Item Item
patterns in, Subsection
sum of row in, Exercise
alternating, Exercise
augmenting, Exercise
type of graph, Paragraphs
perfect matching. See matching
of \(k\) elements chosen from \(n\) (see \(k\)-permutation of \(n\) elements)
of \(n\) elements, Summary
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
regular, Investigate!
polynomial fitting, Section
cardinality of, Exercise
predicate, Paragraph
binary, Exercise
premises, Summary
Prim's algorithm, Paragraph
principle of inclusion/exclusion, Section Subsection
for 2 sets, Summary
for 3 sets, Summary
for 4 or more sets, Paragraph
product notation, Paragraphs Exercise Exercise
product principle. See multiplicative principle
proof
by cases, Subsection
by contradiction, Subsection
by contrapositive, Subsection
proper vertex coloring, Item
proposition, Paragraph
propositional variable, Paragraph
puzzle, Exercise
cardinality, Exercise
chocolate bar, Quotation
domino path, Exercise
houses and utilities, Example
knights and knaves, Investigate! Investigate!
seven bridges, Investigate!
square division, Exercise
Tower of Hanoi, Investigate!
Pythagorean theorem, Paragraph
Pythagorean triple, Paragraph
quantifier, Summary
for all, Summary
implicit, Paragraphs
interaction with negation, Summary
there exists, Summary
racetrack principle, Paragraph
Ramsey theory, Paragraphs
rational numbers, set of, Item
real numbers, set of, Item
recurrence relation, Summary
finding for sequence, Example
for a function, Summary
for binomial coefficient, Summary
for number of bit strings, Paragraph
for number of lattice paths, Paragraph
generating function, Subsection
verifying solution to, Example
recursive definition, Summary
for arithmetic sequence, Summary
for geometric sequence, Summary
recursively defined function, Summary
reference, self. See self reference
region (graph). See face (planar graph)
regular polyhedron, Investigate!
remainder class, Subsection
residue class. See remainder class
rook paths, Investigate!
root (in a tree), Paragraph
rooted tree, Paragraph Subsection
rule of four, Paragraph
search
breadth first, Paragraph
depth first, Paragraph
self reference. See reference, self
sentence (compared to statement), Paragraph
sentential variable. See propositional variable
sequence, Paragraph
as function, Paragraph
inductive definition for, Summary
notation for, Paragraph
sequence of partial sums, Paragraphs Example Exercise Exercise
for Fibonacci sequence, Item
for triangular numbers, Paragraph
set, Paragraph
cardinality, Item
complement, Item
intersection, Item
notation for, Subsection
of all subsets (see power set)
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 Paragraphs
simple graph, Paragraph
six color theorem, Exercise
size of a set
see cardinality, Item
solitary number, Exercise
spanning tree, Subsection Summary
minimum, Paragraph
square numbers, Summary
stars and bars, Section
chart, Paragraph
vs combination, Item
statement, Paragraph
sticks and stones. See stars and bars
string
binary (see bit string)
strong induction. See induction, strong
subset, Subsection Paragraph
counting, Subsection
encoding as bit string, Paragraph
sufficient condition, Summary
sum principle. See additive principle
summation notation, Example Paragraphs Exercise Exercise
surjection, Item Subsection Paragraph Item
tautology, Paragraph
telescoping, Paragraph
tetrahedron, Subsection
there exists (quantifier), Summary
tour, Euler. See Euler circuit
Tower of Hanoi, Investigate! Paragraph
trail, Item
Euler (see Euler path)
transitive sets, Exercise
number of edges and vertices, Proposition
rooted, Paragraph Subsection
spanning, Subsection Summary
truth condition, Summary
for and, Item
for if and only if, Item
for if…, then…, Item
for not, Item
for or, Item
truth table, Subsection
The Twelve Days of Christmas, Exercise
valid, Summary
variable, propositional, Paragraph
Venn diagram, Subsection Paragraph
for counting, Paragraph
intersection, Paragraph
set difference, Paragraph
vertex cover, Exercise
degree sequence, Paragraph
Vizing's Theorem, Theorem
Euler (see Euler path)
weight (bit string), Item
zombies, Exercise