Massachusetts Institute of Technology Lecture 15 6.042J/18.062J: Mathematics for Computer Science October 31, 2000 Professors Nancy Lynch and Srinivas Devadas

Basic Counting

Topics for today:

• Rules for unions

• Rules for products

• Tree diagrams

• Permutations

Reading: Rosen 4.1, 4.3, 5.4

We continue studying the problem of finding the cardinality of a finite set. We saw one way to determine the number of elements in a finite set S last week. Namely, if there is a bijection between S and some set T of known cardinality, then we can conclude that S has the same number of elements as T. But constructing a bijection and proving that it works is painful. In this lecture, we will develop several systematic methods for determining the cardinality of a finite set.

First a note. When we say that |A| = n, we are actually saying that there is a bijection from |A| to the set of numbers {1, …, n}. That is, bijections define sizes of sets. All the counting rules below can be proven by setting up appropriate bijections.

1 The Cardinality of a Union of Sets

Suppose that we know the sizes of some sets A_{1}, A_{2}, … A_{n}. How many elements are in the union? If the sets are disjoint, then the size of the union is given by the simple Sum Rule. If the sets are not necessarily disjoint, then the size is given by the more general, but more complicated Inclusion-Exclusion Principle.

1.1 The Sum Rule

Theorem 1.1 (Sum Rule) If A_{1}, A_{2}, … A_{n} are disjoint sets, then:

|A_{1} ∪ A_{2} ∪ … ∪ A_{n}| = |A_{1}| + |A_{2}| + … + |A_{n}|

The Sum Rule says that the number of elements in a union of disjoint sets is equal to the sum of the sizes of all the sets. The Sum Rule can be proved by induction on the number of sets.

Proof. We leave the induction to the reader. Just to illustrate what’s going on, I’ll prove the two-set case. This will show that it all comes down to bijections.

Suppose |A_{1}| = n and |A_{2}| = m. We want to show |A_{1}| + |A_{2}| = n + m. By definition there is a bijection f : {1, …, n} → A_{1} and a bijection g : {1, …, m} → A_{2}. We need to exhibit a bijection h : {1, …, n + m} → A_{1} ∪ A_{2}. A good one is

h(x) = \begin{cases}f(x) & if x ≤ n \\ g(x − n) & if x > n \end{cases}

This can be shown to be a bijection in the usual way: injection and surjection. Note that the disjointness of A_{1} and A_{2} is necessary for us to argue injectivity.

As an example of the use of the Sum Rule, suppose that MIT graduates 60 majors in math, 200 majors in EECS, and 40 majors in physics. How many students graduate from MIT in these three departments? Let A_{1} be the set of math majors, A_{2} be the set of EECS majors, and A_{3} be the set of physics majors. The set of graduating students in these three departments is A_{1} ∪ A_{2} ∪ A_{3}. Assume for now that these sets are disjoint; that is, there are no double or triple majors. Then we can apply the Sum Rule to determine the total number of graduating students.

|A_{1} ∪ A_{2} ∪ A_{3}| = |A_{1}| + |A_{2}| + |A_{3}|
= 60 + 200 + 40
= 300

1.2 Inclusion-Exclusion Principle (special cases)

The Sum Rule gives the cardinality of a union of disjoint sets. The Inclusion-Exclusion Principle gives the cardinality of a union of sets that may intersect. The Inclusion-Exclusion Principle for n sets is messy to write down, so we’ll start with the simple special cases n = 2 and n = 3.

Theorem 1.2 (Inclusion-Exclusion Principle for 2 sets) Let A and B be sets, not necessarily disjoint.

|A ∪ B| = |A| + |B| − |A ∩ B|

Proof. Items in the intersection of A and B are counted twice in |A| + |B|. Therefore, by subtracting |A ∩ B|, every element is counted once overall.

Theorem 1.3 (Inclusion-Exclusion Principle for 3 sets) Let A, B, and C be sets, not necessarily disjoint.

|A ∪ B ∪ C| = |A| + |B| + |C|
− |A ∩ B| − |A ∩ C| − |B ∩ C|
+ |A ∩ B ∩ C|

