1.1:Basic Counting 9 3. In how many ways can you draw a first card and then a second card from a deck of 52 cards? 4. In how many ways can you draw two cards from a deck of 52 cards? 5. In how many ways can you draw a first,second,and third card from a deck of 52 cards? 6. In how many ways can a 10-person club select a president and a secretary-treasurer from among its members? 7 In how many ways can a 10-person club select a two-person executive committee from among its members? 8. In how many ways can a 10-person club select a president and a two-person executive advisory board from among its members (assuming that the president is not on the advisory board)? Using the formula for (2,it is straightforward to show that (2)=()a-2 However,this proof simply uses blind substitution and simplification. Find a more conceptual explanation of why this formula is true (Hint:Think in terms of officers and committees in a club.) 10.If M is an m-element set and N is an n-element set,how many ordered pairs are there with the first member in M and the second member in N? 11.The local ice cream shop sells ten different flavors of ice cream. How many different two-scoop cones are there?(Following your mother's rule that it all goes to the same stomach,a cone with a vanilla scoop on top of a chocolate scoop is considered the same as a cone with chocolate on top of vanilla.) 12. Suppose you decide to disagree with your mother in Problem 11-the order of the scoops does matter.How many different possible two-scoop cones are there? 13. Suppose on Day 1 you receive one penny,and,for i>1,on Day i you receive twice as many pennies as you did on Day i-1.How many pennies will you have on Day 20?How many will you have on Day n?Can you justify your answer by using the sum or product principle? 14. The Pile High Deli offers a simple sandwich,consisting of your choice of one of five different kinds of bread;either butter, mayonnaise,or no spread;one of three different kinds of meat;and one of three different kinds of cheese,with the meat and cheese
1.1: Basic Counting 9 3. In how many ways can you draw a first card and then a second card from a deck of 52 cards? 4. In how many ways can you draw two cards from a deck of 52 cards? 5. In how many ways can you draw a first, second, and third card from a deck of 52 cards? 6. In how many ways can a 10-person club select a president and a secretary-treasurer from among its members? 7. In how many ways can a 10-person club select a two-person executive committee from among its members? 8. In how many ways can a 10-person club select a president and a two-person executive advisory board from among its members (assuming that the president is not on the advisory board)? 9. Using the formula for n 2 , it is straightforward to show that n n − 1 2 = n 2 (n − 2). However, this proof simply uses blind substitution and simplification. Find a more conceptual explanation of why this formula is true. (Hint: Think in terms of officers and committees in a club.) 10. If M is an m-element set and N is an n-element set, how many ordered pairs are there with the first member in M and the second member in N? 11. The local ice cream shop sells ten different flavors of ice cream. How many different two-scoop cones are there? (Following your mother’s rule that it all goes to the same stomach, a cone with a vanilla scoop on top of a chocolate scoop is considered the same as a cone with chocolate on top of vanilla.) 12. Suppose you decide to disagree with your mother in Problem 11—the order of the scoops does matter. How many different possible two-scoop cones are there? 13. Suppose on Day 1 you receive one penny, and, for i > 1, on Day i you receive twice as many pennies as you did on Day i − 1. How many pennies will you have on Day 20? How many will you have on Day n? Can you justify your answer by using the sum or product principle? 14. The Pile High Deli offers a simple sandwich, consisting of your choice of one of five different kinds of bread; either butter, mayonnaise, or no spread; one of three different kinds of meat; and one of three different kinds of cheese, with the meat and cheese
10 Chapter 1:Counting piled high on the bread.In how many ways can you choose a simple sandwich? 15.Do you see any unnecessary steps in the pseudocode of Exercise 1.1-3?Explain. 1.2 COUNTING LISTS,PERMUTATIONS,AND SUBSETS Using the Sum and Product Principles Exercise 1.2-1 A password for a certain computer system is supposed to be between four and eight characters long and composed of lowercase and/or uppercase letters.How many passwords are possible?What counting principles did you use?Estimate the percentage of the possible passwords that have exactly four letters. A good way to attack a counting problem is to ask if we can use either the sum principle or the product principle to simplify or completely solve it.For this exercise,that question might lead us to think about the fact that a password can have four,five,six,seven,or eight characters.Because the set of all passwords is the union of those with four,five,six,seven, and eight letters,the sum principle might help us.To write the problem algebraically,let Pi be the set of i-letter passwords and P be the set of all possible passwords.Clearly, P=P4UPsUPUP]UPs The P;are mutually disjoint;thus,we can apply the sum principle to obtain i=4 We still need to compute Pil.For an i-letter password,there are 52 choices for the first letter,52 choices for the second,and so on.By the product principle,|Pi-the number of passwords with i letters-is 52.Therefore, the total number of passwords is 524+525+526+527+528 Of these,524 have four letters,so the percentage with four letters is 100.524 524+525+526+527+528
10 Chapter 1: Counting piled high on the bread. In how many ways can you choose a simple sandwich? 15. Do you see any unnecessary steps in the pseudocode of Exercise 1.1-3? Explain. 1.2 COUNTING LISTS, PERMUTATIONS, AND SUBSETS Using the Sum and Product Principles Exercise 1.2-1 A password for a certain computer system is supposed to be between four and eight characters long and composed of lowercase and/or uppercase letters. How many passwords are possible? What counting principles did you use? Estimate the percentage of the possible passwords that have exactly four letters. A good way to attack a counting problem is to ask if we can use either the sum principle or the product principle to simplify or completely solve it. For this exercise, that question might lead us to think about the fact that a password can have four, five, six, seven, or eight characters. Because the set of all passwords is the union of those with four, five, six, seven, and eight letters, the sum principle might help us. To write the problem algebraically, let Pi be the set of i-letter passwords and P be the set of all possible passwords. Clearly, P = P4 ∪ P5 ∪ P6 ∪ P7 ∪ P8. The Pi are mutually disjoint; thus, we can apply the sum principle to obtain |P| = 8 i=4 |Pi|. We still need to compute |Pi|. For an i-letter password, there are 52 choices for the first letter, 52 choices for the second, and so on. By the product principle, |Pi|—the number of passwords with i letters—is 52i . Therefore, the total number of passwords is 524 + 525 + 526 + 527 + 528 . Of these, 524 have four letters, so the percentage with four letters is 100 · 524 524 + 525 + 526 + 527 + 528
1.2:Counting Lists,Permutations,and Subsets 11 Although this is a nasty formula to evaluate by hand,we can get quite a good estimate as follows:Notice that 528 is 52 times as big as 527 and even more dramatically larger than any other term in the sum in the denominator. The ratio is thus a bit less than 100.524 528, which is 100/524,or approximately 0.000014.Thus,to five decimal places, only 0.00001%of the passwords have four letters.It is therefore much easier to guess a password that we know has four letters than it is to guess one that has between four and eight letters-roughly 7 million times easier! Our solution to Exercise 1.2-1 casually refers to the use of the product principle in computing the number of passwords with i letters.We didn't write any set as a union of sets of equal size.We could have,but it would have been clumsy and repetitive.For this reason,we now state a second version of the product principle,which we can derive from the version for unions of sets by using the idea of mathematical induction (see Chapter 4). Principle 1.4 (Product Principle,Version 2) If a set S of lists of length m has the properties that 1.there are i different first elements of lists in S,and 2.for each j>1 and each choice of the first j-1 elements of a list in S,there are i;choices of elements in position j of those lists, then there are ii2…im=ΠW=ik lists in S. Version 2 of the product principle introduces a new notation:the use of II to stand for product.This is called the product notation,and it is used just like summation notation.In particular,is read,The product from k=1 to m of ig."Thus,I ik means the same thing as ii2...im. Let's apply this version of the product principle to compute the number of m-letter passwords.Because an m-letter password is simply a list of m letters and because there are 52 different first elements of the pass- word and 52 choices for each other position of the password,we have that i =52,i2 =52,...,im =52.Thus,this version of the product prin- ciple tells us immediately that the number of passwords of length m is i12…im=52m
1.2: Counting Lists, Permutations, and Subsets 11 Although this is a nasty formula to evaluate by hand, we can get quite a good estimate as follows: Notice that 528 is 52 times as big as 527 and even more dramatically larger than any other term in the sum in the denominator. The ratio is thus a bit less than 100 · 524 528 , which is 100/524, or approximately 0.000014. Thus, to five decimal places, only 0.00001% of the passwords have four letters. It is therefore much easier to guess a password that we know has four letters than it is to guess one that has between four and eight letters—roughly 7 million times easier! Our solution to Exercise 1.2-1 casually refers to the use of the product principle in computing the number of passwords with i letters. We didn’t write any set as a union of sets of equal size. We could have, but it would have been clumsy and repetitive. For this reason, we now state a second version of the product principle, which we can derive from the version for unions of sets by using the idea of mathematical induction (see Chapter 4). Principle 1.4 (Product Principle, Version 2) If a set S of lists of length m has the properties that 1. there are i1 different first elements of lists in S, and 2. for each j > 1 and each choice of the first j − 1 elements of a list in S, there are ij choices of elements in position j of those lists, then there are i1i2 ··· im = m k=1 ik lists in S. Version 2 of the product principle introduces a new notation: the use of to stand for product. This is called the product notation, and it is used just like summation notation. In particular, m k=1 ik is read, “The product from k = 1 to m of ik.” Thus, m k=1 ik means the same thing as i1i2 ··· im. Let’s apply this version of the product principle to compute the number of m-letter passwords. Because an m-letter password is simply a list of m letters and because there are 52 different first elements of the password and 52 choices for each other position of the password, we have that i1 = 52, i2 = 52, ..., im = 52. Thus, this version of the product principle tells us immediately that the number of passwords of length m is i1i2 ··· im = 52m.
12 Chapter 1:Counting Lists and Functions Our discussion of version 2 of the product principle left the term "list" undefined.A list of three things chosen from a set T consists of a first member t of T,a second member t2 of T,and a third member t3 of T,not necessarily all different.If we rewrite the list in a different order,we get a different list.A list of k things chosen from T consists of a first member of T through a kth member of T.To give a more precise definition of a list, we can use the word"function,"which you probably recall from algebra or calculus. Recall that a function from a set S(called the domain of the function) to a set T (called the range of the function)is a relationship between the elements of S and the elements of T that relates exactly one element of T to each element of S.We use a letter,such as f,to stand for a function and f(x)to stand for the element of T related to the element x of S.You are probably used to thinking of functions in terms of formulas like fx)=x. We use formulas like this in algebra and calculus because the functions studied in those classes have infinite sets of numbers as their domains and ranges.In discrete mathematics,however,functions often have finite sets as their domains and ranges,so it is possible to describe a function by saying exactly what it is.For example, f(1)=Sam,f(2)=Mary,f(3)=Sarah is a function that describes a list of three names.This suggests a precise definition of a list of k elements from a set T:a list of k elements from a set T is a function from (1,2,...,k}to T. Exercise 1.2-2 Write down all the functions from the two-element set {1,2)to the two- element set fa,b). Exercise 1.2-3 How many functions are there from a two-element set to a three-element set? Exercise 1.2-4 How many functions are there from a three-element set to a two-element set? In Exercise 1.2-2,it is difficult to choose a notation for writing the functions. We use fi,f2,and so on to stand for the various functions we find.To describe a function fi from (1,2]to (a,b),we have to specify fi(1)and fi(2).We can write f(1)=a fi(2)=b f(1)=b f(2)=a
12 Chapter 1: Counting Lists and Functions Our discussion of version 2 of the product principle left the term “list” undefined. A list of three things chosen from a set T consists of a first member t1 of T, a second member t2 of T, and a third member t3 of T, not necessarily all different. If we rewrite the list in a different order, we get a different list. A list of k things chosen from T consists of a first member of T through a kth member of T. To give a more precise definition of a list, we can use the word “function,” which you probably recall from algebra or calculus. Recall that a function from a set S (called the domain of the function) to a set T (called the range of the function) is a relationship between the elements of S and the elements of T that relates exactly one element of T to each element of S. We use a letter, such as f, to stand for a function and f(x) to stand for the element of T related to the element x of S. You are probably used to thinking of functions in terms of formulas like f(x) = x2. We use formulas like this in algebra and calculus because the functions studied in those classes have infinite sets of numbers as their domains and ranges. In discrete mathematics, however, functions often have finite sets as their domains and ranges, so it is possible to describe a function by saying exactly what it is. For example, f(1) = Sam, f(2) = Mary, f(3) = Sarah is a function that describes a list of three names. This suggests a precise definition of a list of k elements from a set T : a list of k elements from a set T is a function from {1, 2,...,k} to T. Exercise 1.2-2 Write down all the functions from the two-element set {1, 2} to the twoelement set {a, b}. Exercise 1.2-3 How many functions are there from a two-element set to a three-element set? Exercise 1.2-4 How many functions are there from a three-element set to a two-element set? In Exercise 1.2-2, it is difficult to choose a notation for writing the functions. We use f1, f2, and so on to stand for the various functions we find. To describe a function fi from {1, 2} to {a, b}, we have to specify fi(1) and fi(2). We can write f1(1) = a f1(2) = b f2(1) = b f2(2) = a
1.2:Counting Lists,Permutations,and Subsets 13 f3(1)=a f5(2)=a f4(1)=b f4(2)=b In this case,we simply wrote the functions as they occurred to us;but how do we know we have all of them?The set of all functions from (1,2) to fa,b}is the union of the functions fi with fi(1)=a and those with fi(1)=b.The set of functions with fi(1)=a has two elements,one for each choice of fi(2).Therefore,by the product principle,the set of all functions from (1,2)to (a,b}has size 2.2 =4. To compute the number of functions from a two-element set(say (1,2))to a three-element set,we can again think of using fi to stand for a typical function.The set of all functions is the union of three sets,one for each choice of fi(1).Each of these sets has three elements,one for each choice of fi(2).Thus,by the product principle,we have 3.3=9 functions from a two-element set to a three-element set. To compute the number of functions from a three-element set (say (1,2,3)) to a two-element set,we observe that the set of functions is a union of four sets,one for each choice of fi(1)and fi(2)(as we saw in our solution to Exercise 1.2-2).However,each of these sets has two functions in it,one for each choice of fi(3).Thus,by the product principle,we have 4.2=8 functions from a three-element set to a two-element set. A function f is called one-to-one,or an injection,if f(x)f(y)when- ever xy.4 Notice that the two functions fi and f2 in our solution to Exercise 1.2-2 are one-to-one,but f3 and f4 are not. A function f is called onto,or a surjection,if every element y in the range is f(x)for some x in the domain.Notice that the functions fi and f2 in our solution to Exercise 1.2-2 are onto,but f3 and f4 are not. Exercise 1.2-5 Using two-or three-element sets as domains and ranges,find an example of a one-to-one function that is not onto. Exercise 1.2-6 Using two-or three-element sets as domains and ranges,find an example of an onto function that is not one-to-one. The function given by f(1)=c,f(2)=a is an example of a function from (1,2)to fa,b,c}that is one-to-one but not onto.Also,the function given by f(1)=a,f(2)=b,f(3)=a is an example of a function from (1,2,3) to fa,b}that is onto but not one-to-one. 4To understand the concept of one-to-one,it may help to contrast "one-to-one"with “many-to-one
1.2: Counting Lists, Permutations, and Subsets 13 f3(1) = a f3(2) = a f4(1) = b f4(2) = b. In this case, we simply wrote the functions as they occurred to us; but how do we know we have all of them? The set of all functions from {1, 2} to {a, b} is the union of the functions fi with fi(1) = a and those with fi(1) = b. The set of functions with fi(1) = a has two elements, one for each choice of fi(2). Therefore, by the product principle, the set of all functions from {1, 2} to {a, b} has size 2 · 2 = 4. To compute the number of functions from a two-element set (say {1, 2}) to a three-element set, we can again think of using fi to stand for a typical function. The set of all functions is the union of three sets, one for each choice of fi(1). Each of these sets has three elements, one for each choice of fi(2). Thus, by the product principle, we have 3 · 3 = 9 functions from a two-element set to a three-element set. To compute the number of functions from a three-element set (say {1, 2, 3}) to a two-element set, we observe that the set of functions is a union of four sets, one for each choice of fi(1) and fi(2) (as we saw in our solution to Exercise 1.2-2). However, each of these sets has two functions in it, one for each choice of fi(3). Thus, by the product principle, we have 4 · 2 = 8 functions from a three-element set to a two-element set. A function f is called one-to-one, or an injection, if f(x) = f(y) whenever x = y. 4 Notice that the two functions f1 and f2 in our solution to Exercise 1.2-2 are one-to-one, but f3 and f4 are not. A function f is called onto, or a surjection, if every element y in the range is f(x) for some x in the domain. Notice that the functions f1 and f2 in our solution to Exercise 1.2-2 are onto, but f3 and f4 are not. Exercise 1.2-5 Using two- or three-element sets as domains and ranges, find an example of a one-to-one function that is not onto. Exercise 1.2-6 Using two- or three-element sets as domains and ranges, find an example of an onto function that is not one-to-one. The function given by f(1) = c, f(2) = a is an example of a function from {1, 2} to {a, b, c} that is one-to-one but not onto. Also, the function given by f(1) = a, f(2) = b, f(3) = a is an example of a function from {1, 2, 3} to {a, b} that is onto but not one-to-one. 4To understand the concept of one-to-one, it may help to contrast “one-to-one” with “many-to-one