Teacher resources and professional development across the curriculum

Teacher professional development and classroom resources across the curriculum

# Unit 2

## Combinatorics Counts

Rhyind Papyrus

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

• 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.

# Video Transcript

Counting things seems so simple. Children do it intuitively, connecting a thing with fingers to say how many. Finding efficient and interesting ways to organize things and information is what the field of mathematics, known as Combinatorics, is all about.

# Textbook

Not only can combinatorics help to organize complicated sets, but it can also reveal whether or not any organization inherently exists in large, seemingly "random" sets.

# Interactive

Using combinatorics, this interactive looks at the ordering of DNA. You will create structure by building a directed graph and evaluating it in a mathematical way.