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 h1, h2, and h3 and the scarves s1, s2, s3, and s4. Then we can list the different outfits as follows:

EXAMPLE 1.2

At the French restaurant Chacun à Son Got, there are three choices for the appetizer, four choices for the entrée, and five choices for the dessert. How many different dinner orders (consisting of appetizer, entrée, and dessert) can we make?

Solution: The answer is 3 · 4 · 5 = 60, and it isn’t difficult to list all the possibilities. Let’s call the appetizers a1, a2, and a3, the entrées e1, e2, e3, and e4, and the desserts d1, d2, d3, d4, and d5. Then the different possible dinners are as follows:

EXAMPLE 1.3

A variable name in a certain computer programming language consists of a letter (A through Z), a letter followed by another letter, or a letter followed by a digit (0 through 9). How many different variable names are possible?

Solution: There are 26 variable names consisting of a single letter, 262 variable names consisting of two letters, and 26 · 10 variable names consisting of a letter followed by a digit. Altogether, there are

variable names.

EXAMPLE 1.4 Number of binary strings

How many binary strings of length n are there?

Solution: There are two choices (0 or 1) for each element in the string. Hence, there are 2n possible strings.

For instance, there are 23 = 8 binary strings of lenght 3:

EXAMPLE 1.5 Number of subsets of a set

Let S be a set of n elements. How many subsets does S have?

Solution: There are two choices for each element of S; it can be in the subset or not in the subset. This means that there are 2n subsets altogether.

For instance, let S = {a, b, c}, so that n = 3. Then S has 23 = 8 subsets:

EXERCISES

1.2 Permutations

One of the fundamental concepts of counting is that of a permutation. A permutation of a set is an ordering of the elements of the set.

EXAMPLE 1.6

List the permutations of the set {a, b, c}.

Solution: There are six permutations:

We set

(1.1)

The expression n! is called n factorial.

We see in the above example that the number of permutations is 6 = 3!.

There are n! permutations of an n-element set. The reason is there are n choices for the first element in the permutation. Once that choice is made, there are n – 1 choices for the second element, and then n – 2 choices for the third element, and so on. Altogether, there are

choices, which is n!

EXAMPLE 1.7

In how many ways can the letters of the word MISSISSIPPI be arranged?

Solution: This is an example of a permutation of a set with repeated elements. There are 11! permutations of the 11 letters of MISSISSIPPI, but there is much duplication.

We need to divide by the number of permutations of the four I’s, the four S’s, the two P’s, and the one M. Thus, the number of different arrangements of the letters is

Let S be an n-element set, where n ≥ 0. How many permutations of k elements of S are there, where 1 ≤ k ≤ n? There are n choices for the first element, n − 1 choices for the second element,…,n – k + 1 choices for the kth element. Hence, there are

choices altogether. This expression, denoted P(n, k), may be written as

(1.2)

(Notice that we now allow k = 0, which gives P(n, 0) = 1.) We can interpret this formula as a MISSISSIPPI-type problem. The selected elements may be denoted X1,…,Xk, and the nonselected elements all denoted with the letter N (for nonselected).

EXAMPLE 1.8

An organization has 100 members. How many ways may they select a president, a vice-president, a secretary, and a treasurer?

Solution: The number of ways to select a permutation of four people from a group of 100 is

EXERCISES

1.3 Combinations

Another fundamental concept of counting is that of a combination. A combination from a set is an unordered subset (of a given size) of the set.

For convenience, we sometimes refer to an n-element set as an n-set and a k-element subset as a k-subset. Also, we use the notation N = {1, 2, 3,…,} and Nm = {1, 2, 3,…,m}.

Let S be an n-set, where n ≥ 0. How many k-subsets of S are there, where 0 ≤ k ≤ n? We can regard this as a MISSISSIPPI-type problem, i.e., a problem of permutations with repeated elements. Let X denote selected elements and N denote nonselected elements. Then the number of combinations is the number of arrangements of k X’s and n – k N’s, since each such arrangement specifies a combination.

Hence, the number of combinations, denoted C(n, k), is given by

(1.3)

We call this expression “n choose k.” We set C(n, k) = 0 for k < 0 and k > n.

For example, with n = 5 and k = 3, we have C(5, 3) = 5!/(3!2!) = 10 combinations of three elements from the set S = {a, b, c, d, e}, as shown below with the corresponding arrangements of X’s and N’s:

The values of...