Solution Manual for Discrete Mathematics for Computer Scientists, 1st Edition

Page 1 of 16

Solution Manual for Discrete Mathematics for Computer Scientists, 1st Edition - Page 1 preview image

Bogart-81046bookApril 27, 200517:121COUNTING1.1BASIC COUNTINGPages 7 to 8Problem 1SolutionThe value ofiranges from 2 ton. Wheni=k, the variablejranges from 2 tok.Thus, there are at mostk−1 comparisons (because we stop ifj=2). Thus, the totalnumber of comparisons is1+2+ · · · +n−1=n(n−1)2.The algorithm will make this number of comparisons if the original ordering is thereverse of the sorted ordering.Problem 2SolutionNumber the five teams 1–5. Team 1 must play all four others. Team 2 will be in oneof these games but must play in three more games with Teams 3, 4, and 5. Team 3is in two of the games already mentioned and must still play Teams 4 and 5 fortwo more games. Team 4 must play Team 5, in addition to playing in three of thegames already mentioned. Thus, there are 4+3+2+1=10 games. Alternatively,there are five teams, each of which must play in four games, giving us 20 pairingsof two teams each. However, each game involves two of these pairings, so there are20/2=10 games.S1

Page 2 of 16

Solution Manual for Discrete Mathematics for Computer Scientists, 1st Edition - Page 2 preview image

Page 3 of 16

Solution Manual for Discrete Mathematics for Computer Scientists, 1st Edition - Page 3 preview image

Bogart-81046bookApril 27, 200517:12Problem 3SolutionThe set of possible draws is a union of 52 sets (one for each possible first card), eachof size 51. So, by the product principle, there are 52·51 ways to draw the two cards.Problem 4SolutionThe answer is the same as in Problem 3, except we can draw the cards in either order.Therefore, the number of ways is 52·51/2=1326.Problem 5Solution52·51·50, by two applications of the product principle.Problem 6Solution10·9=90.Problem 7Solution(102)=10·9/2=45.Problem 8Solution10·(92),or 8(102).Problem 9SolutionThis formula counts the number of ways to choose a president and an executiveadvisory board (not including the president) from a club ofnpeople. The left sidechooses the president first, then the committee. The right side chooses the committeefirst, then the president.Problem 10Solutionm·n.Problem 11SolutionBy the product rule, there are 10·9=90 ways to choose two-scoop cones withtwo different flavors. However, according to your mother’s rule, the order of scoopsdoesn’t matter. Because each two-scoop cone can be ordered in two different ways(e.g., chocolate over vanilla and vanilla over chocolate), we have 90/2=45 ways ofchoosing two-scoop cones with different flavors. There are an additional ten coneswith the same flavor for both scoops, giving 55 possible cones.S2Chapter 1:Counting

Page 4 of 16

Solution Manual for Discrete Mathematics for Computer Scientists, 1st Edition - Page 4 preview image

Bogart-81046bookApril 27, 200517:12Problem 12SolutionBecause order does matter, we have 10·9=90 ways to choose ice cream coneswith two distinct flavors, plus ten more with the same flavor for both scoops, giving100 choices.Problem 13Solution1+2+4+ · · · +219=220−1=1,048,575. Your justification may be neitherprinciple, only the sum principle (the set of all pennies is the union of the set of pennieson Day 1 with those on Day 2, and so on), or both principles (the set of penniesyou receive on Dayiis the union of two sets of pennies, each of the size that youreceived on Dayi−1). As long as your explanation makes sense, any of theseanswers is fine.Problem 14Solution5·3·3·3=135.Problem 15SolutionYes; in Line 4,jcould start ati+1 rather thani.1.2COUNTING LISTS, PERMUTATIONS, AND SUBSETSPages 17 to 19Problem 1SolutionFor each piece of fruit, we havenchoices of who to give it to. So, by version 2 of theproduct principle, the number of ways to pass out the fruit isnk.Problem 2Solutionf1(1)=af1(2)=af1(3)=af2(1)=af2(2)=af2(3)=bf3(1)=af3(2)=bf3(3)=af4(1)=af4(2)=bf4(3)=bf5(1)=bf5(2)=af5(3)=af6(1)=bf6(2)=af6(3)=bf7(1)=bf7(2)=bf7(3)=af8(1)=bf8(2)=bf8(3)=bNone are one-to-one; all butf1andf8are onto.1.2:Counting Lists, Permutations, and SubsetsS3

