University of Connecticut

Course Info

MATH 3250: Combinatorics

Description: Combinatorics concerns itself with problems involving discrete structures, generally on finite or countably infinite sets. Often we want to count the number of ways something can be done: arranging 5 books on a shelf, partitioning a sports club into 5 disjoint teams, or dividing a polygon into triangles using diagonals which only intersect at a vertex. Sometimes we consider the relationships among such objects, and the discrete structures involved, yielding graphs (imagine an airline route map that connects some pairs of cities, but not all) or partially ordered sets. In all of these we look for elegant ways of understanding and proving our answers are correct, avoiding simpleminded brute-force computations. This course will give an overview of combinatorial techniques and applications. We will count things using basic principles of arithmetic, using infinite series, and using bijections that help us translate objects we want to count into a different form that is easier to count. We will see surprisingly deep applications of the obvious Pigeonhole Principle. This course is an excellent way for students to strengthen their proof writing in contexts which are more easily accessible and concrete than many other areas of mathematics. These ideas come up frequently in other areas of mathematics in computer science, and in parts of chemistry and biology.

Prerequisites: A grade of C or better in MATH 2142 or 2710.

Offered: Spring

Credits: 3

Sections: Fall 2017 on Storrs Campus