Math 301: Introduction to Combinatorial Theory
.png)
Colorado State University, Fall 2018
Instructor: Henry Adams
Email: henry dot adams at colostate dot edu
Office: Weber 125
Office Hours:
- Wednesdays 12-1pm in Military Sciences 115,
- Wednesdays 1-2pm in Military Sciences 115,
- 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
Homework 1 (LaTeX Source) is due Friday, August 24.Homework 2 (LaTeX source) is due Friday, August 31.
Homework 3 (LaTeX source) is due Friday, September 7.
Homework 4 (LaTeX source) is due Friday, September 14.
Homework 5 (LaTeX source) is due Friday, September 21.
Homework 6 (LaTeX source) is due Friday, October 5.
Homework 7 (LaTeX source) is due Friday, October 12.
Homework 8 (LaTeX source) is due Friday, October 19.
Homework 9 (LaTeX source) is due Friday, October 26.
Homework 10 (LaTeX source) is due Monday, November 12.
Homework 11 (LaTeX source) is due Friday, November 16.
Homework 12 (LaTeX source) is due Friday, November 30.
Homework 13 (LaTeX source) is due never.
We will have weekly homework assignments. All homework is due in class at the beginning of class. Your homework should be legible and stapled.
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 20 | Introduction and course overview | |
| Aug 22 | §1.1 Example counting problems, §1.2 Sets | |
| Aug 24 | §1.2 Sets, §1.3 Number of subsets | Homework 1 due |
| Aug 27 | §1.3 Number of subsets, §1.5 Sequences | |
| Aug 29 | §1.6 Permutations, §1.7 Ordered subsets | |
| Aug 31 | §1.8 The number of subsets of a given size | Homework 2 due |
| Sept 3 | Holiday - no class! | |
| Sept 5 | §2.1 Induction | Last day to drop or change grading option |
| Sept 7 | §2.4 Pigeonholes | Homework 3 due |
| Sept 10 | §3.1 Binomial theorem | |
| Sept 12 | §3.2 Multinomial coefficients I, §3.3 Multinomial coefficients II | |
| Sept 14 | §3.4 Distributing money | Homework 4 due |
| Sept 17 | §3.5 Pascal's triangle, §3.6 Identities in Pascal's triangle | |
| Sept 19 | §4.1 Fibonacci numbers | |
| Sept 21 | §4.2 Fibonacci identities | Homework 5 due |
| Sept 24 | §4.3 A formula for the Fibonacci numbers | |
| Sept 26 | Review | |
| Sept 28 | Midterm #1 | Midterm through §3.6 |
| Oct 1 | §6.1 Divisibility of integers, §6.2 Primes and their history | |
| Oct 3 | §6.3 Factorization into primes | |
| Oct 5 | §6.4 On the set of primes | Homework 6 due |
| Oct 8 | §6.6 The Euclidean algorithm | |
| Oct 10 | §6.7 Congruences, §6.8 Division and inverses modulo m | |
| Oct 12 | §6.8 Division and inverses modulo m, and public key cryptography | Homework 7 due |
| Oct 15 | §7.1 Graphs: Even and odd degrees | End of course withdrawal period |
| Oct 17 | §7.2 Paths, cycles, and connectivity | |
| Oct 19 | §7.3 Eulerian walks and Hamiltonian cycles | Homework 8 due |
| Oct 22 | §12.1 Euler's formula for planar maps | |
| Oct 24 | §12.2 Planar graphs | |
| Oct 26 | §12.3 Euler's formula for polyhedra | Homework 9 due |
| Oct 29 | §8.1 How to define trees, §8.2 How to grow trees | |
| Oct 31 | Review | |
| Nov 2 | Midterm #2 | Midterm through §7.3 |
| Nov 5 | §8.2 How to grow trees, §8.3 How to count trees | |
| Nov 7 | §8.4 How to store trees | |
| Nov 9 | TBD | |
| Nov 12 | §8.4 How to store trees | Homework 10 due |
| Nov 14 | §9.1 Finding the best tree, §9.2 Traveling salesperson problem | |
| Nov 16 | §13.1 Coloring regions with two colors (Video) | Homework 11 due |
Fall Recess, Nov 19-23 | ||
| Nov 26 | §13.2 Coloring graphs with two colors (Video) | |
| Nov 28 | §13.3 Coloring graphs with many colors (Video) | |
| Nov 30 | §13.3 Coloring graphs with many colors | Homework 12 due |
| Dec 3 | §13.4 Map coloring and the four color theorem | |
| Dec 5 | Review and class picture | |
| Dec 7 | Review | |
Final Exam, Tuesday December 11 |
||
| 4:10-6:10pm in Military Sciences 115 | ||