Page 5 of 16

Solution Manual for Discrete Mathematics for Computer Scientists, 1st Edition - Page 5 preview image

Bogart-81046bookApril 27, 200517:12Problem 3Solutionf1(1)=af1(2)=af2(1)=af2(2)=bf3(1)=af3(2)=cf4(1)=bf4(2)=af5(1)=bf5(2)=bf6(1)=bf6(2)=cf7(1)=cf7(2)=af8(1)=cf8(2)=bf9(1)=cf9(2)=cNone of the functions are onto; all exceptf1,f5, andf9are one-to-one.Problem 4SolutionIf we listSasx1,x2, . . . ,xs, then there is a bijection between functions fromStoTand listsf(x1),f(x2), . . . ,f(xs). For eachi, there aretchoices forf(xi). So, by theproduct principle, there aretsfunctions fromStoT.Problem 5SolutionWe are asking for the number ofk-element permutations ofnchildren, which isnk,or zero, ifk>n.Problem 6SolutionWhat matters is what subset of thenchildren get fruit, so the answer is(nk). Ifk>n,the answer is zero.Problem 7SolutionFirst, note that “a five-digit base 10 number” means a string of five digits, where thefirst digit is not 0 and each digit is in the set{0,1, . . . ,9}. By the product rule, thenumber of these is 9·104, or 90,000. If no two consecutive digits can be equal, thenthere are nine choices for the first digit, nine for the second (any digit other than thefirst), nine for the third (any digit other than the second), and so on. By the productprinciple, the total number is 95.By the sum principle, the total number of five-digit numbers equals the number thathave no two consecutive digits equal plus the number that have at least one pair ofconsecutive digits equal. Thus, lettingxdenote the number of the latter, we have9·104=95+x; so,x=9·104−95=30,951.S4Chapter 1:Counting

Page 6 of 16

Solution Manual for Discrete Mathematics for Computer Scientists, 1st Edition - Page 6 preview image

Bogart-81046bookApril 27, 200517:12Problem 8SolutionIn both cases, there are two ways to decide whether the leftmost spot is for a studentor for an administrator. This decision determines which four places are for studentsand which are for administrators. Thus, there are 4! ways to assign the students totheir places and 4! ways to assign the administrators to their places. In both cases, theproduct principle leads us to conclude that there are 2·4!·4! lists.Problem 9Solution123124125132134135142143145152153154213214215231234235241243245251253254312314315321324325341342345351352354412413415421423425431432435451452453512513514521523524531532534541542543Six permutations correspond to any given three-element set. We have 60 permutations,so there are 10 three-element sets.Problem 10Solution(203)=20·19·18/6=1140.Problem 11Solution(104)(204).Problem 12Solution2(104)(204)4!4!=2·104204.Problem 13SolutionWhen both scoops have the same flavor, we have 10 possibilities, because there are only10 flavors. When the scoops have different flavors, we have 45 possibilities, accordingto your mother’s rule, as solved before. So, for ice cream, we have 10+45=55possibilities. For topping, we have 3 possibilities. For whipped cream, nuts, and cherry,because we may either have any, all, or none, we have 2 possibilities for each of them(for example, either have cherry or don’t have cherry). By the product rule, we have2·2·2=8 possibilities. Thus, we have 55·3·8=1320 possible sundaes.1.2:Counting Lists, Permutations, and SubsetsS5

Page 7 of 16

Solution Manual for Discrete Mathematics for Computer Scientists, 1st Edition - Page 7 preview image

