资源描述
Math 475 Text: Brualdi, Introductory Combinatorics 5th Ed. Prof: Paul Terwilliger Selected solutions for Chapter 5 1. For an integer k and a real number n, we show n k = n 1 k 1 + n 1 k : First assume k 1. Then each side equals 0. Next assume k = 0. Then each side equals 1. Next assume k 1. Recall P(n;k) = n(n 1)(n 2) (n k + 1): We have n k = P(n;k)k! = nP(n 1;k 1)k! : n 1 k 1 = P(n 1;k 1)(k 1)! = kP(n 1;k 1)k! : n 1 k = P(n 1;k)k! = (n k)P(n 1;k 1)k! : The result follows. 2. Pascals triangle begins 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1 1 3. Let Z denote the set of integers. For nonnegative n 2 Z de ne F(n) = Pk2Z n kk . The sum is well de ned since nitely many summands are nonzero. We have F(0) = 1 and F(1) = 1. We show F(n) = F(n 1) +F(n 2) for n 2. Let n be given. Using Pascals formula and a change of variables k = h+ 1, F(n) = X k2Z n k k = X k2Z n k 1 k + X k2Z n k 1 k 1 = X k2Z n k 1 k + X h2Z n h 2 h = F(n 1) +F(n 2): Thus F(n) is the nth Fibonacci number. 4. We have (x+y)5 = x5 + 5x4y + 10 x3y2 + 10 x2y3 + 5xy4 +y5 and (x+y)6 = x6 + 6x5y + 15x4y2 + 20 x3y3 + 15x2y4 + 6xy5 +y6: 5. We have (2x y)7 = 7X k=0 7 k 27 k( 1)kx7 kyk: 6. The coe cient of x5y13 is 35( 2)13 185 . The coe cient of x8y9 is 0 since 8 + 96= 18. 7. Using the binomial theorem, 3n = (1 + 2)n = nX k=0 n k 2k: Similarly, for any real number r, (1 +r)n = nX k=0 n k rk: 8. Using the binomial theorem, 2n = (3 1)n = nX k=0 ( 1)k n k 3n k: 2 9. We have nX k=0 ( 1)k n k 10k = ( 1)n nX k=0 ( 1)n k n k 10k = ( 1)n(10 1)n = ( 1)n9n: The sum is 9n for n even and 9n for n odd. 10. Given integers 1 k n we show k n k = n n 1 k 1 : Let S denote the set of ordered pairs (x;y) such that x is a k-subset of f1;2;:;ng and y is an element of x. We compute jSj in two ways. (i) To obtain an element (x;y) of S there are nk choices for x, and for each x there are k choices for y. Therefore jSj= k nk . (ii) To obtain an element (x;y) of S there are n choices for y, and for each y there are n 1k 1 choices for x. Therefore jSj= n n 1k 1 . The result follows. 11. Given integers n 3 and 1 k n. We show n k n 3 k = n 1 k 1 + n 2 k 1 + n 3 k 1 : Let S denote the set of k-subsets of f1;2;:;ng. Let S1 consist of the elements in S that contain 1. Let S2 consist of the elements in S that contain 2 but not 1. Let S3 consist of the elements in S that contain 3 but not 1 or 2. Let S4 consist of the elements in S that do not contain 1 or 2 or 3. Note that fSig4i=1 partition S so jSj= P4i=1jSij. We have jSj= n k ; jS1j= n 1 k 1 ; jS2j= n 2 k 1 ; jS3j= n 3 k 1 ; jS4j= n 3 k : The result follows. 12. We evaluate the sum nX k=0 ( 1)k n k 2 : First assume that n = 2m+ 1 is odd. Then for 0 k m the k-summand and the (n k)- summand are opposite. Therefore the sum equals 0. Next assume that n = 2m is even. To evaluate the sum in this case we compute in two ways the the coe cient of xn in (1 x2)n. (i) By the binomial theorem this coe cient is ( 1)m 2mm . (ii) Observe (1 x2) = (1+x)(1 x). We have (1 +x)n = nX k=0 n k xk; (1 x)n = nX k=0 n k ( 1)kxk: 3 By these comments the coe cient of xn in (1 x2)n is nX k=0 n n k ( 1)k n k = nX k=0 ( 1)k n k 2 : Therefore nX k=0 ( 1)k n k 2 = ( 1)m 2m m : 13. We show that the given sum is equal to n+ 3 k : The above binomial coe cient is in row n + 3 of Pascals triangle. Using Pascals formula, write the above binomial coe cient as a sum of two binomial coe ents in row n + 2 of Pascals triangle. Write each of these as a sum of two binomial coe ents in row n + 1 of Pascals triangle. Write each of these as a sum of two binomial coe ents in row n of Pascals triangle. The resulting sum is n k + 3 n k 1 + 3 n k 2 + n k 3 : 14. Given a real number r and integer k such that r6= k. We show r k = rr k r 1 k : First assume that k 1. Then each side is 0. Next assume that k = 0. Then each side is 1. Next assume that k 1. Observe r k = P(r;k)k! = rP(r 1;k 1)k! ; and r 1 k = P(r 1;k)k! = (r k)P(r 1;k 1)k! : The result follows. 15. For a variable x consider (1 x)n = nX k=0 n k ( 1)kxk: 4 Take the derivative with respect to x and obtain n(1 x)n 1 = nX k=0 n k ( 1)kkxk 1: Now set x = 1 to get 0 = nX k=0 n k ( 1)kk: The result follows. 16. For a variable x consider (1 +x)n = nX k=0 n k xk: Integrate with respect to x and obtain (1 +x)n+1 n+ 1 = nX k=0 n k xk+1 k + 1 +C for a constant C. Set x = 0 to nd C = 1=(n+ 1). Thus (1 +x)n+1 1 n+ 1 = nX k=0 n k xk+1 k + 1: Now set x = 1 to get 2n+1 1 n+ 1 = nX k=0 n k 1 k + 1: 17. Routine. 18. For a variable x consider (x 1)n = nX k=0 n k ( 1)n kxk: Integrate with respect to x and obtain (x 1)n+1 n+ 1 = nX k=0 n k ( 1)n k x k+1 k + 1 +C for a constant C. Set x = 0 to nd C = ( 1)n+1=(n+ 1). Thus (x 1)n+1 ( 1)n+1 n+ 1 = nX k=0 n k ( 1)n k x k+1 k + 1: 5 Now set x = 1 to get ( 1)n n+ 1 = nX k=0 n k ( 1)n k 1k + 1: Therefore 1 n+ 1 = nX k=0 n k ( 1)k 1k + 1: 19. One readily checks 2 m 2 + m 1 = m(m 1) +m = m2: Therefore nX k=1 k2 = nX k=0 k2 = 2 nX k=0 k 2 + nX k=0 k 1 = 2 n+ 1 3 + n+ 1 2 = (n+ 1)n(2n+ 1)6 : 20. One readily checks m3 = 6 m 3 + 6 m 2 + m 1 : Therefore nX k=1 k3 = nX k=0 k3 = 6 nX k=0 k 3 + 6 nX k=0 k 2 + nX k=0 k 1 = 6 n+ 1 4 + 6 n+ 1 3 + n+ 1 2 = (n+ 1) 2n2 4 = n+ 1 2 2 : 6 21. Given a real number r and an integer k. We show r k = ( 1)k r +k 1 k : First assume that k 0. Then each side is zero. Next assume that k 0. Observe r k = ( r)( r 1) ( r k + 1)k! = ( 1)k r(r + 1) (r +k 1)k! = ( 1)k r +k 1 k : 22. Given a real number r and integers k;m. We show r m m k = r k r k m k : First assume that m k or k 0. Then each side is zero. Next assume that 0 k m. Observe r m m k = r(r 1) (r m+ 1)m! m!k!(m k)! = r(r 1) (r m+ 1)k!(m k)! = r(r 1) (r k + 1)k! (r k)(r k 1) (r m+ 1)(m k)! = r k r k m k : 23. (a) 2410 . (b) 94 156 . (c) 94 93 63 . (d) 94 156 94 93 63 . 24. The number of walks of length 45 is equal to the number of words of length 45 involving 10 xs, 15 ys, and 20 zs. This number is 45! 10! 15! 20!: 7 25. Given integers m1;m2;n 0. Show nX k=0 m 1 k m 2 n k = m 1 +m2 n : LetAdenote a set with cardinalitym1+m2. PartitionAinto subsetsA1, A2 with cardinalities m1 and m2 respectively. Let S denote the set of n-subsets of A. We compute jSj in two ways. (i) By construction jSj= m 1 +m2 n : (ii) For 0 k n let the set Sk consist of the elements in S whose intersection with A1 has cardinality k. The sets fSkgnk=0 partition S, so jSj= Pnk=0jSkj. For 0 k n we now computejSkj. To do this we construct an element x2Sk via the following 2-stage procedure: stage to do # choices 1 pick xA1 m1k 2 pick xA2 m2n k The number jSkj is the product of the entries in the right-most column above, which comes to m1k m2n k . By these comments jSj= nX k=0 m 1 k m 2 n k : The result follows. 26. For an integer n 1 show nX k=1 n k n k 1 = 12 2n+ 2 n+ 1 2n n : Using Problem 25, nX k=1 n k n k 1 = nX k=0 n k n k 1 = nX k=0 n k n n+ 1 k = 2n n+ 1 = 12 2n n 1 + 12 2n n+ 1 : 8 It remains to show 1 2 2n n 1 + 12 2n n+ 1 = 12 2n+ 2 n+ 1 2n n : This holds since 2n n 1 + 2 2n n + 2n n+ 1 = 2n+ 1 n + 2n+ 1 n+ 1 = 2n+ 2 n+ 1 : 27. Given an integer n 1. We show n(n+ 1)2n 2 = nX k=1 k2 n k : Let S denote the set of 3-tuples (s;x;y) such that s is a nonempty subset of f1;2;:;ng and x;y are elements (not necessarily distinct) in s. We compute jSj in two ways. (i) Call an element (s;x;y) of S degenerate whenever x = y. Partition S into subsets S+, S with S+ (resp. S ) consisting of the degenerate (resp. nondegenerate) elements of S. So jSj=jS+j+jS j. We computejS+j. To obtain an element (s;x;x) of S+ there are n choices for x, and given x there are 2n 1 choices for s. Therefore jS+j= n2n 1. We compute jS j. To obtain an element (s;x;y) of S there are n choices for x, and given x there are n 1 choices for y, and given x;y there are 2n 2 choices for s. ThereforejS j= n(n 1)2n 2. By these comments jSj= n2n 1 +n(n 1)2n 2 = n(n+ 1)2n 2: (ii) For 1 k n let Sk denote the set of elements (s;x;y) in S such that jsj = k. The sets fSkgnk=1 give a partition of S, so jSj= Pnk=1jSkj. For 1 k n we compute jSkj. To obtain an element (s;x;y) of Sk there are nk choices for s, and given s there are k2 ways to choose the pair x;y. Therefore jSkj= k2 nk . By these comments jSj= nX k=1 k2 n k : The result follows. 28. Given an integer n 1. We show nX k=1 k n k 2 = n 2n 1 n 1 : Let S denote the set of ordered pairs (s;x) such that s is a subset of f 1; 2;:; ng and x is a positive element of s. We computejSjin two ways. (i) To obtain an element (s;x) of S There are n choices for x, and given x there are 2n 1n 1 choices for s. Therefore jSj= n 2n 1 n 1 : 9 (ii) For 1 k n let Sk denote the set of elements (s;x) in S such that s contains exactly k positive elements. The sets fSkgnk=1 partition S, so jSj = Pnk=1jSkj. For 1 k n we compute jSkj. To obtain an element (s;x) of Sk there are nk ways to pick the positive elements of s and nn k = nk ways to pick the negative elements of s. Given s there are k ways to pick x. Therefore jSkj= k nk 2. By these comments jSj= nX k=1 k n k 2 : The result follows. 29. The given sum is equal to m 2 +m2 +m3 n : To see this, compute the coe cient of xn in each side of (1 +x)m1(1 +x)m2(1 +x)m3 = (1 +x)m1+m2+m3: In this computation use the binomial theorem. 30, 31, 32. We refer to the proof of Theorem 5.3.3 in the text. Let A denote an antichain such that jAj= n bn=2c : For 0 k n let k denote the number of elements in A that have size k. So nX k=0 k =jAj= n bn=2c : As shown in the proof of Theorem 5.3.3, nX k=0 k n k 1; with equality if and only if each maximal chain contains an element of A. By the above comments nX k=0 k n bn=2c n k n k 0; with equality if and only if each maximal chain contains an element ofA. The above sum is nonpositive but each summand is nonnegative. Therefore each summand is zero and the sum is zero. Consequently (a) each maximal chain contains an element of A; (b) for 0 k n either k is zero or its coe cient is zero. We now consider two cases. 10 Case: n is even. We show that for 0 k n, k = 0 if k6= n=2. Observe that for 0 k n, if k6= n=2 then the coe cient of k is nonzero, so k = 0. Case: n is odd. We show that for 0 k n, either k = 0 if k 6= (n 1)=2 or k = 0 if k6= (n + 1)=2. Observe that for 0 k n, if k6= (n 1)=2 then the coe cient of k is nonzero, so k = 0. We now show that k = 0 for k = (n 1)=2 or k = (n + 1)=2. To do this, we assume that k 6= 0 for both k = (n 1)=2 and get a contradiction. By assumption A contains an element x of size (n + 1)=2 and an element y of size (n 1)=2. De ne s =jxyj. Choose x;y such that s is maximal. By construction 0 s (n 1)=2. Suppose s = (n 1)=2. Then y = xy x, contradicting the fact that x;y are incomparable. So s (n 3)=2. Let y0 denote a subset of x that contains xy and has size (n 1)=2. Let x0 denote a subset of y0y that contains y0 and has size (n + 1)=2. By construction jx0yj= s+ 1. Observe y0 is not inAsince x;y0 are comparable. Also x0 is not inAby the maximality of s. By construction x0 covers y0 so they are together contained in a maximal chain. This chain does not contain an element of A, for a contradiction. 33. De ne a poset (X; ) as follows. The set X consists of the subsets of f1;2;:;ng. For x;y2X de ne x y whenever x y. For n = 3;4;5 we display a symmetric chain decomposition of this poset. We use the inductive procedure from the text. For n = 3, ;1;12;123 2;23 3;13: For n = 4, ;1;12;123;1234 4;14;124 2;23;234 24; 3;13;134 34: For n = 5, ;1;12;123;1234;12345 5;15;125;1235 4;14;124;1245 45;145 2;23;234;2345 25;235 24;245 3;13;134;1345 35;135 34;345: 11 34. For 0 k bn=2c there are exactly nk nk 1 symmetric chains of length n 2k + 1. 35. Let S denote the set of 10 jokes. Each night the talk show host picks a subset of S for his repertoire. It is required that these subsets form an antichain. By Corollary 5.3.2 each antichain has size at most 105 , which is equal to 252. Therefore the talk show host can continue for 252 nights. 36. Compute the coe cient of xn in either side of (1 +x)m1(1 +x)m2 = (1 +x)m1+m2; In this computation use the binomial theorem. 37. In the multinomial theorem (Theorem 5.4.1) set xi = 1 for 1 i t. 38. (x1 +x2 +x3)4 is equal to x41 +x42 +x43 + 4(x31x2 +x31x3 +x1x32 +x32x3 +x1x33 +x2x33) + 6(x21x22 +x21x23 +x22x23) + 12(x21x2x3 +x1x22x3 +x1x2x23): 39. The coe cient is 10! 3! 1! 4! 0! 2! which comes to 12600. 40. The coe cient is 9! 3! 3! 1! 2! 1 3 ( 1)3 2 ( 2)2 which comes to 40320. 41. One routinely obtains the multinomial theorem (Theorem 5.4.1) with t = 3. 42. Given an integer t 2 and positive integers n1;n2;:;nt. De ne n = Pti=1ni. We show n n1 n2 nt = tX k=1 n 1 n1 nk 1 nk 1 nk+1 nt : Consider the multiset fn1 x1;n2 x2;:;nt xtg: Let P denote the set of permutations of this multiset. We compute jPj in two ways. (i) We saw earlier that jPj= n!n 1! n2! nt! = n n1 n2 nt : 12 (ii) For 1 k t let Pk denote the set of elements in P that have rst coordinate xk. The sets fPkgtk=1 partition P, so jPj= Ptk=1jPkj. For 1 k t we compute jPkj. Observe that jPkj is the number of permutations of the multiset fn1 x1;:;nk 1 xk 1;(nk 1) xk;nk+1 xk+1;:;nt xtg: Therefore jPkj= n 1 n1 nk 1 nk 1 nk+1 nt : By these comments jPj= tX k=1 n 1 n1 nk 1 nk 1 nk+1 nt : The result follows. 43. Given an integer n 1. Show by induction on n that 1 (1 z)n = 1X k=0 n+k 1 k zk; jzj 1: The base case n = 1 is assumed to hold. We show that the above identity holds with n replaced by n+ 1, provided that it holds for n. Thus we show 1 (1 z)n+1 = 1X =0 n+ z; jzj 1: Observe 1 (1 z)n+1 = 1 (1 z)n 1 1 z = 1X k=0 n+k 1 k zk 1X h=0 zh = 1X =0 cz where c = n 1 0 + n 1 + n+ 1 2 + + n+ 1 = n+ : The result follows. 13 44. (Problem statement contains typo) The given sum is equal to ( 3)n. Observe ( 3)n = ( 1 1 1)n = X n1+n2+n3=n n n1 n2 n3 ( 1)n1+n2+n3 = X n1+n2+n3=n n n1 n2 n3 ( 1)n1 n2+n3: Also 1 = (1 1 + 1)n = X n1+n2+n3=n n n1 n2 n3 ( 1)n2: 45. (Problem statement contains typo) The given sum is equal to ( 4)n. Observe ( 4)n = ( 1 1 1 1)n = X n1+n2+n3+n4=n n n1 n2 n3 n4 ( 1)n1+n2+n3+n4 = X n1+n2+n3+n4=n n n1 n2 n3 n4 ( 1)n1 n2+n3 n4: Also 0 = (1 1 + 1 1)n = X n1+n2+n3+n4=n n n1 n2 n3 n4 ( 1)n2+n4: 46. Observe p30 = 5r30 25 = 5(1 +z)1=2 z = 1=5; = 5 1X k=0 1=2 k zk: For n = 0;1;2;: the nth approximation to p30 is an = 5 nX k=0 1=2 k 5 k: We have 14 n an 0 5 1 5.5 2 5.475 3 5.4775 4 5.4771875 5 5.47723125 6 5.477224688 7 5.477225719 8 5.477225551 9 5.477225579 47. Observe 101=3 = 2 10 8 1=3 = 2(1 +z)1=3 z = 1=4; = 2 1X k=0 1=3 k zk: For n = 0;1;2;: the nth approximation to 101=3 is an = 2 nX k=0 1=3 k 4 k: We have n an 0 2 1 2.166666667 2 2.152777778 3 2.154706790 4 2.154385288 5 2.154444230 6 2.154432769 7 2.154435089 8 2.154434605 9 2.154434708 48. We show that a poset with mn + 1 elements has a chain of size m + 1 or an antichain of size n + 1. Our strategy is to assume the result is false, and get a contradiction. By assumption each chain has size at most m and each antichain has size at most n. Let r denote the size of the longest chain. So r m. By Theorem 5.6.1 the elements of the poset can be partitioned into r antichains fAigri=1. We have jAij n for 1 i r. Therefore mn+ 1 = rX i=1 jAij rn mn; 15 for a contradiction. Therefore, the poset has a chain of size m + 1 or an antichain of size n+ 1. 49. We are given a sequence of mn+ 1 real numbers, denotedfaigmni=0. Let X denote the set of ordered pairs f(i;ai)j0 i mng. Observe jXj = mn + 1. De ne a partial order on X as follows: for distinct x = (i;ai) and y = (j;aj) in X, declare xy whenever ij and ai aj. For the poset (X; ) the chains correspond to the (weakly) increasing subsequences offaigmni=0, and the antichains correspond to the (strictly) decreasing subsequences offaigmni=0. By Problem 48, there exists a chain of size m+ 1 or an antichain of size n+ 1. Therefore the sequencefaigmni=0 has a (weakly) increasing subsequence of size m+1 or a (strictly) decreasing subsequence of size n+ 1. 50. (i) Here is a chain of size four: 1;2;4;8. Here is a partition of X into four antichains: 8;12 4;6;9;10 2;3;5;7;11 1 Therefore four is both the largest size of a chain, and the smallest number of antichains that partition X. (ii) Here is an antichain of size six: 7;8;9;10;11;12. Here is a partition of X into six chains: 1;2;4;8 3;6;12 9 5;10 7 11 Therefore six is both the largest size of an antichain, and the smallest number of chains that partition X. 51. There exists a chain x1 x2 xt of size t 2 in the poset S such that x1 6xt in the poset R. Indeed we could take t = 2 and let x1;x2 be elements of X such that x1 x2 in S but x1 6 x2 in R. Pick a chain as above with t maximal. De ne p = x1 and q = xt. Then the pair (p;q) meets the requirements of the problem. 16
展开阅读全文