The topics listed below are covered by Problem Sets 1–3, lectures, the notes :FiniteSets” from the Files page of the Math 455 web site,, and the indicated sections from the textbook.

Sets and functions (1.2, 1.3)

• Union, intersection, complement (set difference), symmetric difference, power set: definitions, calculations, simple proofs
• Power set of a set: definition, # of elements in power set of n-element set
• Partition of a set: definition
• Injective, surjective, bijective functions: definitions; counting them (see below)
• Characteristic function of subset of a set: definition; use in counting # of subsets of a set

Mathematical induction and recursion (2.1, 3.1, 3.5–3.6, 4.1–4.2)

• proofs by mathematical induction
• proving and using formulas for sums (1 + 2 + ... + n, 1 + r + r² + ... + rⁿ, etc.)
• binomial coefficients, Pascal’s triangle: what they are, calculations, proving formulas about binomial coefficients
• recursively defined functions such as n! and the Fibonacci sequence

Combinatorics (1.5–1.8, 2.3–2.4, 3.2–3.4)

• Finite set: definition
• Sum Rule for # elements in disjoint union of 2 or more sets; # elements in a complement
• Inclusion-Exclusion Principle for 2, 3, and n sets
• Pigeonhole Principle and Generalized Pigeonhole Principle
• Product Rule for # (A x B) and generalization to product of n sets
• The Generalized Product Rule when each choice depends on prior choices
• Number of functions from one finite set to another, i.e., #(Y^X); special case:
  #(P(X)) via #({0, 1}^X)
• Binomial coefficients C(n, r)and # of r-element subsets of an n-element set
• Permutations of a finite set and # of such
• P(n, r) as # of injections from an r-element set to an n-element set; as # of ordered arrangements of r objects chosen from n
• “Stars-and-bars” and “X’s and wedges” models for counting
• Stirling numbers S(n, r) of the Second Kind and # of r-member partitions of an n-element set: you do not need to memorize the recursive formula for S(n, r); if you need it, I will state it on the exam
• Number of surjections of an n-element set onto an r-element set
• Number of derangements of a set: you do not need to memorize either the closed-form formula (obtained from PIE) or the recursive formula (my notes, sec. 5.3); if you need either, I will state it on the exam
• Applying the preceding principles and methods individually or in combination to real or fanciful counting problems

Mathematica

You’ll need a basic working knowledge of Mathematica in order to do some calculations.  You will have access to the notebooks SetsAndFunctions.nb and Combinatorics.nb.