Counting is an act of organization, a listing of a collection of things in an orderly fashion. Sometimes it's easy; for instance counting people in a room. But listing all the possible seating arrangements of those people around a circular table is more challenging. This unit looks at combinatorics, the mathematics of counting complicated configurations. In an age in which the organization of bits and bytes of data is of paramount importance—as with the human genome—combinatorics is essential.

Unit Goals

• Combinatorics is about organization.
• Many combinatorial problems involve ways to enumerate, or count, various things in an efficient manner.
• The counting function C(n,k), is a powerful tool used to count subsets of a larger set, or give coefficients in binomial expansions.
• Bijection—the identification of a "one-to-one" correspondence—enables us to enumerate a set that may be difficult to count in terms of another set that is more easily counted.
• Pascal's Triangle is an elegant illustration of the counting function C(n,k).
• Techniques from graph theory can help with combinatorial challenges such as finding circular permutations.
• The pigeonhole principle—the idea that if you have more pigeons than holes, some holes must have more than one pigeon—is a deceptively simple idea that can be used to prove startling results.
• Ramsey Theory explains why we sometimes find order in supposed randomness.
• Ideas from combinatorics are at play in modern methods of DNA sequencing.
• The question of whether or not P = NP—whether certain types of seemingly computationally intractable combinatorial problems can be solved in reasonable amounts of time—is at the forefront of current research in both combinatorics and computer science.