2.4 Counting

2.4.1 Basic counting principles

The sum rule: If a first task can be done in n₁ ways and a second task can be done in n₂ ways, and if these tasks cannot be done at the same time, then there are n₁ + n₂ ways to do either task.

Example. Suppose that either a member of the mathematics faculty or a student who is a mathematics major is chosen as a representative to a university committee. How many different choices are there for this representative if there are 37 members of the mathematics faculty and 83 mathematics majors?

Solution: 37 + 83 = 120 possible ways to pick this representative.

We can extend the sum rule to more than two tasks. Suppose that the tasks can be done in ways, respectively, and no two of these tasks can be done at the same time. Then the number of ways to do one of these tasks is .

Example. A student can choose a computer project from one of three lists. The three lists contain 23, 15 and 19 possible projects, respectively. How many possible projects are there to choose from these lists?

Solution: 23 + 15 + 19 = 57 projects.

The product rule: Suppose that a procedure can be broken down into two tasks. If there are n₁ ways to do the first task and n₂ ways to do the second task after the first task has been done, then there are n₁n₂ ways to do the procedure.

Example. The chairs of an auditorium are to be labeled with a letter and a positive integer not exceeding 100. What is the largest number of chairs that can be labeled differently?

Solution: The procedure of labeling a chair consists of two tasks, namely, assigning one of the 26 letters and then assigning one of the 100 possible integers to the seat. The product rule shows that there are 26 ∙ 100 = 2600 different ways that a chair can be labeled. Therefore, the largest number of chairs that can be labeled differently is 2600.

An extended version of the product rule is often useful. Suppose that a procedure is carried out by performing the tasks . If task T_i can be done in n_i ways after tasks have be done, then there are ways to carry out the procedure.

2.4.2 The inclusion-exclusion principle

When two tasks can be done at the same time, we cannot use the sum rule to count the number of ways to do one of the two tasks. Adding the number of ways to do each task leads to an over count, since the ways to do both tasks are counted twice. To correctly count the number of ways to do one of the two tasks, we add the number of ways to do each of the two tasks and then subtract the number of ways to do both tasks. This technique is called the principle of inclusion-exclusion.

Example: How many bit strings of length eight either start with a 1 bit or end with the two bits 00?

Solution: The first task, constructing a bit string of length eight beginning with a 1 bit, can be done in 2⁷ = 128 ways. This follows by the product rule, since the first bit can be chosen in only one way and each of the other seven bits can be chosen in two ways. The second task, constructing a bit string of length eight ending with the two bits 00, can be done in 2⁶ = 64 ways. Both tasks, constructing a bit string of length eight that begins with a 1 and ends with 00, can be done in 2⁵ = 32 ways. Consequently, by the principle of inclusion-exclusion we have 128 + 64 – 32 = 160.

2.4.3 The Pigeonhole Principle

Theorem 1 (The Pigeonhole Principle). If k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.

Proof: Suppose that none of the k boxes contains more than one object. Then the total number of objects would be at most k. This is a contradiction, since there are at least k + 1 objects.

The pigeonhole principle is also called the Dirichlet Drawer principle.

Example. Among any group of 367 people, there must be at least two with the same birthday, because there are only 366 possible birthdays.

Solution: There are 101 possible scores on the final. The pigeonhole principle shows that among any 102 students there must be at least 2 students with the same score.

Theorem 2 (The generalized Pigeonhole principle). If N objects are placed into k boxes, then there is at least one box containing at least N/k objects.

Proof: Suppose that none of the boxes contains more than N/k – 1 objects. Then, the total number of objects is at most k( N/k – 1) < k(((N/k) + 1) – 1) = N, where the inequality N/k < (N/k) + 1 has been used. This is a contradiction, since there a total of N objects.

Example. Among 100 people there are at least 100/12 = 9 who were born in the same month.

Example. What is the minimum number of students required in a discrete mathematics class to be sure that at least six will receive the same grade, if there are five possible grades, A, B, C, D and F?

Solution: The minimum number of students needed to guarantee that at least six students receive the same grade is the smallest integer N such that N/5 = 6. The smallest such integer is N = 5 ∙ 5 + 1 = 26. Thus, 26 is the minimum number of students needed to be sure that at least 6 students will receive the same grade.

