xxviii Preface Laserwords was in charge of ushering the manuscript through copyediting, composition,and proofreading. Each of the authors would like to thank the other two for the time they have taken from other professional activities to work on this project.Because of the time required to meld the points of view of our disciplines,it was only with the support of the National Science Foundation (Grant DUE- 9552462)that we were able to undertake this project.We believe that the staff of the Division of Undergraduate Education showed excellent insight into the needs of undergraduates and the difficulties of interdisciplinary cur- ricular development when they conceived their program of Mathematical Sciences and their applications throughout the curriculum.We would like to acknowledge the positive impact this program had on undergraduate mathe- matics education and on the development of interdisciplinary collaborations in curriculum development. Cliff Stein Scot Drysdale
xxviii Preface Laserwords was in charge of ushering the manuscript through copyediting, composition, and proofreading. Each of the authors would like to thank the other two for the time they have taken from other professional activities to work on this project. Because of the time required to meld the points of view of our disciplines, it was only with the support of the National Science Foundation (Grant DUE- 9552462) that we were able to undertake this project. We believe that the staff of the Division of Undergraduate Education showed excellent insight into the needs of undergraduates and the difficulties of interdisciplinary curricular development when they conceived their program of Mathematical Sciences and their applications throughout the curriculum. We would like to acknowledge the positive impact this program had on undergraduate mathematics education and on the development of interdisciplinary collaborations in curriculum development. Cliff Stein Scot Drysdale
DISCRETE MATHEMATICS FOR COMPUTER SCIENTISTS
DISCRETE MATHEMATICS FOR COMPUTER SCIENTISTS
1 Counting 1.1 BASIC COUNTING The Sum Principle In this book,we introduce ideas through exercises.Trying to figure out how to do each exercise will help you understand the explanation that follows. Our first exercise illustrates the sum principle. Exercise 1.1-1 The following loop is part of an implementation of selection sort,which sorts a list of items chosen from an ordered set (numbers,alphabet characters, words,etc.)into nondecreasing order. (1)for i=1 to n-1 (2) for j=i+1 to n (3) if (A[i]>A[j]) (4) exchange A[i]and A[j] How many times is the comparison A[i]A[j]made in Line 3? In Exercise 1.1-1,the segment of code from Lines 2-4 is executed n- 1 times,once for each value of i between 1 and n-1,inclusive.The first time,it makes n-1 comparisons.The second time,it makes n-2 comparisons.The ith time,it makes n-i comparisons.Thus,the total number of comparisons is (n-1)+(n-2)+·+1. (1.1) This formula is not as important as the reasoning that led to it.To put the reasoning into a broadly applicable format,we use the language of sets to describe what we are doing.Think about the set S containing all comparisons made by the algorithm in Exercise 1.1-1,in which we divided set S into n-1 pieces (i.e.,smaller sets):the set S of comparisons made when i =1,the set S2 of comparisons made when i =2,and so on through 1
1 Counting 1.1 BASIC COUNTING The Sum Principle In this book, we introduce ideas through exercises. Trying to figure out how to do each exercise will help you understand the explanation that follows. Our first exercise illustrates the sum principle. Exercise 1.1-1 The following loop is part of an implementation of selection sort, which sorts a list of items chosen from an ordered set (numbers, alphabet characters, words, etc.) into nondecreasing order. (1) for i = 1 to n − 1 (2) for j = i + 1 to n (3) if (A[i] > A[j]) (4) exchange A[i] and A[j] How many times is the comparison A[i] > A[j ] made in Line 3? In Exercise 1.1-1, the segment of code from Lines 2–4 is executed n − 1 times, once for each value of i between 1 and n − 1, inclusive. The first time, it makes n − 1 comparisons. The second time, it makes n − 2 comparisons. The ith time, it makes n − i comparisons. Thus, the total number of comparisons is (n − 1) + (n − 2) +···+ 1. (1.1) This formula is not as important as the reasoning that led to it. To put the reasoning into a broadly applicable format, we use the language of sets to describe what we are doing. Think about the set S containing all comparisons made by the algorithm in Exercise 1.1-1, in which we divided set S into n − 1 pieces (i.e., smaller sets): the set S1 of comparisons made when i = 1, the set S2 of comparisons made when i = 2, and so on through 1
2 Chapter 1:Counting the set Sn-1 of comparisons made when i =n-1.We figured out the number of comparisons in each piece and then added the sizes of all the pieces to get the size of the set of all comparisons. To describe a general version of this process,we now introduce some set- theoretic terminology.Two sets are called disjoint when they have no elements in common.Each set S;described above is disjoint from each of the others because the comparisons made for one value of i are differ- ent from those made for another value of i.We say that the set of sets (S1,...,Sm}(above,m was n-1)is a family of mutually disjoint sets, to mean that it is a family (set)of sets,any two of which are disjoint.With this language,we can state a general principle that explains what we did without making any specific reference to the problem we solved. Principle 1.1 (Sum Principle) The size of a union of a family of mutually disjoint finite sets is the sum of the sizes of the sets. Thus,in effect,we used the sum principle to solve Exercise 1.1-1.We can also describe the sum principle using an algebraic notation.Let S denote the size of the set S.For example,la,b,c)=3 and la,b,a)l =2.I Using this notation,we can state the sum principle as follows.If S,S2.....Sm are disjoint sets,then ISUS2U.…USml=lSl+lS2l+·+ISml (1.2) We can also use the standard notation for union,as follows,to avoid writing the dots that indicate left-out material (as was done in Equation 1.2).The union notation is used exactly as summation notation and is read as "the union from i equals 1 to m of S sub i." When we can write a set S as a union of disjoint sets S1,S2,...,Sk,we say that we have partitioned S into the sets S1,S2....,Sk and that the sets S1, IIt may look strange to have lfa,b.a)l=2,but an element either is or is not in a set.An element cannot be in a set multiple times.(This situation leads to the idea of multisets, which are introduced in Section 1.5.)This example emphasizes that the notation fa,b,a) means the same thing as fa,b).Why would someone even contemplate the notation a,b.a)?Suppose we wrote S=xx is the first letter of Ann.Bob,or Alice).Explicitly following this description of S would lead us to first write down (a,b,a)and then realize it equals fa,b)
2 Chapter 1: Counting the set Sn−1 of comparisons made when i = n − 1. We figured out the number of comparisons in each piece and then added the sizes of all the pieces to get the size of the set of all comparisons. To describe a general version of this process, we now introduce some settheoretic terminology. Two sets are called disjoint when they have no elements in common. Each set Si described above is disjoint from each of the others because the comparisons made for one value of i are different from those made for another value of i. We say that the set of sets {S1,...,Sm} (above, m was n − 1) is a family of mutually disjoint sets, to mean that it is a family (set) of sets, any two of which are disjoint. With this language, we can state a general principle that explains what we did without making any specific reference to the problem we solved. Principle 1.1 (Sum Principle) The size of a union of a family of mutually disjoint finite sets is the sum of the sizes of the sets. Thus, in effect, we used the sum principle to solve Exercise 1.1-1. We can also describe the sum principle using an algebraic notation. Let |S| denote the size of the set S. For example, |{a, b, c}| = 3 and |{a, b, a}| = 2.1 Using this notation, we can state the sum principle as follows. If S1, S2,...,Sm are disjoint sets, then |S1 ∪ S2 ∪···∪ Sm|=|S1|+|S2|+···+|Sm|. (1.2) We can also use the standard notation for union, as follows, to avoid writing the dots that indicate left-out material (as was done in Equation 1.2). The union notation is used exactly as summation notation and is read as “the union from i equals 1 to m of S sub i.” m i=1 Si = m i=1 |Si|. When we can write a set S as a union of disjoint sets S1, S2,...,Sk, we say that we have partitioned S into the sets S1, S2,...,Sk and that the sets S1, 1It may look strange to have |{a, b, a}| = 2, but an element either is or is not in a set. An element cannot be in a set multiple times. (This situation leads to the idea of multisets, which are introduced in Section 1.5.) This example emphasizes that the notation {a, b, a} means the same thing as {a, b}. Why would someone even contemplate the notation {a, b, a}? Suppose we wrote S = {x|x is the first letter of Ann, Bob, or Alice}. Explicitly following this description of S would lead us to first write down {a, b, a} and then realize it equals {a, b}.
1.1:Basic Counting 3 S2,....S&form a partition of S.Thus,((1),(3,5),(2,4))is a partition of the set {1,2,3,4,5),and the set (1,2,3,4,5}can be partitioned into the sets (1),(3,5),(2,4).However,it is clumsy to say we are partitioning a set into sets;instead,we call the sets Si,into which we partition a set S,the blocks of the partition.Thus,the sets (1),{3,5),(2,4)are the blocks of a partition of (1,2,3,4,5).In this language,we can restate the sum principle as follows. Principle 1.2 (Sum Principle) If a finite set S has been partitioned into blocks,then the size of S is the sum of the sizes of the blocks. Abstraction The process of figuring out a general principle that explains why a certain computation makes sense is an example of the mathematical process of abstraction.In this book,we don't give a precise definition of abstraction; instead,we provide examples of the process as we proceed.In a course in set theory,we would further abstract our work and derive the sum principle from the axioms of set theory.In a course in discrete mathematics,however, this level of abstraction is unnecessary.We simply use the sum principle as the basis of computations when it is convenient to do so.If our goal were to solve only Exercise 1.1-1,then our abstraction would have been almost a mindless exercise that complicated what was an "obvious"solution. However,the sum principle will prove to be useful in a variety of problems. Thus,the value of abstraction is that recognizing the abstract elements of a problem often helps us solve subsequent problems. Summing Consecutive Integers Returning to the problem in Exercise 1.1-1,it would be nice to find a simpler form for the sum given in Equation 1.1.We may write this sum as ∑m-i). i= To avoid summing the values of n-i,we observe that the values we are summing are n-1,n-2,...,1;so,we may write
1.1: Basic Counting 3 S2,...,Sk form a partition of S. Thus, {{1},{3, 5},{2, 4}} is a partition of the set {1, 2, 3, 4, 5}, and the set {1, 2, 3, 4, 5} can be partitioned into the sets {1}, {3, 5}, {2, 4}. However, it is clumsy to say we are partitioning a set into sets; instead, we call the sets Si, into which we partition a set S, the blocks of the partition. Thus, the sets {1}, {3, 5}, {2, 4} are the blocks of a partition of {1, 2, 3, 4, 5}. In this language, we can restate the sum principle as follows. Principle 1.2 (Sum Principle) If a finite set S has been partitioned into blocks, then the size of S is the sum of the sizes of the blocks. Abstraction The process of figuring out a general principle that explains why a certain computation makes sense is an example of the mathematical process of abstraction. In this book, we don’t give a precise definition of abstraction; instead, we provide examples of the process as we proceed. In a course in set theory, we would further abstract our work and derive the sum principle from the axioms of set theory. In a course in discrete mathematics, however, this level of abstraction is unnecessary. We simply use the sum principle as the basis of computations when it is convenient to do so. If our goal were to solve only Exercise 1.1-1, then our abstraction would have been almost a mindless exercise that complicated what was an “obvious” solution. However, the sum principle will prove to be useful in a variety of problems. Thus, the value of abstraction is that recognizing the abstract elements of a problem often helps us solve subsequent problems. Summing Consecutive Integers Returning to the problem in Exercise 1.1-1, it would be nice to find a simpler form for the sum given in Equation 1.1. We may write this sum as n−1 i=1 (n − i). To avoid summing the values of n − i, we observe that the values we are summing are n − 1, n − 2,..., 1; so, we may write n−1 i=1 (n − i) = n−1 i=1 i