Bogart-81046bookApril 27, 200517:12Problem 14SolutionAlthough this problem is similar to Problem 13, we may have three different flavors(there are 10·9·8/6=2880 ways to choose three flavors), two scoops of one flavorand one of a second (there are 10·9=90 ways to do this), or three scoops of the sameflavor (there are 10 ways to choose these). Thus, we have 220·3·8=5280 differentsundaes.Problem 15SolutionSuppose we list the people in the club in some way and keep that list for the remainderof the problem. Take the first person from the list and pair that person with any of the2n−1 remaining people. Now take the nextunpairedperson from the list and pairthat person with any of the remaining 2n−3 unpaired people. Continuing in this way,oncekpairs have been selected, take the next unpaired person from the list and pairthat person with any of the remaining 2n−2k−1 unpaired people. Every pairing canarise in this way, and no pairing can arise twice in this process. Thus, the number ofoutcomes is∏n−1i=02n−2i−1. For another solution, choose people in pairs. There are(2n2)ways to choose one pair,(2n−22)ways to choose a second pair, and oncekpairshave been chosen, there are(2n−2k2)ways to choose the next pair. The number oflistsof pairs we get in this way is∏n−1i=0(2n−2i2)=(2n)!2i. Both ways of pairing people getslistedn! times because we see all possible lists of pairs of lengthn. Therefore, thenumber of actual pairings is(2n)!(2n)n!=2n!2n·2n−2·2n−4·· · ··2=n−1∏i=0(2n−2i−1) .For the second question, multiply the answer to the first question by 2nto give(2n)!/n!.Problem 16Solution(125).(52)(42)(31)=180.(52)(42)(11)+(52)(52)(21)—that is, either the versatileplayer is playing center or not; if not, that player is available to play forward.Problem 17SolutionIffis one-to-one, it hasndistinct values. Therefore, all elements of the range mustbe values off, so it must be onto. Thus, a one-to-one function from ann-element setto ann-element set is onto. If we now suppose thatfis onto, thenfhasndistinctvalues because it maps onto a set of sizen. But in this case, we may conclude thatbecause there are onlynvalues ofx, all the values off(x)are different. Therefore,fmust be one-to-one.S6Chapter 1:Counting

Page 8 of 16

Solution Manual for Discrete Mathematics for Computer Scientists, 1st Edition - Page 8 preview image

Bogart-81046bookApril 27, 200517:12Problem 18Solutiona. Iffis a bijection, we may defineg(y)to be the uniquexsuch thatf(x)=y.This defines a function because different values ofyare related to differentvalues ofx. But thenf(g(y))is the result of applyingfto the uniquexwithf(x)=y, sof(g(y))=y. Also,g(f(x))is the uniquexthat is related tof(x),sog(f(x))=x. This shows that iffis a bijection, thenfhas aninverse function. On the other hand, iffhas an inverse functiongand iff(x)=f(x′), theng(f(x))=g(f(x′)), which gives usx=x′. Therefore, iffhas an inverse function, thenfis one-to-one. Further, iffhas an inversefunctiong, then becausey=f(g(y))andg(y)is in the domain off, there isanxin the domain off(namely,g(y)) such thatf(x)=y; so,fis onto.b. Supposegandhboth satisfy the definition of being inverses tof. Supposeyis in the range offandg(y)=x. Then,f(g(y))=f(x)andh(f(g(y)))=h(f(x))=x. Becausef(g(y))=y, we haveh(y)=xas well.Thus, for anyyin the range off,h(y)=g(y), which means thatgandhareequal. Thus,fhas only one inverse function.1.3BINOMIAL COEFFICIENTSPages 26 to 28Problem 1Solution220, 220.(nk)equals(nn−k).Problem 2Solution1 8 28 56 70 56 28 8 1Problem 3Solutiona.(x+1)5=x5+5x4+10x3+10x2+5x+1.b.(x+y)5=x5+5x4y+10x3y2+10x2y3+5x y4+y5.c.(x+2)5=x5+10x4+40x3+80x2+80x+32.d.(x−1)5=x5−5x4+10x3−10x2+5x−1.Problem 4Solution(x+y)4=x4+(41)x3y1+(42)x2y2+(43)x1y3+y4. To expand the product, wecreate all possible products ofx’s andy’s by selectingyfrom some of the factors andxfrom the remaining ones. Then we add all these products. There is 1=(40)way tochoose ayfrom none of our fourx+yfactors. Thus, the coefficient ofx4is 1. There1.3:Binomial CoefficientsS7

