MATH BC2006
Combinatorics
Spring 2021

http://www.math.columbia.edu/~bayer/S21/Combinatorics

Tuesdays and Thursdays, 10:10am - 11:25am ET
Zoom meeting

Dave Bayer
Email
Office Hours

Directory of Classes | Spring 2021 Mathematics | MATH BC2006
CourseWorks
Student Services Online

Content

This is an introductory course in combinatorics, with a focus on counting problems. As there are many methods that have been developed in calculus and analysis for measuring continuous quantities, there are also many methods that have been developed in combinatorics for counting finite sets. We will survey these methods, with a focus on problem solving.

Exams

Course grades will be determined by two exams and a final:

• Exam 1 (30 points), February 11-14
• Exam 2 (30 points), March 18-21
• Final (30 points), April 20-23

Makeup exams will only be given under exceptional circumstances.

The two exams and our final will be take-home, to be submitted as PDF files through our CourseWorks Assignments tab. You will have Thursday through Sunday to complete each exam, with a one day grace period. You will have Tuesday through Friday to complete our final, with a two day grace period. The exams will be open-book, but you are to work alone. All resources on my web site will be available.

Textbooks

Our textbooks are available freely online to Columbia University affiliates, mostly through SpringerLink.

These books overlap in content, with varying styles and levels. As we study each topic, please work with the book(s) that you prefer.

How to choose? This is personal. For me, books that are too low level think that talking too much makes math easier. That isn’t my experience.

On the other hand, books that are too high level can be hard to read. The sweet spot for me is a book that is considered high level because of its depth, but is extraordinarily clear with no wasted words. Go in with purpose, knowing what you’re looking for. This is why one learns faster in grad school than as an undergraduate; one reads with a shopping list. From this perspective, Aigner is a gem:

• 2007 Aigner - A Course in Enumeration

The following are good introductory expositions:

• 1983 Pólya, Tarjan, Woods - Notes on Elementary Combinatorics
• 1994 Graham, Knuth, Patashnik - Concrete mathematics (not available for download)
• 2001 Martin - Counting: The art of enumerative combinatorics
• 2003 Lovasz, Pelikan, Vesztergombi - Discrete mathematics
• 2011 Camina, Lewis - An introduction to enumeration
• 2015 Beeler - How to count
• 2015 Roman - An Introduction to Catalan Numbers
• 2015 Petersen - Eulerian numbers
• 2016 Mariconda, Tonolo - Discrete calculus

The following are also of interest, but don’t match our syllabus as closely:

• 1994 Wilf - generatingfunctionology
• 2004 Andreescu, Feng - A path to combinatorics for undergraduates
• 2010 Soifer - Geometric Etudes in Combinatorial Mathematics
• 2013 Soberon - Problem-Solving Methods in Combinatorics
• 2013 de Longueville - A course in topological combinatorics
• 2018 Aigner, Ziegler - Proofs from The Book

For the curious, here is the definitive graduate text on enumeration:

• 2011 Stanley - Enumerative Combinatorics Volume 1, second edition

The On-Line Encyclopedia of Integer Sequences

• The On-Line Encyclopedia of Integer Sequences

This is a fantastic resource. Has anyone else seen before the sequence of integers that you’re studying? This is “Google” for counting problems.

Previous semesters

One can find old exam solutions, and other useful resources, in my past course web pages:

• Spring 2016 Combinatorics
• Spring 2015 Combinatorics
• Spring 2014 Combinatorics
• Fall 2011 Combinatorics
• Fall 2000 Combinatorics

I have also lead undergraduate seminars on this topic, in several recent years:

• Spring 2019 Seminar
• Spring 2018 Seminar
• Spring 2017 Seminar

Calendar

This calendar gives our schedule of classes and exams. The links are to a guide for that week of classes:

source links validate