The art of counting

Lectures: 2 sessions / week, 1 hour / session

The subject of enumerative combinatorics deals with counting the number of elements of a finite set. For instance, the number of ways to write a positive integer n as a sum of positive integers, taking order into account, is 2n-1. We will be concerned primarily with bijective proofs, i.e., showing that two sets have the same number of elements by exhibiting a bijection (one-to-one correspondence) between them. This is a subject which requires little mathematical background to reach the frontiers of current research. Students will therefore have the opportunity to do original research.

Every week, the first session is for lectures on different techniques and results related to bijective proofs. Problems of varying levels of difficulty (some unsolved as the course progresses) related to the lecture will be passed out on the first session. In every second session, students will report on their work on the problems. All students must participate in this process. "Reasonable" collaboration on problem sets is permitted, but you shouldn't simply copy someone else's solution or a solution from an outside source.

There will be no text required for the course. All material will be based on the handouts. There is currently one book in print devoted solely to bijective proofs:

Stanton, D., and D. E. White. Constructive Combinatorics. This book is rather sophisticated.

A more elementary book by A. T. Benjamin, and J. J. Quinn, Proofs That Really Count, will soon be published, but it is not yet available.

Don't show me this again

This is one of over 2,200 courses on OCW. Find materials for this course in the pages linked along the left.

MIT OpenCourseWare is a free & open publication of material from thousands of MIT courses, covering the entire MIT curriculum.

No enrollment or registration. Freely browse and use OCW materials at your own pace. There's no signup, and no start or end dates.

Knowledge is your reward. Use OCW to guide your own life-long learning, or to teach others. We don't offer credit or certification for using OCW.

Made for sharing. Download files for later. Send to friends and colleagues. Modify, remix, and reuse (just remember to cite OCW as the source.)

Learn more at Get Started with MIT OpenCourseWare