Page 9 of 16

Solution Manual for Discrete Mathematics for Computer Scientists, 1st Edition - Page 9 preview image

Bogart-81046bookApril 27, 200517:12are(41)ways to choose ayfrom one of the four factors. Because we choosexfromthe remaining factors, this choice gives us the term(41)x3y. There are(42)ways tochooseyfrom two of our four factors, so the coefficient ofx2y2is(42). There are(43)ways to chooseyfrom three of our factors, so the coefficient ofx y3is(43). There is1=(44)way to chooseyfrom all the factors, so the coefficient ofy4is 1.Problem 5Solution10!/(3!3!4!)=4200. This is the number of ways to label three of the chairs with thelabel green, three of the chairs with the label blue, and four of the chairs with the labelred.Problem 6SolutionThemultinomialcoefficient(nn1,n2,...,nk)isthecoefficientofxn11xn22· · ·xnkkin(x1+x2+ · · · +xk)n. The proof is just like the proofs of the binomial theoremand the trinomial theorem.Problem 7SolutionIfNis a set andKis a subset ofN, letN−Kstand for the set of all elements ofNthat are not inK. Iff(K)=N−K, thenfis a bijection that maps thek-elementsubsets ofNonto the(n−k)-element subsets ofN.Problem 8Solution(m+nn)or(m+nm), because of the following:• From any line segment on our path, we have two choices: horizontal andvertical. Clearly, we neednvertical line segments andmhorizontal linesegments to reach(m,n)in exactlym+nsteps.• By deciding on our choice ofnvertical lines, we have also decided the choiceofmhorizontal lines, because we must choose a horizontal line for each stepthat is not a vertical line. We could also start by choosingmhorizontal lines,which automatically decides the choice ofnvertical lines. Thus, the numberof ways to choose the path is the number of ways to choose thenplaces forvertical lines fromm+nplaces or themplaces for horizontal lines fromm+nplaces.Problem 9Solution∑ni=0(ni)xiyn−i=yn+(n1)x yn−1+(n2)x2yn−2+ · · · +xn.S8Chapter 1:Counting

Page 10 of 16

Solution Manual for Discrete Mathematics for Computer Scientists, 1st Edition - Page 10 preview image

Bogart-81046bookApril 27, 200517:12Problem 10SolutionOnce we choose four disjoint subsets from a 12-element set, we may label them in 4!ways. That is, choosing the sets does not tell us which set to label with which label.Therefore, the number of choices of the four sets is the number of labelings dividedby 4!, namely,12!4!(3!)4. The number of ways to choose three disjoint subsets of size fourfrom a 12-element set is12!3!(4!)3.Problem 11SolutionFor the first case, the president may be chosen from 20 persons, and after that, the vicepresident may chosen from 19 persons, the secretary from 18 persons, and the treasurerfrom 17 persons. The nominations committee may be chosen from the remaining16 persons without order mattering. So, there are 20·19·18·17·(163)ways to choosethe committee. For the second case, the nominating committee may be chosen fromthe 20 persons without order mattering. So, there are 20·19·18·17·(203)ways tochoose the committee.Problem 12Solution(n−1k−1)+(n−1k)=(n−1)!(k−1)!(n−k)!+(n−1)!k!(n−k−1)!=(n−1)!k(k)!(n−k)!+(n−1)!(n−k)k!(n−k)!=(n−1)!(k+n−k)k!(n−k)!=n!k!(n−k)!=(nk).Problem 13SolutionProof 1:n!k!(n−k)!=n!(n−k)!k!.Proof 2: The number of ways to choose thekelements that are in ak-element subsetis the same as the number of ways to choose the elements that arenotin the subset,and there aren−ksuch elements.1.3:Binomial CoefficientsS9

