Syllabus updated November 13, 2006.

Basic course info

Grades and duties

Course Outline

Texts

Course Description

Introduction:

Combinatorics is the study of counting the number of elements in a finite set.  Much of mathematics could be described in this way, but enumerative combinatorics has been formalized and unified over the last 50 years, based on motivation from computer science.  This focus has brought coherence and unity to the subject. 

This course teaches concepts, methods and models of counting and estimation that are essential for any discrete mathematician and are valuable for researchers in algebra, statistics, computer science, computer engineering and other scientific fields.
 

Grades and Duties

Grades will be determined by the following items:

1. Homework 1, due around January 30. (15 pts.)
2. Homework 2, due around February 20. (15 pts.)
3. Homework 3, due around March 27. (15 pts.)
4. Homework 4, due around April 10. (15 pts.)
5. Take-home midterm exam, due around March 6. (20 pts.)
6. Take-home final exam, due around April 24. (20 pts.)

Exams: The midterm exam will cover first-half topics and the final exam will cover second-half topics only. The exams will be take-home exams and will be assigned the previous Thursday. Students may not work with anyone else on a take-home exam. The scheduled dates are T 3/6 and T 4/24.

Homework assignments: Scheduled due dates for these are T 1/30, T 2/20, T 3/27, T 4/10. These dates can easily be changed upon request. These problems will be distributed at least one week before the due date and will be posted on the archive page. Students may collaborate on homework but must submit their own writeup individually. Typed solutions are preferred. You may submit them electronically if you wish. If you are planning to give a seminar talk this semester in any related seminar (see Discrete Math seminar or Algebra seminar, for example) you can be excused from one homework assignment. See me first.

The main course page at http://orion.math.iastate.edu/rymartin/ISU606/ISU606.shtml will have updates as well as a general outline for the course.

Preliminary Course Outline:

• Weeks 1-4: Basic counting: Useful inequalities, Stirling's formula, inclusion-exclusion, permutation statistics, the twelvefold way
• Weeks 5-7: Generating functions: ordinary and exponential generating functions, recurrence relations, counting using generating functions
• Weeks 8-11: Extremal set theory: Intersecting systems and Erdős-Ko-Rado, property B of hypergraphs, shadows and Kruskal-Katona
• Weeks 12-14: Partially ordered sets: semi-lattices and lattices, Dilworth's theorem, Sperner's theorem, Möbius inversion
• Week 15: Other topics: based on class interest

Texts: There is no formal textbook for the course. I will cull my notes from a number of texts.