Though this formula contains many terms, the general pattern is easy to remember: add the sizes of individual sets (first line), subtract intersections of pairs of sets (second line), and add the intersection of all three sets (third line).

Proof. Items contained in just one of the sets A, B, or C are counted once on the first line. Since these items are not contained in any intersection of sets, they are not subtracted away on the second line or counted again on the third line. In total, these items are counted just once.

Items contained in two of the sets A, B, and C are counted twice on the first line, subtracted away once on the second line, and not counted again on the third line. Again, in total, these items are counted just once.

Items contained in all three sets A, B, and C are counted three times on the first line, subtracted away three times on the second line, and added back once on the third line. Since 3 − 3 + 1 = 1, these items are also counted just once overall.

The name “Inclusion-Exclusion” comes from the way items are counted, subtracted away, counted again, etc.

Earlier we applied the Sum Rule to count MIT graduates in math, EECS, and physics, assuming that there were no double or triple majors. Using Inclusion-Exclusion, we can count the number of graduates even if some people have multiple majors. (After all, this is MIT, where some students even have 4 majors...) Suppose the numbers are as follows:

60 math majors  (|A| = 60)
200 EECS majors  (|B| = 200)
40 physics majors  (|C| = 40)
10 math/EECS double majors (|A ∩ B| = 10)
4 math/physics double majors (|A ∩ C| = 4)
15 EECS/physics double majors (|B ∩ C| = 15)
2 triple majors  (|A ∩ B ∩ C| = 2)

We can compute the total number of graduates, |A∪B∪C|, by plugging numbers into the Inclusion-Exclusion formula:

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
= 60 + 200 + 40 − 10 − 4 − 15 + 2
= 273

1.3 Inclusion-Exclusion Principle (general case)

Here is the nasty Inclusion-Exclusion formula for n sets. The formula is given both in words and in symbols. The word version is the one to remember, but look over the symbolic version to make sure that you really know what the theorem says.

Theorem 1.4 (Inclusion-Exclusion for n sets) Let A_{1}, A_{2}, …, A_{n} be sets, not necessarily disjoint. The cardinality of the union is computed as follows: add the sizes of all individual sets subtract the sizes of all two-way intersection add the sizes of all three-way intersections subtract the sizes of all four-way intersections add the sizes of all five-way intersections etc.

Restated in symbols, the cardinality of the union is:

|A_{1} ∪ A_{2} ∪ … ∪ A_{n}| = ∑_{1≤i≤n} |A_{i}|

− ∑_{1≤i<j≤n} |A_{i} ∩ A_{j}|

+ ∑_{1≤i<j<k≤n} |A_{i} ∩ A_{j} ∩ A_{k}|

… + (−1)^{n+1}|A_{1} ∩ A_{2} ∩ … ∩ A_{n}|

= ∑_{k=1}^{n}(−1)^{k+1} ( ∑_{S⊆[1,n],|S|=k} | ⋂_{i∈S} A_{i}|)

We won’t give the complete proof, which is messy, but observe that it can be done by induction. Here is the inductive step, going from n to n + 1:

|A_{1} ∪ A_{2} ⋯ ∪ A_{n+1}| = |A_{1} ∪ ⋯ ∪ A_{n}| + |A_{n+1}| − |(A_{1} ∪ ⋯ ∪ A_{n}) ∩ A_{n+1}|
= |A_{1} ∪ ⋯ ∪ A_{n}| + |A_{n+1}| − |(A_{1} ∩ A_{n+1}) ∪ (A_{2} ∩ A_{n+1}) ∪ ⋯ ∪ (A_{n} ∩ A_{n+1})|

where we are applying the distributive law for intersection over union to get the last line. The last line involves two groups of n sets each, so we can apply the inductive hypothesis to count them. Then terms must be collected,...

There is a different, slick proof that can be derived once we learn about binomial coefficients (next week).

1.4 Counting Primes

How many of the numbers 1, 2, …, 100 are prime? One way to answer this question is to test each number up to 100 for primality and keep a count. This requires considerable effort. (Is 57 prime? How about 67?)

