Math 301: Introduction to Combinatorial Theory
.png)
Colorado State University, Fall 2019
Instructor: Henry Adams
Email: henry dot adams at colostate dot edu
Office: Weber 125
Office Hours:
- Wednesdays 2-3pm in Weber 017,
- Thursdays 10-11am in Weber 017,
- or by appointment.
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 | ||