Lecture Overview

Introduction to Combinatorics, specifically today I talk about enumerative combinatorics. This is MCS 421.

Combinatorics is the study of the existence and enumeration of finite structures.

• How many games must \(n\) teams play if each team played every other team?
• How many hands in poker are a full house? How many if some of the cards in the hand are already known?
• How many rooks can be put onto a chessboard so that no two rooks are attacking each other?
• In an election where candidate A receives \(p\) votes and candidate B receives \(q\) votes with \(p > q\), what is the probability that A will be strictly ahead of B throughout the count?
• How many ways are there to place \(2\) by \(1\) domino pieces on a chessboard so that every square of the chessboard is filled?
• How many colors are needed to color each country on a map so that no two bordering countries receive the same color?
• Given 36 officers of 6 ranks and 6 regiments, can they be arranged in a 6 by 6 formation so that in each row and column there is one officer of each rank and one officer from each regiment?

Historically, combinatorial problems were studied purely for amusement or for their aesthetic appeal. Since the sixties, there has been a tremendous growth in combinatorics because of its application to computer science. Combinatorics is concerned with arrangements of the objects of a set into patterns satisfying specified rules. There are two major focuses:

• Existence of the arrangement: If one wants to arrange the objects of a set so that certain conditions are fulfilled, it may not be at all obvious that such an arrangement exists (e.g. the 36 officer problem from the 1700s). If the arrangement does not always exist, under what extra conditions can it be achieved?
• Enumeration or classification of the arrangements: If an arrangement is possible, how many are there and can you classify them into types.

In combinatorics, we build up tools to help answer questions of this type. Here are a few of the most basic.

• \(n!\) (in words n factorial) is the number of ways of ordering \(n\) things.
• \(\binom{n}{k}\) (in words binomial coefficient) is the number of ways of picking \(k\) things out of a set of \(n\) things.
• Pigeonhole principle

Here are a few examples

• Example: Committee-Chair identity: \(k\binom{n}{k}\) = \(n\binom{n-1}{k-1}\). Both are the number of ways of picking a committee of size \(k\) from \(n\) people, where one of the members is identified as the chair.
• Example: Betrand's ballot problem
• Example: Rooks problem

Sometimes it is not clear how these problems actually have applications. For example, the 36-officers problem (and its extensions where \(6\) is replaced by higher numbers called block designs) has important applications in designing statistical experiments. Other applications come from analysis of algorithms. For example, you want to determine the probability that an input to an algorithm will cause some specific if branch to be taken (e.g. because the if branch is really long and will impact the runtime). Probability (of finite things) is just counting, so we want to count how many of the inputs to the algorithm cause the if branch to be taken. This is exactly counting things under some restriction, and the tools developed for e.g. the rook problem also apply to analyzing the algorithm. (Both are counting some stuff under some given restrictions.)

Exercises

• Count the subsets of \(\{1,2,\dots,n\}\) that contain at least one odd number.

• Chicago has around 9 million residents. Suppose that each resident has 100 coins in a jar. The coins come in five types (pennies, nickels, dimes, quarters, half-dollars). Two jars are equivalent if they have the same number of coins of each type. Is it possible that no two people have equivalent jars? (It is possible to answer this with pencil and paper only, but you could also try writing a short python program.)