## Combinatorics: Why Counting Counts, or How to Count Without Counting

### Course enrollment will be available for this course once it is scheduled.

View related courses »

### Course Description

Imagine putting a random group of people in a room: how many do you need so the probability that two of them have the same birthday is at least one half? Something like 182 or about 365/2, right? Wrong! In fact, the probability is already greater than one half with a random collection of only 23 people! At its core, this is a question about counting; in this course, we study the organized mathematical approach to counting called combinatorics and explore how potentially counter intuitive facts pervade areas of science and mathematics.

In the first week, we will discover fundamental techniques and theory of combinatorics--the inclusion-exclusion principle, permutations, and combinations--through problem solving. Starting with questions as simple as "how many ways can five people arrange themselves in a line?", we will make our way to more subtle and sophisticated questions, some of which have challenged the great minds of past centuries.

In the second week, we will broaden our horizons and examine ways combinatorics has contributed to mathematics, the sciences, and popular culture. We will take a brief tour through probability to reveal the mathematical underpinnings of some astonishing card tricks as well as card games such as poker and blackjack. We will discuss applications of combinatorics to other areas of science; in particular, we will discuss error-correcting codes invented by the computer scientist Hamming. We will also discuss combinatorial problems that have made their way into popular culture. One example is the Monty Hall controversy, which originated from the television show Let's Make a Deal. Its essence is the following: you are faced with three boxes; two are empty, but the third contains a thousand dollars. After picking one, the game host, who knows which box contains the money, opens a box that is empty. You are then offered the opportunity to switch boxes - should you?

During the course, students will learn about methods of mathematical proof. If you have been bored or frustrated by math because of repetitious, formulaic, and unmotivated material, this may be the right course for you. The landscape of combinatorics is a dense jungle and each problem has many paths to a valid solution. True knowledge is gained only by careful argument and deliberation--for this reason, lively discussion and argument among the students will be encouraged.

In science and mathematics, being able to ask the right questions is arguably as important as being able to answer them. In this course, students will hone both skills through group discussions, individual work, and presentations. We will largely eschew the standard lecture model and will in many cases allow students' own findings to influence the pace of the course.

Familiarity with Algebra I is recommended, but NOT required. More important is intellectual curiosity and creativity. In fact, I encourage you to take this course even if you have not enjoyed math in the past.