Another approach is to use the Inclusion-Exclusion Principle. This requires one trick: to determine the number of primes, we will first count the number of non-primes. We can then find the number of primes by subtraction. We will use this trick of “counting the complement” several times in coming weeks.

Reducing the Problem to the Cardinality of a Union

The set of non-primes in the range 1, …, 100 consists of the set C of composite numbers in this range (4, 6, 8, 9, …, 99, 100) and the number 1, which is neither prime nor composite. The main job is to determine the size of the set C of composite numbers. For this purpose, define:

A_{p} = {x | 1 ≤ x ≤ 100, p | x, and x ≠ p}

In words, A_{p} is the set of numbers in the range 1, …, 100 that are divisible by p, but not equal to p. For example, A_{2} = {4, 6, 8, …, 100}.

Claim 1.5 C = A_{2} ∪ A_{3} ∪ A_{5} ∪ A_{7}

The claim explains the point of these funny A_{p} sets: we can write the set C of composite numbers as a union of them. We can compute the cardinality of the union using Inclusion-Exclusion, and this will tell us the number of composite numbers in the range 1, …, 100.

Proof. We prove the two sets equal by showing that each contains the other.

First, we show that A_{2} ∪ A_{3} ∪ A_{5} ∪ A_{7} ⊆ C. Let n be an element of A_{2} ∪ A_{3} ∪ A_{5} ∪ A_{7}. Then n ∈ A_{p} for p = 2, 3, 5 or 7. This implies that n is in the range 1, …, 100, n is divisible by p, and n is not equal to p. This implies that n is a composite in the range 1, …, 100, and so n ∈ C.

Second, we show that C ⊆ A_{2} ∪ A_{3} ∪ A_{5} ∪ A_{7}. Let n be an element of C. Then n is a composite number in the range 1, …, 100. This means that n has at least two prime factors p and q. One of these must be 2, 3, 5, or 7. (Otherwise, both p and q are at least 11, and so n ≥ pq ≥ 11·11 = 121, a contradiction.) This implies that n is an element of A_{2}, A_{3}, A_{5}, or A_{7}, and so n ∈ A_{2} ∪A_{3} ∪A_{5} ∪A_{7}.

Corollary 1.6 |C| = |A_{2} ∪ A_{3} ∪ A_{5} ∪ A_{7}|

Computing the Cardinality of the Union

We have reduced the problem of counting primes to a problem about the cardinality of a union of sets. Specifically, we must evaluate |A_{2} ∪ A_{3} ∪ A_{5} ∪ A_{7}|. This will give us the number of composites in the range 1, …, 100, and from this we can figure out the number of primes. As a stepping stone, we can compute the cardinality of each set A_{p}:

|A_{p}| = ⌊\frac{100}{p}⌋ − 1

The first term, ⌊\frac{100}{p}⌋, is the number of values in the range 1, …, 100 that are divisible by p. The second term, −1, arises because we defined A_{p} to exclude p itself. This formula gives:

|A_{2}| = ⌊\frac{100}{2}⌋ − 1 = 49
|A_{3}| = ⌊\frac{100}{3}⌋ − 1 = 32
|A_{5}| = ⌊\frac{100}{5}⌋ − 1 = 19
|A_{7}| = ⌊\frac{100}{7}⌋ − 1 = 13

Here is an erroneous way to compute the number of composites in the range 1 to 100.

|C| = |A_{2} ∪ A_{3} ∪ A_{5} ∪ A_{7}|
= |A_{2}| + |A_{3}| + |A_{5}| + |A_{7}|
= 49 + 32 + 19 + 13
= 113

In the first step, we applied the Sum Rule and the rest was substitution and simplification. The result is obviously wrong because there are only 100 numbers in the range 1 to 100! The problem is that the Sum Rule is inapplicable; the Sum Rule requires that the sets A_{2}, A_{3}, A_{5}, and A_{7} be disjoint. However, 6 is in both A_{2} and A_{3}, for example. Since the sets intersect, we must use the Inclusion-Exclusion Principle instead:

|C| = |A_{2} ∪ A_{3} ∪ A_{5} ∪ A_{7}|
= |A_{2}| + |A_{3}| + |A_{5}| + |A_{7}|
− |A_{2} ∩ A_{3}| − |A_{2} ∩ A_{5}| − |A_{2} ∩ A_{7}| − |A_{3} ∩ A_{5}| − |A_{3} ∩ A_{7}| − |A_{5} ∩ A_{7}|
+ |A_{2} ∩ A_{3} ∩ A_{5}| + |A_{2} ∩ A_{3} ∩ A_{7}| + |A_{2} ∩ A_{5} ∩ A_{7}| + |A_{3} ∩ A_{5} ∩ A_{7}|
− |A_{2} ∩ A_{3} ∩ A_{5} ∩ A_{7}|

There are a lot of terms here! Fortunately, all of them are easy to evaluate. For example, |A_{3} ∩ A_{7}| is the number of multiples of 3 · 7 = 21 in the range 1 to 100, which is ⌊\frac{100}{21}⌋ = 4. (Note that there is no reason to subtract 1 as we did when evaluating |A_{p}| above.) Substituting values for all of the terms above gives:

|C| = 49 + 32 + 19 + 13

− 16 − 10 − 7 − 6 − 4 − 2 + 3 + 2 + 1 + 0 − 0

= 74

This calculation shows that there are 74 composite numbers in the range 1 to 100. Since the number 1 is neither composite nor prime, there are 100 − 74 − 1 = 25 primes in this range.

In retrospect, checking each number from 1 to 100 for primality and keeping a count of primes might have been easier! However, the Inclusion-Exclusion approach used here is asymptotically faster as the range of numbers grows large. The naive strategy requires N runs of a primality test if the upper bound is N. The Inclusion-Exclusion approach seems to require summing an immense number of terms, but fewer than N of these are non-zero and the rest can be ignored.

2 Products of Sets

Recall the definition of the Cartesian product of two sets:

A × B = {(a, b) | a ∈ A, b ∈ B}

For example, if A = {x, y, z} and B = {1, 2}, then A×B = {(x, 1), (y, 1), (z, 1), (x, 2), (y, 2), (z, 2)}. In this case, A contains three items, B contains two items, and the product contains 3·2 = 6 items. More generally, the size of a product of sets is given by the Product Rule:

Theorem 2.1 (Product Rule) If A_{1}, A_{2}, … A_{n} are sets, then:

|A_{1} × A_{2} × … × A_{n}| = |A_{1}| · |A_{2}| · . . . · |A_{n}|

The proof can be done by induction on n, but we leave it to the reader.

For intuition, consider the case where n = 2, and organize all the pairs in A_{1} ×A_{2} into a rectangular “grid”. The “area” of this grid is equal to the product of the lengths of the two sides.

Here is another way to look at the product rule: the number of ways to pick one item from A_{1}, 1 item from A_{2}, …, and 1 item from A_{n} is ∏_{i=1}^{n} |A_{i}|.

Four-Course Italian Meals

As an example of the Product Rule, suppose that an Italian restaurant menu lists 15 antipasti, 6 pastas, 10 main courses, and 4 desserts. How many four course-meals are possible? In this case, A_{1} is the set of antipasti, A_{2} is the sets of pastas, A_{3} is the set of main courses, and A_{4} is the set of desserts. The number of four-course meals is the number of ways of picking one item from each set. By the Product Rule this is:

|A_{1} × A_{2} × A_{3} × A_{4}| = |A_{1}| · |A_{2}| · |A_{3}| · |A_{4}|
= 15 · 6 · 10 · 4
= 3600

Binary Strings

How many n-bit binary strings are there? If we let B = {0, 1}, then the set of n-bit binary strings is:

\underbrace{B × B × … × B}_{n terms}

By the Product Rule, the number of binary strings is |B|^{n} = 2^{n}.

Telephone Numbers

How many telephone numbers are there? There are actually two formats for telephone numbers, an old one and a new one. The formats can be defined in terms of three sets of digits:

A = {0, 1, …, 9}
B = {2, 3, …, 9}
C = {0, 1}