Theorem 3. Every sequence of n² + 1 distinct real numbers contains a subsequence of length n + 1 that is either strictly increasing or strictly decreasing.

Example. The sequence 8, 11, 9, 1, 4, 6, 12, 10, 5, 7 contains 10 terms. Note that 10 = 3² + 1. There are four increasing subsequences of length four, namely, 1, 4, 6, 12; 1, 4, 6, 7; 1, 4, 6, 10 and 1, 4, 5, 7. There is also a decreasing subsequence of length four, namely, 11, 9, 6, 5.

Proof of Theorem 3: Let be a sequence of n² + 1 distinct real numbers. Associate ordered pair with each term of the sequence, namely, associate to the term a_k, where i_k is the length of the longest increasing subsequence starting at a_k, and d_k is the length of the longest decreasing subsequence starting at a_k.

Suppose that there are no increasing or decreasing subsequences of length n + 1. Then i_k and d_k are both positive integers less than or equal to n, for k = 1, 2, ..., n² + 1. Hence, by the product rule there are n² possible ordered pairs for . By the pigeonhole principle, two of these n² + 1 ordered pairs are equal. In other words, there exist terms a_s and a_t, with s < t such that i_s = i_t and d_s = d_t. We will show that this is impossible. Because the terms of the sequence are distinct, either a_s < a_t or a_s > a_t. If a_s < a_t, then, since i_s = i_t, an increasing subsequence of length i_t + 1 can be built starting at a_s, by taking a_s followed by an increasing subsequence of length i_t beginning at a_t. This is a contradiction. Similarly, if a_s > a_t, it can be shown that d_s must be greater than d_t, which is a contradiction.

The final example shows how the generalized pigeonhole principle can be applied to an important part of combinatorics called Ramsey theory. In general, Ramsey theory deals with the distribution of subsets of elements of sets.

2.4.4 Permutations

A permutation of a set of distinct objects is an ordered arrangement of these objects.

An ordered arrangement of r elements of a set is called an r-permutation.

Example. Let S = {1, 2, 3}. The arrangement 3, 1, 2 is a permutation of S. The arrangement 3, 2 is a 2-permutation of S.

The number of r-permutations of a set with n elements is denoted by P(n, r).

Theorem 1. The number of r-permutations of a set with n distinct elements is

Proof: The first element of the permutation can be chosen in n ways, since there are n elements in the set. There are n – 1 ways to choose the second element of the permutation, since there are n – 1 elements left in the set after using the element picked for the first position. Similarly, there are n – 2 ways to choose the third element, and so on, until there are exactly n – r + 1 ways to choose the r^th element. Consequently, by the product rule, there are r-permutations of the set.

;

Example. How many different ways are there to select 4 different players from 10 players on a team to play four tennis matches, where the matches are ordered?

Solution: The answer is given by the number of 4-permutations of a set with 10 elements. By Theorem 1, this is P(10, 4) = 10  9  8  7 = 5040.

2.4.5 Combinations

An r-combination of elements of a set is an unordered selection of r elements from the set. Thus, an r-combination is simply a subset of the set with r elements.

Example. Let S be the set {1, 2, 3, 4}. Then {1, 3, 4} is a 3-combination from S.

The number of r-combinations of a set with n distinct elements is denoted by C(n, r).

