4 Chapter 1:Counting A clever trick,usually attributed to Carl Friedrich Gauss,gives us a shorter formula for this sum: 1 +2+.·+(n-2)+(n-1) +(n-1)+(n-2)+··+2+1 n十n The sum below the horizontal line has n-1 terms,each equal to n.Thus, the sum is n(n-1),or the sum of the two sums above the line.Because these sums are equal (identical except for being in reverse order),the sum below the line must be twice either sum above.Therefore,either of the sums above the line must be n(n-1)/2.In other words,we may write This lovely trick is quite helpful in other similar situations involving a sum of variables.There are other ways to get the formula that don't use a trick. At the end of this section,after we analyze Exercise 1.1-2 and abstract the process used there,we will come back to this problem to see how we could have discovered this formula for ourselves without any tricks. The Product Principle Exercise 1.1-2 The following loop is part of a program that computes the product of two matrices.(You don't need to know how to find the product of two matrices to do this exercise.) (1)for i=1 to r (2) for j=1 to m (3) S=0 (4) for k 1 to n (5) S=S+A[i,k]B[k,j] (6) c[i,j]s How many multiplications (expressed in terms of r,m,and n)does this pseudocode carry out in total among all the iterations of Line 5? Exercise 1.1-3 Consider the following longer piece of pseudocode that sorts a list of num- bers and then counts big gaps in the list.(For this exercise,a"big gap"is a place where a number in the list is more than twice the previous number.)
4 Chapter 1: Counting A clever trick, usually attributed to Carl Friedrich Gauss, gives us a shorter formula for this sum: 1 + 2 + ··· + (n − 2) + (n − 1) + (n − 1) + (n − 2) + ··· + 2 + 1 n + n + ··· + n + n The sum below the horizontal line has n − 1 terms, each equal to n. Thus, the sum is n(n − 1), or the sum of the two sums above the line. Because these sums are equal (identical except for being in reverse order), the sum below the line must be twice either sum above. Therefore, either of the sums above the line must be n(n − 1)/2. In other words, we may write n−1 i=1 (n − i) = n−1 i=1 i = n(n − 1) 2 . This lovely trick is quite helpful in other similar situations involving a sum of variables. There are other ways to get the formula that don’t use a trick. At the end of this section, after we analyze Exercise 1.1-2 and abstract the process used there, we will come back to this problem to see how we could have discovered this formula for ourselves without any tricks. The Product Principle Exercise 1.1-2 The following loop is part of a program that computes the product of two matrices. (You don’t need to know how to find the product of two matrices to do this exercise.) (1) for i = 1 to r (2) for j = 1 to m (3) S = 0 (4) for k = 1 to n (5) S = S + A[i,k] * B[k,j] (6) C[i,j] = S How many multiplications (expressed in terms of r, m, and n) does this pseudocode carry out in total among all the iterations of Line 5? Exercise 1.1-3 Consider the following longer piece of pseudocode that sorts a list of numbers and then counts big gaps in the list. (For this exercise, a “big gap” is a place where a number in the list is more than twice the previous number.)
1.1:Basic Counting 5 (1) for i 1 to n-1 (2) minval A[i] (3) minindex =i (4) for j=i to n (5) if (A[j]<minval) (6) minval A[j] (7) minindex =j (8) exchange A[i]and A[minindex] (9) bigjump =0 (10) for i=2 to n (11) if(A[i]>2*A[i-1]) (12) bigjump bigjump 1 How many comparisons does the pseudocode make in Lines 5 and 11? In Exercise 1.1-2,the program segment in Lines 4-5,which we call the "inner loop,"takes exactly n steps.Thus,it makes n multiplications,regard- less of what the variables i and j are.The program segment in Lines 2-5 repeats the inner loop exactly m times,regardless of what i is.Therefore, this program segment makes n multiplications m times,or nm multiplica- tions. Why did we add in Exercise 1.1-1 but multiply here?We can answer this question using the abstract point of view we adopted in discussing Exercise 1.1-1.The algorithm in Exercise 1.1-2 performs a certain set of multiplications.For any given i,the set of multiplications performed in Lines 2-5 can be divided into the set SI of multiplications performed when j=1,the set S2 of multiplications performed when j=2,and,in gen- eral,the set Si of multiplications performed for any given value of j.Each set Si consists of those multiplications that the inner loop carries out for a particular value of j,and there are exactly n multiplications in this set. Let T;be the set of multiplications that our program segment carries out for a certain value of i.The set Ti is the union of the sets Si.We use the standard notation for unions to write i=1 By the sum principle,the size of the set Ti is the sum of the sizes of the sets Si.A sum of m numbers,each equal to n,is mn.Stated as an equation, 9-21-2=m = (1.3)
1.1: Basic Counting 5 (1) for i = 1 to n − 1 (2) minval = A[i] (3) minindex = i (4) for j = i to n (5) if (A[j] < minval) (6) minval = A[j] (7) minindex = j (8) exchange A[i] and A[minindex] (9) bigjump = 0 (10) for i = 2 to n (11) if (A[i]>2 * A[i − 1]) (12) bigjump = bigjump + 1 How many comparisons does the pseudocode make in Lines 5 and 11? In Exercise 1.1-2, the program segment in Lines 4–5, which we call the “inner loop,” takes exactly n steps. Thus, it makes n multiplications, regardless of what the variables i and j are. The program segment in Lines 2–5 repeats the inner loop exactly m times, regardless of what i is. Therefore, this program segment makes n multiplications m times, or nm multiplications. Why did we add in Exercise 1.1-1 but multiply here? We can answer this question using the abstract point of view we adopted in discussing Exercise 1.1-1. The algorithm in Exercise 1.1-2 performs a certain set of multiplications. For any given i, the set of multiplications performed in Lines 2–5 can be divided into the set S1 of multiplications performed when j = 1, the set S2 of multiplications performed when j = 2, and, in general, the set Sj of multiplications performed for any given value of j. Each set Sj consists of those multiplications that the inner loop carries out for a particular value of j, and there are exactly n multiplications in this set. Let Ti be the set of multiplications that our program segment carries out for a certain value of i. The set Ti is the union of the sets Sj . We use the standard notation for unions to write Ti = m j=1 Sj . By the sum principle, the size of the set Ti is the sum of the sizes of the sets Sj . A sum of m numbers, each equal to n, is mn. Stated as an equation, |Ti| = m j=1 Sj = m j=1 |Sj | = m j=1 n = mn. (1.3)
6 Chapter 1:Counting Thus,we multiplied because multiplication is repeated addition. From our solution,we extract a second principle that simply shortcuts the use of the sum principle. Principle 1.3 (Product Principle) The size of a union of m disjoint sets,each of size n,is mn. We now complete our discussion of Exercise 1.1-2.Lines 2-5 are executed once for each value of i from I to r.A different i value is used each time those lines are executed;so,the set of multiplications in one execution is disjoint from the set of multiplications in any other.Thus,the set of all multiplications that the program carries out is a union of r disjoint sets Ti, each of which consists of mn multiplications.By the product principle,the set of all multiplications has size rmn.Therefore,the program carries out rmn multiplications. Exercise 1.1-3 shows us that thinking about whether the sum or product principle is appropriate for a problem can help decompose the problem into easily solvable pieces.If we can decompose the problem into smaller pieces and solve the smaller pieces,then we may be able to either add or multiply solutions to smaller problems in order to solve the larger problem.In this exercise,the number of comparisons in the program fragment is the sum of the number of comparisons in the first loop (Lines 1-8)and the number of comparisons in the second loop (Lines 10-12).(What two disjoint sets are we talking about here?)Furthermore,the first loop makes n(n+1)/2-1 comparisons,2 and the second loop has n-1 comparisons.The number of comparisons made by the fragment is n(n+1)/2-1+n-1 n(n+ 1)/2+n-2 comparisons. Two-Element Subsets There are often several ways to solve a problem.We originally solved Exercise 1.1-1 using the sum principle,but it is also possible to solve it using the product principle.Solving a problem two ways not only increases our confidence that we have found the correct solution,but it can also allow us to make new connections and yield valuable insight. Consider the set of comparisons made by the entire execution of the code in Exercise 1.1-1.When i=1,variable j takes on every value from 2 to 2To see why this is true,ask yourself first where the n(n+1)/2 comes from and then why we subtracted 1
6 Chapter 1: Counting Thus, we multiplied because multiplication is repeated addition. From our solution, we extract a second principle that simply shortcuts the use of the sum principle. Principle 1.3 (Product Principle) The size of a union of m disjoint sets, each of size n, is mn. We now complete our discussion of Exercise 1.1-2. Lines 2–5 are executed once for each value of i from 1 to r. A different i value is used each time those lines are executed; so, the set of multiplications in one execution is disjoint from the set of multiplications in any other. Thus, the set of all multiplications that the program carries out is a union of r disjoint sets Ti, each of which consists of mn multiplications. By the product principle, the set of all multiplications has size rmn. Therefore, the program carries out rmn multiplications. Exercise 1.1-3 shows us that thinking about whether the sum or product principle is appropriate for a problem can help decompose the problem into easily solvable pieces. If we can decompose the problem into smaller pieces and solve the smaller pieces, then we may be able to either add or multiply solutions to smaller problems in order to solve the larger problem. In this exercise, the number of comparisons in the program fragment is the sum of the number of comparisons in the first loop (Lines 1–8) and the number of comparisons in the second loop (Lines 10–12). (What two disjoint sets are we talking about here?) Furthermore, the first loop makes n(n + 1)/2 − 1 comparisons,2 and the second loop has n − 1 comparisons. The number of comparisons made by the fragment is n(n + 1)/2 − 1 + n − 1 = n(n + 1)/2 + n − 2 comparisons. Two-Element Subsets There are often several ways to solve a problem. We originally solved Exercise 1.1-1 using the sum principle, but it is also possible to solve it using the product principle. Solving a problem two ways not only increases our confidence that we have found the correct solution, but it can also allow us to make new connections and yield valuable insight. Consider the set of comparisons made by the entire execution of the code in Exercise 1.1-1. When i = 1, variable j takes on every value from 2 to 2To see why this is true, ask yourself first where the n(n + 1)/2 comes from and then why we subtracted 1
1.1:Basic Counting 7 n.When i=2,variable j takes on every value from 3 to n.Thus,for each two numbers i and j,we compare A[i]and ALj]exactly once in our loop.(The order in which we compare them depends on whether i or j is smaller.)Thus,the number of comparisons we make is the same as the number of two-element subsets of the set (1,2,...,n).3 In how many ways can we choose two elements from this set?If we choose a first and second element,there are n ways to choose a first element,and for each choice of the first element,there are n-1 ways to choose a second element.Thus, the set of all such choices is the union of n sets of size n-1,one set for each first element.It might appear that,by the product principle,there are n(n-1)ways to choose two elements from our set.However,what we have chosen is an ordered pair,or a pair of elements in which one comes first and the other comes second.For example,we could choose 2 first and 5 second to get the ordered pair (2,5),or we could choose 5 first and 2 second to get the ordered pair(5,2).Because each pair of distinct elements of (1,2,...,n}can be ordered in two ways,we get twice as many ordered pairs as two-element sets.Thus,because the number of ordered pairs is n(n-1),the number of two-element subsets of {1,2,...,n)is n(n-1)/2. Therefore,the answer to Exercise 1.1-1 is n(n-1)/2.This number comes up so often,it has its own name and notation:we call this number "n choose2”'and denote it by(径)，To summarize,.(2)stands for the number of two-element subsets of an n-element set and equals n(n-1)/2.Because one answer to Exercise 1.1-1 is 1+2+...+(n-1)and a second answer to Exercise 1.1-1 is(),we see that n(n-1) 1+2+..+(n-1) 2 Important Concepts,Formulas,and Theorems 1.Set.A set is a collection of objects.In a set,order is not important. Thus,the set (A,B,C}is the same as the set [A,C,B).An element either is or is not in a set;it cannot be in a set more than once,even if a description of a set names that element more than once. 2.Disjoint.Two sets are disjoint if they have no elements in common. 3.Mutually disjoint sets.A set of sets (S1,...,Sn)is a family of mutually disjoint sets if each two of the sets S;are disjoint. 4.Size of a set.Given a set S,the size of S,denoted S,is the number of distinct elements in S. 3The relationship between the set of comparisons and the set of two-element subsets of (1.2.....n)is an example of a bijection,an idea that we examine more in Section 1.2
1.1: Basic Counting 7 n. When i = 2, variable j takes on every value from 3 to n. Thus, for each two numbers i and j, we compare A[i] and A[j ] exactly once in our loop. (The order in which we compare them depends on whether i or j is smaller.) Thus, the number of comparisons we make is the same as the number of two-element subsets of the set {1, 2,...,n}. 3 In how many ways can we choose two elements from this set? If we choose a first and second element, there are n ways to choose a first element, and for each choice of the first element, there are n − 1 ways to choose a second element. Thus, the set of all such choices is the union of n sets of size n − 1, one set for each first element. It might appear that, by the product principle, there are n(n − 1) ways to choose two elements from our set. However, what we have chosen is an ordered pair, or a pair of elements in which one comes first and the other comes second. For example, we could choose 2 first and 5 second to get the ordered pair (2, 5), or we could choose 5 first and 2 second to get the ordered pair (5, 2). Because each pair of distinct elements of {1, 2,...,n} can be ordered in two ways, we get twice as many ordered pairs as two-element sets. Thus, because the number of ordered pairs is n(n − 1), the number of two-element subsets of {1, 2,...,n} is n(n − 1)/2. Therefore, the answer to Exercise 1.1-1 is n(n − 1)/2. This number comes up so often, it has its own name and notation: we call this number “n choose 2” and denote it by n 2 . To summarize, n 2 stands for the number of two-element subsets of an n-element set and equals n(n − 1)/2. Because one answer to Exercise 1.1-1 is 1 + 2 +···+ (n − 1) and a second answer to Exercise 1.1-1 is n 2 , we see that 1 + 2 +···+ (n − 1) = n 2 = n(n − 1) 2 . Important Concepts, Formulas, and Theorems 1. Set. A set is a collection of objects. In a set, order is not important. Thus, the set {A, B,C} is the same as the set {A,C, B}. An element either is or is not in a set; it cannot be in a set more than once, even if a description of a set names that element more than once. 2. Disjoint. Two sets are disjoint if they have no elements in common. 3. Mutually disjoint sets. A set of sets {S1,...,Sn} is a family of mutually disjoint sets if each two of the sets Si are disjoint. 4. Size of a set. Given a set S, the size of S, denoted |S|, is the number of distinct elements in S. 3The relationship between the set of comparisons and the set of two-element subsets of {1, 2,...,n} is an example of a bijection, an idea that we examine more in Section 1.2
8 Chapter 1:Counting 5.Sum principle.The size of a union of a family of mutually disjoint sets is the sum of the sizes of the sets.In other words,if S1,S2...., S are disjoint sets,then S1US2U·USnl=lS1l+lS2l+·+lSnl To avoid the "dots"that indicate left-out material,we write 6.Partition of a set.A partition of a set S is a set of mutually disjoint subsets (sometimes called blocks)of S whose union is S. 7.Sum of first n-1 numbers. n(n-1) 8.Product principle.The size of a union of m disjoint sets,each of size n,is mn. 9.Two-element subsets.The number of two-element subsets of an n-element set,denoted ()equals n(n-1)/2.(is read as"n choose2.” Problems All problems with blue boxes have an answer or hint available at the end of the book. 1. The following segment of code is part of a program that uses insertion sort to sort a list A. for i -2 to n j=i while (j 2)and (A[j]A[j-1]) exchange A[j]and A[j-1] j=j-1 What is the maximum number of times (considering all lists of n items that you could be asked to sort)the program makes the comparison A[j]A[j-1]?Describe as succinctly as you can those lists that require this number of comparisons. 2.Five schools are going to send their baseball teams to a tournament in which each team must play each other team exactly once.How many games are required?
8 Chapter 1: Counting 5. Sum principle. The size of a union of a family of mutually disjoint sets is the sum of the sizes of the sets. In other words, if S1, S2, ..., Sn are disjoint sets, then |S1 ∪ S2 ∪···∪ Sn|=|S1|+|S2|+···+|Sn|. To avoid the “dots” that indicate left-out material, we write n i=1 Si = n i=1 |Si|. 6. Partition of a set. A partition of a set S is a set of mutually disjoint subsets (sometimes called blocks) of S whose union is S. 7. Sum of first n − 1 numbers. n−1 i=1 n − i = n−1 i=1 i = n(n − 1) 2 . 8. Product principle. The size of a union of m disjoint sets, each of size n, is mn. 9. Two-element subsets. The number of two-element subsets of an n-element set, denoted n 2 , equals n(n − 1)/2. n 2 is read as “n choose 2.” Problems All problems with blue boxes have an answer or hint available at the end of the book. 1. The following segment of code is part of a program that uses insertion sort to sort a list A. for i = 2 to n j = i while (j ≥ 2) and (A[j] < A[j − 1]) exchange A[j] and A[j − 1] j = j − 1 What is the maximum number of times (considering all lists of n items that you could be asked to sort) the program makes the comparison A[j ] < A[j − 1]? Describe as succinctly as you can those lists that require this number of comparisons. 2. Five schools are going to send their baseball teams to a tournament in which each team must play each other team exactly once. How many games are required?