Page 11 of 16

Solution Manual for Discrete Mathematics for Computer Scientists, 1st Edition - Page 11 preview image

Bogart-81046bookApril 27, 200517:12Problem 14SolutionProof 1:(nk) (kj)=n!k!(n−k)!k!j!(k−j)!=n!(n−k)!j!(k−j)!=n!j!(n−j)!(n−j)!(k−j)!(n−k)!=(nj) (n−jk−j).Proof 2: The number of ways to choosekitems fromnitems and then choosejitemsfrom the chosenkitems is(nk)(kj). We can also carry out this process in the followingway: First choosejitems fromnitems, and then choosek−jmore items from theremainingn−jitems. The number of ways to do this is(nj)(n−jk−j).Problem 15SolutionProof 1:(nk) (n−kj)=n!(n−k)!k!(n−k)!j!(n−k−j!)=n!k!j!(n−k−j)!.Similarly,(nk)(n−kj)equals the same expression.Proof 2: There are two ways of choosing two disjoint sets, one withkelements andone withjelements. We can pick thek-element set first, then choosejelements fromwhat is left, or we can pick thej-element set first, then choosekelements from whatis left.Problem 16Solutionn k3456620156173521785628984Problem 17SolutionThe formula is simply the expansion of(1−1)n.S10Chapter 1:Counting

Page 12 of 16

Solution Manual for Discrete Mathematics for Computer Scientists, 1st Edition - Page 12 preview image

Bogart-81046bookApril 27, 200517:12Problem 18Solution(1+x)n=∑ni=0(ni)xi. Taking the derivative of both sides, we getn(1+x)n−1=n∑i=1i(ni)xi−1.Thus, if we letx=1, we haven2n−1=∑ni=1i(ni).Problem 19SolutionFalse.(42)is 6, but(20)+(21)+(22)is 4. The correct statement is(nk)=(n−2k−2)+2(n−2k−1)+(n−2k).The proof consists of applying the Pascal relationship to both(n−1k−1)and(n−1k)andadding the results.1.4EQUIVALENCE RELATIONS AND COUNTINGPages 38 to 41Problem 1Solution(n−1)! ways.Problem 2SolutionIf we rotate a scarf through 180 degrees, we do not change the scarf, but we do getthe reversed row of circles. Thus, two arrangements ofncircles are equivalent if oneis the reverse of the other. The equivalence classes have two members, so the numberof ways to embroider the circles on the scarf isn!/2.Problem 3SolutionThere are(52)=10 ways to choose the two places out of five in which the goldenapples are placed. For equivalence class counting, there are 5! ways to line up theapples. Two ways are equivalent if we interchange the golden apples or mix up the redapples in any way. Thus, there are 2·3! arrangements per equivalence class. Therefore,there are 5!/(2·3!)equivalence classes. This means that there are 5!/(2·3!)ways toline up the apples. Note that the second answer is simply the usual formula for thefirst answer.1.4:Equivalence Relations and CountingS11

Page 13 of 16

Solution Manual for Discrete Mathematics for Computer Scientists, 1st Edition - Page 13 preview image