The old format is (BCA) BBA − AAAA and the new format is (BAA) BAA − AAAA. This gives:

old numbers = |B| · |C| · |A| · |B| · |B| · |A| · |A| · |A| · |A| · |A|
= 2 · 8^{3} · 10^{6}
= 1.024 billion
new numbers = |B| · |A| · |A| · |B| · |A| · |A| · |A| · |A| · |A| · |A|
= 8^{2} · 10^{8}
= 6.4 billion

The reason for the new format is that there are more numbers. In particular, the number of area codes is increased from 8 · 2 · 10 = 160 to 8 · 10 · 10 = 800.

Passwords

Suppose that a password consists of 8 characters where each character is either a number or a lowercase letter. A password is legal if there is at least one number and at least one letter. How many legal passwords are there?

We can solve this problem by “counting the complement”. We used this method earlier to find the number of primes in the range 1 to 100 by counting the composites in this range. In this case, we can find the number of legal passwords by counting the illegal passwords. An illegal password has either all numbers or all letters. By the Product Rule, the number of passwords with all numbers is 10^{8}, and the number of passwords with all letters is 26^{8}. Also by the Product Rule, the total number of passwords (both legal and illegal) is 36^{8}. Therefore, the total number of legal passwords is 36^{8} − 26^{8} − 10^{8}.

3 Tree Diagrams

The Sum and Product Rules are both useful in counting the number of ways that something can be done. In more complicated problems, we need to combine these rules. In such cases, tree diagrams are helpful.

3.1 A Problem Getting Dressed

Suppose we have 3 blue shirts, 2 red shirts, and 1 green shirt. We also have 2 gray pants and 3 brown pants. How many outfits are possible? (Two pieces of clothing with the same color are still considered distinct; assume that they have slightly different shades.)

This problem is easier than it sounds. Let S be the set of shirts and P be the set of pants. We form an outfit by picking one shirt and one pair of pants. By the Product Rule, there are 6 · 5 = 30 outfits. All the color information is irrelevant.

However, suppose that gray pants “go with” only blue and red shirts and brown pants “go with” only green and red shirts. How many matching outfits are there?

One approach to this problem is to count the complement set. That is, we count the number of matching outfits by counting the number of mismatching outfits. By the Product Rule, there are 2 · 1 = 2 mismatching gray-green outfits and 3 · 3 = 9 mismatching brown-blue outfits. Therefore, there are 30 − 2 − 9 = 19 matching outfits.

Figure 1: This is a tree diagram for the matching outfits problem. Edge weights are shown in parentheses.

A second approach is to use a tree diagram like the one shown in Figure 1. Tree diagrams are useful in counting the number of possible outcomes arising from a sequence of decisions. In the simplest case, each internal node of a tree diagram represents a decision, each child corresponds to an available choice, and each leaf is associated with an outcome. The choice selected at one internal node determines what decisions must be made subsequently. For example, if we choose gray pants, then we must subsequently decide on a blue or red shirt; however, if we choose brown pants, then we must subsequently decide on a green or red shirt. The tree diagram in Figure 1 is a little more complicated because edges have weights; these correspond to distinct choices that lead to the same set of future decisions. For example, we can choose either of the two pairs of gray pants without affecting our subsequent choice of a shirt.

The number of matching outfits can be computed from the tree diagram as follows. A root-to-leaf path corresponds to a sequence of choices such as “gray pants, blue shirt”. The number of distinct outcomes of this type can be computed by the Product Rule; we just multiply the weights of the edges on the path. For example, the number of ways to choose a pair of gray pants and a blue shirt is 2 · 3 = 6 . Then we can use the Sum Rule to compute the number of outcomes of all types; we just add up all the products. This gives 6 + 4 + 3 + 6 = 19 matching outfits. This is the same number we found by the method of counting the complement. (Good thing!)

Tree diagrams are a more sophisticated example of the case analysis we did for phone numbers. They use cases to break up the top level set, then use more cases to break up each subset, and so on.

3.2 Playoff Outcomes

