Henry Adams

Math 301: Introduction to Combinatorial Theory

                        

Colorado State University, Fall 2019

Instructor: Henry Adams
Email: henry dot adams at colostate dot edu
Office: Weber 125
Office Hours:

Lectures: MWF 11:00-11:50am in Military Sciences 115
Textbook: Discrete Mathematics: Elementary and Beyond by László Lovász, József Pelikán, and Katalin Vesztergombi. This book is freely available as a PDF to CSU students if you login on the CSU library webpage.
List of typos

Overview: This course is an introduction to combinatorics. Topics covered include combinations, permutations, sets, induction, inclusion and exclusion, the pigeonhole principle, binomial coefficients, recurrence, prime numbers, graph theory, and trees. Additional topics will be chosen from Euler's formula, finite geometries, cryptography, and Ramsey's theorem.

Syllabus: Here is the course syllabus.

Course notes: Here is a typed version of Henry's course notes.

Book


  Update from 2023: Together with Kelly Emmrich, Maria Gillespie, Shannon Golden, and Rachel Pries, I wrote the book Counting Rocks! An Introduction to Combinatorics (2023). This book has been used for the class Math 301, Introduction to Combinatorial Theory, at Colorado State University. [Book Webpage, Book PDF, Videos]

Homework

We will have weekly homework assignments. All homework is due in class at the beginning of class. Your homework should be well-organized, legible, stapled, and with no dangling paper tabs on it if you rip it out of a spiral bound notebook.

Homework 1 (LaTeX source) is due Friday, September 6.
Homework 2 (LaTeX source) is due Friday, September 13.
Homework 3 (LaTeX source) is due Monday, September 23.
Homework 4 (LaTeX source) is due Friday, September 27.
Homework 5 (LaTeX source) is due Friday, October 11.
Homework 6 (LaTeX source) is due Friday, October 18.
Homework 7 (LaTeX source) is due Friday, October 25.
Homework 8 (LaTeX source) is due Friday, November 1.
Homework 9 (LaTeX source) is due Friday, November 15.
Homework 10 (LaTeX source) is due Friday, November 22.
Homework 11 (LaTeX source) is due Friday, December 6.
Homework 12 (LaTeX source) is due never.

Exams

The exams will be in-class. You will only be able to use your brain and a pen or pencil - no notes, books, or electronic devices. The exams will be comprehensive, except that Midterm 2 will emphasize the material after Midterm 1, and the Final will emphasize the material after Midterm 2.

Here is Practice Midterm 1A.
Here is Practice Midterm 1B.
Here is Practice Midterm 1C.
Here is Practice Midterm 2A.
Here is Practice Midterm 2B.
Here is Practice Midterm 2C.
Here is Practice Final A.
Here is Practice Final B.
Here is Practice Final C.

Schedule

Date Class Topic Remark

Aug 26 Introduction and course overview
Aug 28 §1.1 Example counting problems, §1.2 Sets
Aug 30 §1.2 Sets, §1.3 Number of subsets

Sep 2 Holiday - no class!
Sep 4 §1.3 Number of subsets, §1.5 Sequences
Sep 6 §1.6 Permutations, §1.7 Ordered subsets Homework due

Sept 9 §1.8 The number of subsets of a given size
Sept 11 §2.1 Induction Last day to drop or change grading option
Sept 13 §2.4 Pigeonholes Homework due

Sept 16 §3.1 Binomial theorem (Video)
Sept 18 §3.2 Multinomial coefficients I, §3.3 Multinomial coefficients II
Sept 20 §3.4 Distributing money

Sept 23 §3.5 Pascal's triangle, §3.6 Identities in Pascal's triangle Homework due
Sept 25 §4.1 Fibonacci numbers
Sept 27 §4.2 Fibonacci identities Homework due

Sept 30 §4.3 A formula for the Fibonacci numbers
Oct 2 Review
Oct 4 Midterm #1 Midterm through §3.6

Oct 7 §6.1 Divisibility of integers, §6.2 Primes and their history
Oct 9 §6.3 Factorization into primes
Oct 11 §6.4 On the set of primes Homework due

Oct 14 §6.6 The Euclidean algorithm
Oct 16 §6.7 Congruences, §6.8 Division and inverses modulo m
Oct 18 §6.8 Division and inverses modulo m, and public key cryptography Homework due

Oct 21 §7.1 Graphs: Even and odd degrees End of course withdrawal period
Oct 23 §7.2 Paths, cycles, and connectivity
Oct 25 §7.3 Eulerian walks and Hamiltonian cycles Homework due

Oct 28 §12.1 Euler's formula for planar maps
Oct 30 §12.3 Euler's formula for polyhedra
Nov 1 §12.2 Planar graphs Homework due

Nov 4 §8.1 How to define trees, §8.2 How to grow trees
Nov 6 Review
Nov 8 Midterm #2 Midterm through §7.3

Nov 11 §8.2 How to grow trees, §8.3 How to count trees
Nov 13 §8.4 How to store trees
Nov 15 §8.4 How to store trees Homework due

Nov 18 §9.1 Finding the best tree
Nov 20 §9.2 Traveling salesperson problem
Nov 22 §13.1 Coloring regions with two colors (Video) Homework due

Fall Recess, Nov 25-29
Dec 2 §13.2 Coloring graphs with two colors (Video)
Dec 4 §13.3 Coloring graphs with many colors (Video)
Dec 6 §13.3 Coloring graphs with many colors Homework due

Dec 9 §13.4 Map coloring and the four color theorem
Dec 11 Review and class picture
Dec 13 Review

Final Exam, Wednesday December 18
4:10-6:10pm in Military Sciences 115