14 Chapter 1:Counting The Bijection Principle Exercise 1.2-7 The following loop is part of a program to determine the number of triangles formed by n points in the plane. (1) trianglecount =0 (2) for i =1 to n (3) for j=i+1 to n (4)】 for k j+1 to n (5)】 if points i,j,and k are not collinear (6)】 trianglecount trianglecount +1 Among all iterations of line 5 of the pseudocode,what is the total number of times this line checks three points to see if they are collinear? Exercise 1.2-7 has a loop embedded in a loop embedded in another loop. Because the second loop,starting in Line 3,begins with j=i+1 and j increases up to n and because the third loop,starting in Line 4,begins with k =j+1 and k increases up to n,the code examines each triple of values i,j,k,with i<j<k,exactly once.For example,if n is 4,then the triples (i,j,k)used by the algorithm,in order,are (1,2,3),(1,2,4), (1,3,4),and (2,3,4).Thus,one way to solve Exercise 1.2-7 would be to compute the number of such triples,which we call increasing triples.As with the earlier case of two-element subsets,the number of such triples is the number of three-element subsets of an n-element set.This is the second time we have proposed counting the elements of one set (in this case,the set of increasing triples chosen from the set (1,2....,n))by saying that the number of elements of the set is equal to the number of elements of some other set (in this case,the set of three-element subsets of the set {1,2,,n}). When are we justified in making the assertion that two sets have the same size?There is a fundamental principle that abstracts our concept of what it means for two sets to have the same size.Intuitively,two sets have the same size if we can match their elements in such a way that each element of one set corresponds to exactly one element of the other set.This description carries with it some of the same words that appeared in the definitions of one-to-one and onto functions.Thus,it should be no surprise that one-to-one and onto functions are part of our abstract principle. Principle 1.5 (Bijection Principle) Two sets have the same size if and only if there is a one-to-one function from one set onto the other
14 Chapter 1: Counting The Bijection Principle Exercise 1.2-7 The following loop is part of a program to determine the number of triangles formed by n points in the plane. (1) trianglecount = 0 (2) for i = 1 to n (3) for j = i + 1 to n (4) for k = j + 1 to n (5) if points i, j, and k are not collinear (6) trianglecount = trianglecount + 1 Among all iterations of line 5 of the pseudocode, what is the total number of times this line checks three points to see if they are collinear? Exercise 1.2-7 has a loop embedded in a loop embedded in another loop. Because the second loop, starting in Line 3, begins with j = i + 1 and j increases up to n and because the third loop, starting in Line 4, begins with k = j + 1 and k increases up to n, the code examines each triple of values i, j, k, with i<j<k, exactly once. For example, if n is 4, then the triples (i, j, k) used by the algorithm, in order, are (1, 2, 3), (1, 2, 4), (1, 3, 4), and (2, 3, 4). Thus, one way to solve Exercise 1.2-7 would be to compute the number of such triples, which we call increasing triples. As with the earlier case of two-element subsets, the number of such triples is the number of three-element subsets of an n-element set. This is the second time we have proposed counting the elements of one set (in this case, the set of increasing triples chosen from the set {1, 2,...,n}) by saying that the number of elements of the set is equal to the number of elements of some other set (in this case, the set of three-element subsets of the set {1, 2,..., n}). When are we justified in making the assertion that two sets have the same size? There is a fundamental principle that abstracts our concept of what it means for two sets to have the same size. Intuitively, two sets have the same size if we can match their elements in such a way that each element of one set corresponds to exactly one element of the other set. This description carries with it some of the same words that appeared in the definitions of one-to-one and onto functions. Thus, it should be no surprise that one-to-one and onto functions are part of our abstract principle. Principle 1.5 (Bijection Principle) Two sets have the same size if and only if there is a one-to-one function from one set onto the other
1.2:Counting Lists,Permutations,and Subsets 15 This principle is called the bijection principle because a one-to-one and onto function is called a bijection.Another name for a bijection is a one-to- one correspondence.A bijection from a set to itself is called a permutation of that set. What bijection is behind our assertion that the number of increasing triples equals the number of three-element subsets?We define the function f as the function that takes the increasing triple (i,j,k)to the subset (i,j,k). Because the three elements of an increasing triple are different,the subset is a three-element set;so,we have a function from increasing triples to three-element sets.Because two different triples can't be the same set in two different orders,they must be associated with different sets.Thus,f is one-to-one.Because each set of three integers can be listed in increasing order,it is thus the image of an increasing triple under f.Therefore f is onto.Thus,we have a one-to-one correspondence,or bijection,between the set of increasing triples and the set of three-element sets. k-Element Permutations of a Set Because counting increasing triples is equivalent to counting three-element subsets,we can count increasing triples by counting three-element subsets instead.We use a method similar to the one used to compute the number of two-element subsets of a set.Recall that the first step of that method was to compute the number of ordered pairs of distinct elements that we can choose from the set [1,2,...,n).So we now ask,in how many ways can we choose an ordered triple of distinct elements from (1,2,...,n)? Or more generally,in how many ways can we choose a list of k distinct elements from (1,2,...,n)?A list of k distinct elements chosen from a set N is called a k-element permutation'of N. How many three-element permutations of (1,2,...,n)can we make?Recall that a k-element permutation is a list of k distinct elements.There are n choices for the first number in the list.For each way of choosing the first element,there are n-1 choices for the second.For each choice of the first two elements,there are n-2 ways to choose a third (distinct)number. So,by version 2 of the product principle,there are n(n-1)(n-2)ways to choose the list of numbers.For example,if n=4,the three-element 5In particular,a k-element permutation of (2.....is a list ofk distinct elements of (1.2.....k),which,by our definition of a list,is a function from (1.2.....k}to (1,2,....k).This function must be one-to-one because the elements of the list are distinct. Because there are k distinct elements of the list,every element of (1,2.....k)appears in the list,so the function is onto.This means our function is a bijection.Thus,our definition of a permutation of a set is consistent with our definition of a k-element permutation in the case where the set is (1,2.....k)
1.2: Counting Lists, Permutations, and Subsets 15 This principle is called the bijection principle because a one-to-one and onto function is called a bijection. Another name for a bijection is a one-toone correspondence. A bijection from a set to itself is called a permutation of that set. What bijection is behind our assertion that the number of increasing triples equals the number of three-element subsets? We define the function f as the function that takes the increasing triple (i, j, k) to the subset {i, j, k}. Because the three elements of an increasing triple are different, the subset is a three-element set; so, we have a function from increasing triples to three-element sets. Because two different triples can’t be the same set in two different orders, they must be associated with different sets. Thus, f is one-to-one. Because each set of three integers can be listed in increasing order, it is thus the image of an increasing triple under f. Therefore f is onto. Thus, we have a one-to-one correspondence, or bijection, between the set of increasing triples and the set of three-element sets. k-Element Permutations of a Set Because counting increasing triples is equivalent to counting three-element subsets, we can count increasing triples by counting three-element subsets instead. We use a method similar to the one used to compute the number of two-element subsets of a set. Recall that the first step of that method was to compute the number of ordered pairs of distinct elements that we can choose from the set {1, 2,...,n}. So we now ask, in how many ways can we choose an ordered triple of distinct elements from {1, 2,...,n}? Or more generally, in how many ways can we choose a list of k distinct elements from {1, 2,...,n}? A list of k distinct elements chosen from a set N is called a k-element permutation5 of N. How many three-element permutations of {1, 2,...,n} can we make? Recall that a k-element permutation is a list of k distinct elements. There are n choices for the first number in the list. For each way of choosing the first element, there are n − 1 choices for the second. For each choice of the first two elements, there are n − 2 ways to choose a third (distinct) number. So, by version 2 of the product principle, there are n(n − 1)(n − 2) ways to choose the list of numbers. For example, if n = 4, the three-element 5In particular, a k-element permutation of {1, 2,...,k} is a list of k distinct elements of {1, 2,...,k}, which, by our definition of a list, is a function from {1, 2,...,k} to {1, 2,...,k}. This function must be one-to-one because the elements of the list are distinct. Because there are k distinct elements of the list, every element of {1, 2,...,k} appears in the list, so the function is onto. This means our function is a bijection. Thus, our definition of a permutation of a set is consistent with our definition of a k-element permutation in the case where the set is {1, 2,...,k}
16 Chapter 1:Counting permutations of {1,2,3,4}are L={123,124,132,134,142,143,213,214,231,234,241,243, 312,314,321,324,341,342,412,413,421,423,431,4321.(1.4) There are indeed 4.3.2 =24 lists in this set.Notice that this list is in the order that it would appear in a dictionary(assuming we treated numbers as we treat letters).This ordering of lists is called lexicographic ordering. A general pattern is emerging.To compute the number of k-element per- mutations of the set (1,2,...,n),we first recall that those permutations are lists.Then we note the following: We have n choices for the first element of the list. Regardless of which choice we make,we have n-1 choices for the second element of the list. More generally,given the first i-1 elements of a list,we have n-(i-1)=n-i+1 choices for the ith element of the list. Thus,by version 2 of the product principle,we have n(n-1)...(n-k+ 1)(which is the first k terms of n!)ways to choose a k-element permutation of (1,2.....n).A very handy notation for this product,first suggested by Donald E.Knuth,is nk,which stands for n(n-1)…(n-k+1) i=0 We call this the kth falling factorial power of n.We summarize our obser- vations in a theorem. Theorem 1.1 The number of k-element permutations of an n-element set is k-1 Πom-i)=nm-1)…(m-k+1)= n! (n-k)！ Counting Subsets of a Set We now return to the question of counting the number of three-element sub- sets of (12...)We use ()which we read as"choose 3."to stand for the number of three-element subsets of (1,2,...,n),or,more generally, of any n-element set.We just carried out the first step of computing by counting the number of three-element permutations of (1,2,...,n)
16 Chapter 1: Counting permutations of {1, 2, 3, 4} are L = {123, 124, 132, 134, 142, 143, 213, 214, 231, 234, 241, 243, 312, 314, 321, 324, 341, 342, 412, 413, 421, 423, 431, 432}. (1.4) There are indeed 4 · 3 · 2 = 24 lists in this set. Notice that this list is in the order that it would appear in a dictionary (assuming we treated numbers as we treat letters). This ordering of lists is called lexicographic ordering. A general pattern is emerging. To compute the number of k-element permutations of the set {1, 2,...,n}, we first recall that those permutations are lists. Then we note the following: • We have n choices for the first element of the list. • Regardless of which choice we make, we have n − 1 choices for the second element of the list. • More generally, given the first i − 1 elements of a list, we have n − (i − 1) = n − i + 1 choices for the ith element of the list. Thus, by version 2 of the product principle, we have n(n − 1)···(n − k + 1) (which is the first k terms of n!) ways to choose a k-element permutation of {1, 2,...,n}. A very handy notation for this product, first suggested by Donald E. Knuth, is nk , which stands for n(n − 1)···(n − k + 1) = k −1 i=0 (n − i). We call this the kth falling factorial power of n. We summarize our observations in a theorem. Theorem 1.1 The number of k-element permutations of an n-element set is nk = k −1 i=0 (n − i) = n(n − 1)···(n − k + 1) = n! (n − k)! . Counting Subsets of a Set We now return to the question of counting the number of three-element subsets of {1, 2,...,n}. We use n 3 , which we read as “n choose 3,” to stand for the number of three-element subsets of {1, 2,...,n}, or, more generally, of any n-element set. We just carried out the first step of computing n 3 by counting the number of three-element permutations of {1, 2,...,n}
1.2:Counting Lists,Permutations,and Subsets 17 Exercise 1.2-8 Let L be the set of all three-element permutations of (1,2,3,4),as in Equation 1.4.How many of the lists (permutations)in L are lists of the three-element set (1,3,4)?What are these lists? We see that this set appears in L as six different lists:134,143,314,341, 413,and 431.In general,when given three different numbers with which to create a list,there are three ways to choose the first number in the list; given the first,there are two ways to choose the second;and given the first two,there is only one way to choose the third element.Thus,by version 2 of the product principle,there are 3.2.1 =6 ways to make the list. Because there are n(n-1)(n-2)three-element permutations of an n- element set and each three-element subset appears in exactly six of these lists,the number of three-element permutations is six times the number of three-element subsets-that is,n(n-1)(n-2)=().6.Whenever we see that one number that counts something is the product of two other numbers that count something,we should expect there to be an argument using the product principle explaining why.Thus,we should be able to see how to break the set of all three-element permutations of (1,2,...,n}either into six disjoint sets of size ()or into (subsets of size six.Because we argued that each three-element subset corresponds to six lists,we have described how to get a set of six lists from one three-element set.Two different sub- sets could never give us the same lists,so our sets of three-element lists are disjoint.In other words,we have divided the set of all three-element permutations into()mutually disjoint sets of size six.Thus,the product principle explains why n(n-1)(n-2)=(3).6.By division,we find that ()= n(n-1)n-2) 6 is the number of three-element subsets of (1,2,...,n).For n=4,the number is 4(3)(2)/6=4,and the sets are (1,2,3),{1,2,4),{1,3,4),and (2,3.,41.It is straightforward to verify that each of these sets appears six times in L as six different lists. Essentially the same argument gives us the number of k-element subsets of (1.2.....n).We denote this number by ()which is read as"n choosek." Here is the argument:The set of all k-element permutations of (1,2,...,n} can be partitioned into(disjoint blocks,with each block comprising all k-element permutations of a k-element subset of (1,2....,n).However, the number of k-element permutations of a k-element set is k!,either by version 2 of the product principle or by Theorem 1.1.Thus,by version 1 6Here we are using the language introduced for partitions of sets in Section 1.1
1.2: Counting Lists, Permutations, and Subsets 17 Exercise 1.2-8 Let L be the set of all three-element permutations of {1, 2, 3, 4}, as in Equation 1.4. How many of the lists (permutations) in L are lists of the three-element set {1, 3, 4}? What are these lists? We see that this set appears in L as six different lists: 134, 143, 314, 341, 413, and 431. In general, when given three different numbers with which to create a list, there are three ways to choose the first number in the list; given the first, there are two ways to choose the second; and given the first two, there is only one way to choose the third element. Thus, by version 2 of the product principle, there are 3 · 2 · 1 = 6 ways to make the list. Because there are n(n − 1)(n − 2) three-element permutations of an nelement set and each three-element subset appears in exactly six of these lists, the number of three-element permutations is six times the number of three-element subsets—that is, n(n − 1)(n − 2) = n 3 · 6. Whenever we see that one number that counts something is the product of two other numbers that count something, we should expect there to be an argument using the product principle explaining why. Thus, we should be able to see how to break the set of all three-element permutations of {1, 2,...,n} either into six disjoint sets of size n 3 or into n 3 subsets of size six. Because we argued that each three-element subset corresponds to six lists, we have described how to get a set of six lists from one three-element set. Two different subsets could never give us the same lists, so our sets of three-element lists are disjoint. In other words, we have divided the set of all three-element permutations into n 3 mutually disjoint sets of size six. Thus, the product principle explains why n(n − 1)(n − 2) = n 3 · 6. By division, we find that n 3 = n(n − 1)(n − 2) 6 is the number of three-element subsets of {1, 2,...,n}. For n = 4, the number is 4(3)(2)/6 = 4, and the sets are {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, and {2, 3, 4}. It is straightforward to verify that each of these sets appears six times in L as six different lists. Essentially the same argument gives us the number of k-element subsets of {1, 2,...,n}. We denote this number by n k , which is read as “n choose k.” Here is the argument: The set of all k-element permutations of {1, 2,...,n} can be partitioned into n k disjoint blocks,6 with each block comprising all k-element permutations of a k-element subset of {1, 2,...,n}. However, the number of k-element permutations of a k-element set is k!, either by version 2 of the product principle or by Theorem 1.1. Thus, by version 1 6Here we are using the language introduced for partitions of sets in Section 1.1
18 Chapter 1:Counting of the product principle,we get =( Division by k!gives us our next theorem. Theorem 1.2 For integers n and k with 0<k <n,the number of k-element subsets of an n-element set is n n! Proof The proof is given above,except for when k=0.However,the only subset of our n-element set of size zero is the empty set,so we have exactly one such subset.This is exactly what the formula gives us as well. (Note that the cases k =0 and k =n both use the fact?that 0!=1.)The equality in the theorem comes from the definition of n< Another notation for the numbers (is C(n,k).Thus,we have that C(n,k)= n! k!(n-K)月 (1.5) These numbers are called binomial coefficients for reasons that will become clear later. Important Concepts,Formulas,and Theorems 1.List.A list of k items chosen from a set X is a function from {1,2,.,k}toX 2.Lists versus sets.In a list,the order in which elements appear matters,and an element may appear more than once.In a set,the order of the elements does not matter,and an element may appear at most once. 3.Product principle,version 2.If a set S of lists of length m has the properties that a.there are i different first elements of lists in S,and b.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 lists in S. 7There are many reasons why 0!is defined to be 1.Making the formula for ()work out is one of those reasons
18 Chapter 1: Counting of the product principle, we get nk = n k k!. Division by k! gives us our next theorem. Theorem 1.2 For integers n and k with 0 ≤ k ≤ n, the number of k-element subsets of an n-element set is nk k! = n! k!(n − k)! . Proof The proof is given above, except for when k = 0. However, the only subset of our n-element set of size zero is the empty set, so we have exactly one such subset. This is exactly what the formula gives us as well. (Note that the cases k = 0 and k = n both use the fact7 that 0! = 1.) The equality in the theorem comes from the definition of nk. Another notation for the numbers n k is C(n, k). Thus, we have that C(n, k) = n k = n! k!(n − k)! . (1.5) These numbers are called binomial coefficients for reasons that will become clear later. Important Concepts, Formulas, and Theorems 1. List. A list of k items chosen from a set X is a function from {1, 2,...,k} to X. 2. Lists versus sets. In a list, the order in which elements appear matters, and an element may appear more than once. In a set, the order of the elements does not matter, and an element may appear at most once. 3. Product principle, version 2. If a set S of lists of length m has the properties that a. there are i1 different first elements of lists in S, and b. 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 lists in S. 7There are many reasons why 0! is defined to be 1. Making the formula for n k work out is one of those reasons