In how many ways can a 5-game playoff series be decided? That is, how many different sequences of wins and losses are there? A first answer might use the product rule and say 2^{5} = 32, but this count includes certain outcomes that can never happen. For example, one possibility is that the home team wins a game, then loses one, and then wins two more. In this case, there would be no need for a fifth game.

We can solve this problem with the tree diagram shown in Figure 2. In this case, there are no edge weights. (Equivalently, one can say that the edges all have weight 1.) The number of outcomes is equal to the number of leaves, which is 20.

Figure 2: This is a tree diagram for the number of ways to decide a 5-game playoff. W and L indicates wins and losses for the home team.

In a larger problem, like the 7-game World Series, the tree diagram would be unmanageable. As we will soon see, however, sometimes we can observe a pattern and count the number of leaves without drawing out the complete tree.

4 Permutations

4.1 Simple Permutations

In how many ways can n items be ordered in a line? Each such ordering is called a permutation. So the question can be restated as, “How many permutations are there of n items?”

It is unmanageable to solve this problem by drawing a complete tree diagram. However, the partial diagram shown in Figure 3, suggests that there are n choices for the first item, n − 1 choices for the second item given the first, n − 2 choices for the third item given the first two, etc. Therefore, the total number of leaves in the tree is n(n − 1)(n − 2) … 2 · 1 = n!. This gives an important fact; never forget it!

We can formalize this by observing that if P (n) is the number of permutations of n elements, then P (n) = n · P (n − 1) because there are n ways to pick the first element and then P (n − 1) ways to permute the remaining n − 1 items. This gives P (n) = n! by induction.

Figure 3: This is a partial tree diagram for counting the number of ways n items can be ordered in a line. The diagram suggests that there are n choices for the first item, n − 1 choices for the second, n − 2 for the third, and so forth.

Fact 1 The number of permutations of n items is n!.

For example, the number of ways to order a deck of cards is 52!. This is clearly a very big number; we can estimate how big with Stirling’s Formula:

52! ≥ \sqrt{2π52} (\frac{52}{e})^{52} e^{\frac{1}{12·52+1}}
= 8.05 . . . · 10^{67}

This is more than the number of atoms in the universe! This is more than the number of induction proofs in 6.042! Such rapid growth in the number of possibilities in combinatorial problems gives rise to the term “combinatorial explosion”. There is no way a computer could ever try all these arrangements!

4.2 A Lower Bound for Sorting

The fact that there are n! ways to order n items can be combined with the Pigeonhole Principle to prove a nice lower bound on the number of comparisons needed to sort a list of n items. In particular, we can prove that the Merge Sort algorithm that we covered three weeks ago is very close to optimal. (Recall that Merge Sort required at most n log_{2} n − n + 1 comparisons.)

Theorem 4.1 Any comparison-based sorting algorithm must make at least the following number of comparisons to sort n items in the worst case:

n log_{2} n − n log_{2} e

In a comparison-based sorting algorithm, we can compare two items and move items around in memory. All other operations on items, such as looking at certain bits or performing arithmetic on items, are ruled out. For example, there is a sorting algorithm called “bucket sort” that is not comparison-based and for which this theorem does not apply.

The idea behind the proof is the same as in the ball-and-balance problems that we saw two weeks ago. There we compared the number of possible locations of the odd-weight ball with the number of leaves in a decision tree defined by our weighing scheme. Here we compare the number of initial permutations of items with the number of leaves in a computation tree defined by the sorting algorithm.

Proof. Let x_{1}, …, x_{n} be the items to be sorted. Since we are proving a lower bound, we can assume that the items are all distinct.

Let A be any sorting algorithm. Algorithm A must permute the items x_{1}, …, x_{n} to put them in the correct order. Since a different permutation is required for each different initial ordering of the items, the number of different permutations that might be required is n!.

The computations performed by algorithm A can be modeled with a tree diagram as shown in Figure 4. Each internal node corresponds to a comparison of two items. The two subtrees beneath each internal node define the computations performed based on the result of the comparison. A run of the algorithm corresponds to a root-to-leaf path. Associated with each leaf is the permutation of x_{1}, …, x_{n} that places the items in sorted order.