Bogart-81046bookApril 27, 200517:12Problem 4SolutionPassing out the apples corresponds to choosing ak-element multiset from thenchil-dren. Choosing ak-element multiset from the children tells us how many apples togive each child. Thus, there are(n+k−1k)ways to pass out the apples.Problem 5SolutionNumber the places around the table consecutively from 1 to 2n. A seating gives a listof the 2npeople. Once we decide the gender of the person in Seat 1, we haven! waysto seat that gender andn! ways to seat the other gender. By the product principle, wehave 2·n!·n! lists of people corresponding to seating arrangements. But there are 2nlists that correspond to the same circular arrangement. Therefore, the number of waysto seat the people is 2n!n!/2n=n!(n−1)!.Another way is to seat one gender in(n−1)! ways and then seat the other genderin thenplaces between members of the first group inn! ways. Then, by the productprinciple, we have(n−1)!n! seating arrangements.Problem 6SolutionGive one apple to each child. Then pass outk−napples to the children in(n+k−n−1k−n)=(k−1k−n)ways.Problem 7SolutionSelectkbooks in(nk)ways, and place one on the far left of each shelf inn! ways.Then shelve the remainingk−nbooks innk−nways. This gives(kn)n!nk−n=k!(k−1)!(k−n)!(n−1)!ways to shelve all the books.Problem 8Solutiona.(k+n−1k), or the number of ways to choose the places where the red checkersgo. This is also the way to putkidentical books andn−1 identical blocksof wood in a line, because it is the number of ways to choose where thebooks (or the blocks of wood) go.b. The number of red checkers between black checker numberi−1 and blackchecker numberi(or before black checker number 1) is the multiplicity ofi(or 1). The number of red checkers after the last black checker is themultiplicity of black checkern.S12Chapter 1:Counting

Page 14 of 16

Solution Manual for Discrete Mathematics for Computer Scientists, 1st Edition - Page 14 preview image

Bogart-81046bookApril 27, 200517:12c. Parts a and b count the same thing, so the number ofk-element multisetschosen from ann-element set is(n+k−1k).Problem 9SolutionIf you think of the value ofxias the multiplicity ofiin a multiset, then the number ofsolutions is the number of multisets,(n+k−1k).Problem 10SolutionIf you think ofxias the multiplicity ofiin a multiset, then you are counting thenumber ofk-element multisets chosen from{1,2, . . . ,n}in which every element hasmultiplicity at least 1. This is the same as the number ofk−nelement multisets of{1,2, . . . ,n}, which is(k−1k−n). To see why this is the answer, think of givingkidenticalapples tonchildren. Give each child one apple and then distribute the remainingk−napples however you want.Problem 11SolutionImagine this circular arrangement as a linear arrangement. If both thenred checkersand then+1 black checkers were distinguishable, there would be(n+n+1)!=(2n+1)! possible linear arrangements. When we think of the red checkers (andthe black ones) as indistinguishable, we haven!(n+1)! lists per equivalence class,because these lists would be equivalent if we mixednred checkers among themselvesandn+1 black checkers among themselves. Each linear arrangement ofnred andn+1 black checkers corresponds to 2n+1 other arrangements, which becomeidentical when we put them into a circle. (This would not be the case if we hadnred andnblack checkers; think about alternating red and black.) So, the number ofarrangements is(2n+1)!(2n+1)n!(n+1)!=(2n)!n!(n+1)!=1n+1(2nn).Problem 12Solutiona. ForS(n,n), each element must be in a part by itself. There is one suchpartition, soS(n,n)=1. ForS(n,1), every element must be in the same part,soS(n,1)=1.b. An elementamay be in a part by itself or not. The number of partitions inwhichais in a part by itself isS(n−1,k−1), because then we have to chooseremainingk−1 parts from remainingn−1 elements. Otherwiseais in a partwith other elements. Becauseacan be in any of thekparts and the othern−1elements may be partitioned intokparts inS(n−1,k)ways, we have1.4:Equivalence Relations and CountingS13

Page 15 of 16

Solution Manual for Discrete Mathematics for Computer Scientists, 1st Edition - Page 15 preview image