Example. We see that C(4, 2) = 6, since the 2-combinations of {a, b, c, d} are the six subsets {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, and {c, d}.

We can determine the number of r-combinations of a set with n elements using the formula for the number of r-permutations of a set. To do this, note that the r-permutations of a set can be obtained by first forming r-combinations and then ordering the elements in these combinations.

Theorem 2. The number of r-combinations of a set with n elements, where n is a positive integer and r is an integer with , equals .

Proof: The r-permutations of the set can be obtained by forming the C(n, r) r-combinations of the set, and then ordering the elements in each r-combination, which can be done in P(r, r) ways. Consequently, This implies that

.

Corollary 1. Let n and r be nonnegative integers with . Then .

There is another common notation for the number of r-combinations from a set with n elements, namely, , i.e. . This number is also called a binomial coefficient. The name “binomial coefficient” is used because these numbers occur as coefficients in the expansion of powers of binomial expressions such as .

Example. How many ways are there to select 5 players from a 10-member tennis team to make a trip to a match at another school?

Solution: The answer is given by the number of 5-combinations of a set with 10 elements:

2.4.6 The binomial theorem

The binomial theorem gives the coefficients of the expansion of powers of binomial expressions. A binomial expression is simply the sum of two terms, such as x + y.

Example. The expansion of can be found using combinatorial reasoning instead of multiplying the three terms out. When is expanded, all products of a term in the first sum, a term in the second sum, and a term in the third sum added. Terms of the form x³, x²y, xy², and y³ arise. To obtain a term of the form x³, an x must be chosen in each of the sums, and this can be done in only one way. Thus, the x³ term in the product has a coefficient of 1. To obtain a term of the form x²y, an x must be chosen in two of the three sums (and consequently a y in the other sum). Hence, the number of such terms is the number of 2-combinations of three objects, namely C(3, 2). Similarly, the number of terms of the form xy² is the number of ways to pick one of the three sums to obtain an x (and consequently take a y from each of other two terms). This can be done in C(3, 1) ways. Finally, the only way to obtain a y³ term is to choose the y for each of the three sums in the product, and this can be done in exactly one way. Consequently, it follows that

Theorem 3 (the binomial theorem). Let x and y be variables, and let n be a positive integer. Then

Proof: The terms in the product when it is expanded are of the form for To count the number of terms of the form , note that to obtain such a term it is necessary to choose n – j xs from the n sums (so that the other j terms in the product are ys). Therefore, the coefficient of is

Example. What is the expansion of ?

Solution:

.

2.4.7 Permutations with repetition

Theorem 4. The number of r-permutations of a set of n objects with repetition allowed is n^r.

Proof: There are n ways to select an element of the set for each of the r positions in the r-permutation when repetition is allowed, since for each choice all n objects are available. Hence, by the product rule there are n^r r-permutations when repetition is allowed.

2.4.8 Combinations with repetition

Theorem 5. There are C(n + r – 1, r) r-combinations from a set with n elements when repetition of elements is allowed.

Proof: Each r-combination of a set with n elements when repetition is allowed can be represented by a list of n – 1 bars and r stars. The n – 1 bars are used to mark off n different cells, with the i^th cell containing a star for each time the i^th element of the set occurs in the combination. For instance, a 6-combination of a set with four elements is represented with three bars and six stars.

Here * * | * | | * * * represents the combination containing exactly two of the first element, one of the second element, none of the third element, and three of the fourth element of the set.

As we have seen, each different list containing n – 1 bars and r stars corresponds to an r-combination of the set with n elements, when repetition is allowed. The number of such lists is C(n – 1 + r, r), since each list corresponds to a choice of the r positions to place the r stars from the n – 1 + r positions that contain r stars and n – 1 bars.

Example. Suppose that a cookie shop has four different kinds of cookies. How many different ways can six cookies be chosen? Assume that only the type of cookie, and not the individual cookies or the order in which they are chosen, matters.

Solution: The number of ways to choose six cookies is the number of 6-combinations of a set with four elements. From Theorem 5 this equals C(4 + 6 – 1, 6) = C(9, 6). Since C(9, 6) = 84, there are 84 different ways to choose the six cookies.

2.4.9. Permutations of sets with indistinguishable objects

Example. How many different strings can be made by reordering the letters of the word SUCCESS?

Solution: Because some of the letters of SUCCESS are the same, the answer is not given by the number of permutations of seven letters. This word contains three Ss, two Cs, one U, and one E. To determine the number of different strings that can be made by reordering the letters, first note that the three Ss can be placed among the seven positions in C(7, 3) different ways, leaving four positions free. Then the two Cs can be placed in C(4, 2) ways, leaving two free positions. The U can be placed in C(2, 1) ways, leaving just one position free. Hence E can be placed in C(1, 1) way. Consequently, from the product rule, the number of different strings that can be made is

.

Theorem 6. The number of different permutations of n objects, where there are n₁ indistinguishable objects of type 1, n₂ indistinguishable objects of type 2, …, and n_k indistinguishable objects of type k, is .