MATH 108: Introduction to Combinatorics and its Applications

Stanford University, Winter 2017

Lectures: Tue/Thu 1:30 - 2:50 PM, room 380C
Instructor: Jan Vondrak (jvondrak@stanford.edu)
Course Assistant: Zev Rosengarten (zevrosengarten@gmail.com)
Office hours:
Monday 3-4 pm, 383-J (Jan)
Friday 3-4 pm, 381-N (Zev)

FINAL EXAM: Monday, March 20, 12:15 - 3:15 PM in 380-C.
Sample Final Exam and some information here .

Course description: This is an introductory course in combinatorics. Tentative list of topics:

graphs, vertex coloring, edge coloring
matchings, Konig's theorem
the Boolean cube, posets, chains and antichains
Latin squares and finite projective planes
enumerative combinatorics, recurrences and generating functions
counting and generation of permutations, trees and partitions

A more detailed syllabus can be downloaded here.

Prerequisites: Linear algebra and calculus (Math 51).

Textbook:

Jiri Matousek and Jaroslav Nesetril: Invitation to Discrete Mathematics

While much of the material we will cover is in this book, some isn't. You are expected to come to class and take your own notes.

Grading:

Homework constitutes 30% of the grade.
The midterm exam (closed book) constitutes 30% of the grade.
The final exam constitutes 40% of the grade.

Midterm and final exam: will be closed-book (one 3" x 5" card of notes allowed).

Class policy is: PLEASE SOLVE THE PROBLEMS ON YOUR OWN. If the problems seem too hard, something's wrong - come and talk to me.
Please try to write out complete arguments, using full sentences in a way that we can read them.

If you don't have experience with rigorous proofs, here is a nice essay on how to construct proofs and write them down properly.