Bogart-81046bookApril 27, 200517:12k S(n−1,k)partitions of this type. By the sum principle, we getS(n,k)=S(n−1,k−1)+k S(n−1,k).c.n k1234561121131314176151152510161319065151Problem 13SolutionThere are six lists of four letters: you can make a list by choosing two of the fourplaces for the red beads in(42)=6 ways. The equivalence classes are{RRBB,RBBR,BBRR,BRRB}and{RBRB,BRBR}. Because the sizes of the equivalence classes arenot the same, you cannot apply Theorem 1.5.Problem 14Solutiona. “Greater than” is transitive. “Is a brother of” is not transitive (Paul can be abrother to Bob and Bob to Paul, but Paul is not a brother to Paul). “Is a siblingof” is not transitive but is symmetric. “Is a sibling of or is” is transitive,symmetric, and reflexive.b.xis in the same equivalence class asx, so it is reflexive. Ifxis in the sameequivalence class asy, thenyis in the same equivalence class asx. Therefore,it is symmetric. Ifxis in the same equivalence class asyandyis in the sameequivalence class asz, thenxis in the same equivalence class asz. Therefore,it is transitive.c. IfSxandSyhave a common element, such asa, then we have thatais relatedto bothxandy. We also have thatyis related toaby symmetry. For anyelementbinSy, we havebis related toy. Thenbis related toaby transitivityand related toxagain by transitivity. Thus, we haveb∈Sx, which shows thatSy⊆Sx. Similarly, we haveSx⊆Sy. Therefore, we haveSx=Sy. Thus, ifSxandSyhave a common element, they are identical. IfSxandSyhave nocommon element, they are disjoint. Therefore, we can use the relationship todivideSinto disjoint sets: the setsSx. Note that by reflexivity, any elementxisin the setSx. Thus, a reflexive symmetric transitive relation is an equivalencerelation.d. Part b says that an equivalence relation, as defined in the text, is reflexive,symmetric, and transitive. Part c says that a reflexive, symmetric, and transitiverelation is an equivalence relation, as was defined in the text.S14Chapter 1:Counting

Page 16 of 16

Solution Manual for Discrete Mathematics for Computer Scientists, 1st Edition - Page 16 preview image

Bogart-81046bookApril 27, 200517:12Problem 15SolutionThe original version computes the entire Pascal triangle up to the element in rownand columnkeach time it is called. Your new version should store that informationglobally so that it only has to do one addition each time it computes a new value inPascal’s triangle.Problem 16Solutiona. This problem asks you to count functions from the candy to the people, sothe answer isnk.b. This asks for one-to-one functions from the candy to the people, so theanswer isnk. Note how the notation for counting one-to-one functions issimilar to the notation for counting functions.c. A distribution is equivalent to ak-element multiset of then-element set ofpeople. Thus, there are(n+k−1k)distributions.d. This asks fork-element subsets of thenpeople, so the answer is(nk).e. This is the number ofk-element permutations of thenobjects, so the answerisnk.f. Because you are counting functions, the answer isnk.g. By definition,(nk).h. By the theorem for counting multisets,(n+k−1k).i. This is asking for the number of lists ofkdistinct people chosen out ofn.Such a list is ak-element permutation of thenelements, so the answer isnk.j. This is asking for the number ofk-element multisets of ann-element set,and this number is(n+k−1k).k. Because it matters who gets which type, this is the same as asking howmany one-to-one functions there are from ak-element set to ann-elementset. Thus, the answer isnk.1.4:Equivalence Relations and CountingS15

Preview Mode

This document has 145 pages. Sign in to access the full document!

Report

Learning Tools

Writing Tools

Browse Resources

Solution Manual for Discrete Mathematics for Computer Scientists, 1st Edition - Page 1

Study Now!

Document Details

Related Documents

Precalculus - Polynomial and Rational Functions

Precalculus - Functions

Precalculus - Exponential and Logarithmic Functions

Math Word Problems - Translating Expressions

Math Word Problems - Equations

Algebra II – Word Problems

Algebra II – Sequences and Series

Algebra II - Segments Lines and Inequalities

Algebra II - Relations and Functions

Algebra II - Rational Expressions

Company

Explore

Study Tools