Introduction to Combinatorics, 2nd Edition

CHAPTER 1

BASIC COUNTING METHODS

We begin our tour of combinatorics by investigating elementary methods for counting finite sets. How many ways are there to choose a subset of a set? How many permutations of a set are there? We will explore these and other such questions.

1.1 The multiplication principle

We start with the simplest counting problems. Many of these problems are concerned with the number of ways in which certain choices can occur.

Here is a useful counting principle: If one choice can be made in x ways and another choice in y ways, and the two choices are independent, then the two choices together can be made in xy ways. This rule is called the “multiplication principle.”

EXAMPLE 1.1

Suppose that you have three hats and four scarves. How many different hat and scarf outfits can you choose?

Solution: By the multiplication principle, there are 3 · 4 = 12 different outfits. Let’s call the hats h₁, h₂, and h₃ and the scarves s₁, s₂, s₃, and s₄. Then we can list the different outfits as follows:

EXAMPLE 1.2

At the French restaurant Chacun à Son Got, there are three choices ...