We can assume that every node in the tree diagram is reached for some input. If a node were unreachable (say, because both x_{1} < x_{2} and x_{1} > x_{2} must hold to reach it), then we could remove that node from the tree.

Figure 4: This is how the computation tree of a sorting algorithm might look.

Every one of the n! permutations of x_{1}, …, x_{n} must appear at some leaf. Otherwise, if items are ordered according to some missing permutation, then the algorithm can not possibly output the correct answer.

Let L be the number of leaves in the computation tree. We will obtain both an upper bound and a lower bound on L.

Permutations are assigned in some way to leaves. Regard the permutations as pigeons and the leaves as holes. If L < n!, then by the Pigeonhole Principle, two permutations are assigned to the same leaf. This is a contradiction, since the algorithm always permutes the items one particular way. Therefore L ≥ n!.

On the other hand, the number of leaves is limited by the depth of the computation tree. Let D be the depth of the tree; that is, D is the length of the longest root-to-leaf path. Early in the course, we proved that the number of leaves in a binary tree with depth D is at most 2^{D}. Therefore, L ≤ 2^{D}.

Since D is the length of the longest root-to-leaf path in the computation tree, D is the number of comparisons used by algorithm A in the worst case. We can get a lower bound on D by putting together the upper and lower bounds on the number of leaves L.

2^{D} ≥ L ≥ n!
D ≥ log_{2} n!

Now we can use Stirling’s Formula to make sense of log_{2} n!:

D ≥ log_{2} (\sqrt{2πn} (\frac{n}{e})^{n} e^{\frac{1}{12n+1}} )
= n log_{2} n − n log_{2} e + \frac{1}{2} log_{2}(2πn) + \frac{log_{2} e}{12n + 1}
≥ n log_{2} n − n log_{2} e

Merge Sort requires at most n log_{2} n−n+1 comparisons. From the theorem, at least n log_{2} n−1.45n comparisons are necessary in the worst case. The difference is only about n/2, a low-order term. So Merge Sort is very nearly optimal!

4.3 r-Permutations

In a horse race, the first-place horse is said to “win”, the second-place horse is said to “place”, and the third-place horse is said to “show”. A bet in which one guesses exactly which horses will win, place, and show is called a Trifecta. How many possible Trifecta bets are there in a race with 10 horses? This problem is easy enough that we do not need to draw out the tree diagram; there are 10 choices to win, 9 choices to place given the winner, and 8 choices to show given the first two finishers. This gives 10 · 9 · 8 = 720 possible Trifecta bets.

This is a special case of a standard problem: counting r-permutations of a set.

Definition An r-permutation of a set is an ordering of r distinct items from the set.

For example, the 2-permutations of the set {A, B, C} are:

\begin{matrix}(A, B) & (A, C) & (B, C) \\ (B, A) & (C, A) & (C, B) \end{matrix}

The number of r-permutations of an n-element set comes up so often in combinatorial problems that there is a special notation.

Definition P (n, r) denotes the number of r-permutations of an n-element set. In other words,

P (n, r) = n(n − 1) … (n − r + 1) = \frac{n!}{(n − r)!}

For example, the number of Trifecta bets in a 10 horse race is P (10, 3) = \frac{10!}{7!} = 720.

Example: How many strings of 5 letters are there with no repetitions? For example, ZYGML, is such a string. In general, these strings are exactly the 5-permutations of the set of letters. Therefore, there are P (26, 5) = \frac{26!}{21!}, which is 7,893,600.

Example: How many ways can 5 students be chosen from a class of 180 to be given 5 fabulous (different) prizes, say $1000, $500, $250, $100, $50? Answer: P (180, 5), which is 180 × 179 × 178 × 177 × 176.

Example: How many injective functions are there from A to B, if |A| = n and |B| = m (assume n ≤ m). Answer: Order A arbitrarily. First element maps somewhere in B. Second element maps somewhere else (injective), etc. Number of possibilities is P (m, n) = m(m−1)(m−2) … (m− n + 1) = \frac{m!}{(m−n)!}. Essentially picking a sequence of n of the m elements of B.