
# Appendix D: Hints to Selected Problems


1. Answer the questions in Problem 2 for the case of five schools.

3. For each kind of bread, how many sandwiches are possible?

6. Try to solve the problem first with a two-scoop cone. (Look for an earlier problem that is analogous.) Then, for each two scoop cone, in how many ways can you put on a top scoop?

7a. Ask yourself “how many choices do we have for $$f(1)$$?” Then ask how many choices we have for $$f(2)$$.

7b. It may not be practical to write down rules for all the functions for this problem. But you could ask yourself how many choices we have for $$f(1)$$, how many we have for $$f(2)$$ and how many we have for $$f(3)$$.

7c. If you are choosing a function $$f$$, how many choices do you have for $$f(a)$$? Then how many choices do you have for $$f(b)$$?

8a. You know how to figure out in how many ways they could make a list of three flavors out of the twelve. But each set of three flavors can be listed in a number of different ways. Try to figure out in how many ways a set of three flavors can be listed, and then try to see how this helps you.

8b. Try to break the problem up into cases you can solve by previous methods; then figure out how to get the answer to the problem by using these answers for the cases.

12a. Suppose you have a list in alphabetical order of names of the members of the club. In how many ways can you pair up the first person on the list? In how many ways can you pair up the next person who isn’t already paired up?

15. In how many ways may you assign the men to their rows? The women? Once a woman and a man have a row to share, in how many ways may they choose their seats?

18. Try applying the product principle in the case $$n = 2$$ and $$n = 3$$. How might you apply it in general?

19. Ask yourself if either the sum principle or product principle applies. Additional Hint: Remember that zero is a number.

20. Do you see an analogy between this problem and any of the previous problems?

26a. For each part of this problem, think about how many arrows are allowed to enter a vertex representing a member of $$Y$$.

28. The problem is asking you to describe a one-to-one function from the set of binary representations of numbers between $$0$$ and $$2n−1$$ onto the set of subsets of the set $$[n]$$. Write down these two sets for $$n = 2$$. They should both have four elements. The set of binary representations should contain the string $$00$$. You could think of this as the instruction “take no ones and take no twos.” In that context, what could you think of the string $$11$$ as standing for? This should help you describe a function. Of course now you have to figure out how to show it is one-to-one and onto.

31. Starting with the row $$1 \;\;8 \;\;28 \;\;56 \;\;70\;\; 56\;\; 28\;\; 8\;\; 1$$, put dots below it where the elements of row 9 should be. Then put dots below that where the elements of row 10 should be. Do the same for rows 11 and 12. Mark the dot where row 12 should appear. Now mark the dots you need in row 11 to compute the entry in column 3 of row 12. Now mark the dots you need in row 10 to compute the marked entries in row 11. Do the same for rows 9 and 8. Now you should be able to see what you need to do.

32a. Begin by trying to figure out what the entries just above the diagonal of the rectangle are. After that, what other entries can you figure out?

32b. See if you can figure out what the entries in column −1 have to be.

32c. What does the sum of two consecutive values in row −1 have to be? Could this sum depend on which two consecutive values we take? Is there some value of row −1 that we could choose arbitrarily? Now what about row −2? Can we make arbitrary choices there? If so, how many can we make, and is their position arbitrary?

36. The first thing you need to decide is “What are the two sets whose elements we are counting?” Then it will be easier to think of a bĳection between these two sets. It turns out that these two sets are sets of sets!

37. Ask yourself “What is a problem like this doing in the middle of a bunch of problems about counting subsets of a set? Is it related, or is it supposed to gives us a break from sets?”

38. The problem suggests that you think about how to get a list from a seating arrangement. Could every list of $$n$$ distinct people come from a seating chart? How many lists of $$n$$ distinct people are there? How many lists could we get from a given seating chart by taking different starting places? Additional Hint: For a different way of doing the problem, suppose that you have chosen one person, say the first one in a list of the people in alphabetical order by name. Now seat that person. Does it matter where they sit? In ways can you seat the remaining people? Does it matter where the second person in alphabetical order sits?

39a. A block consists of all permutations of some subset $$\{a_1, a_2,..., a_k \}$$ of $$S$$. How many permutations are there of the set $$\{a_1, a_2,..., a_k \}$$?

39c. What sets are listed, and how many times is each one listed if you take one list from each row of Table 1.2.8? How does this choice of lists give you the bĳection in this special case?

39d. You can make good use of the product principle here.

40b. The coach is making a sequence of decisions. Can you figure out how many choices the coach has for each decision in the sequence?

40c. As with any counting problem whose context does not suggest an approach, it is useful to ask yourself if you could decompose the problem into simpler parts by using either the sum or product principle.

43. How could we get a list of beads from a necklace? Additional Hint: When we cut the necklace and string it out on a table, there are $$2n$$ lists of beads we could get. Why is it $$2n$$ rather than $$n$$?

44a. You might first choose the pairs of people. You might also choose to make a list of all the people and then take them by twos from the list.

44b. You might first choose ordered pairs of people, and have the first person in each pair serve first. You might also choose to make a list of all the people and then take them by twos from the list in order.

45. It might be helpful to just draw some pictures of the possible configurations. There aren’t that many.

47. Note that we must walk at least ten blocks, so ten is the smallest number of blocks possible. In how many of those ten blocks must we walk north?

48b. In Problem 47 you saw that we had to make ten choices of north or east, choosing north four times.

48c. This problem is actually a bit tricky. What happens to the answer if $$i > m$$ or $$j > n$$? Remember that paths go up or to the right.

49a. Where can you go from $$(0,0)$$ in one step? In two steps? In any of these cases, what can you say about the sum of the coordinates of a point you can get to? Can you find any other relationship between the $$x$$- and $$y$$-coordinates of a point you can get to? For example, can you get to the point $$(1, 3)$$?

49c. How many choices do you have to make in order to choose a path?

50c. In each part, each such sequence corresponds to a path that can’t cross over (but may touch) a certain line.

51b. Given a path from $$(0, 0)$$ to $$(n, n)$$ which touches or crosses the line $$y = x + 1$$, how can you modify the part of the path from $$(0, 0)$$ to the first touch of $$y = x + 1$$ so that the modified path starts instead at $$(−1, 1)$$? The trick is to do this in a systematic way that will give you your bĳection.

51c. A path either touches the line $$y = x + 1$$ or it doesn’t. This partitions the set of paths into two blocks.

52b. Look back at the definition of a Dyck Path and a Catalan Path.

52c. What makes this part difficult is understanding how we are partitioning the paths. As an example, $$B_0$$ is the set of all paths that have no upsteps following the last absolute minimum. Can such a path have downsteps after the last absolute minimum? (The description we gave of $$B_0$$ is not succinct enough to be the answer to the second question of this part.) As another example, $$B_1$$ is the set of all paths that have exactly one upstep and perhaps some downsteps after the last absolute minimum. Is it possible, though, for a path in $$B_1$$ to have any downsteps after the last absolute minimum? A path in $$B_2$$ has exactly two upsteps after its last absolute minimum. If is possible to have one downstep after the last absolute minimum, but it has to be in a special place. What place is that? Now to figure out how many parts our partition has, we need to know the maximum number of upsteps a path can have following its last absolute minimum. What is this maximum? It might help to draw some pictures with $$n = 5$$ or $$6$$. In particular, is it possible that all upsteps occur after the last absolute minimum?

52e. Using d for down and u for up, we could have $$u\;u\;d\;d\;u\;u\;d\;d\;u\;d\;u\;d$$ as our Catalan path. Suppose that $$i = 5$$. The fifth upstep is the $$u$$ in position 9. Thus $$F = u\;u\;d\;d\;u\;u\;d\;d$$, $$U = u$$, and $$B = d\;u\;d$$. Now $$BUF$$ is $$d\;u\;d\;u\;u\;u\;d\;d\;u\;u\;d\;d$$. This is a Dyck path that begins by going below the $$x$$-axis. The $$d$$’s in positions 1 and 3 take the path to the $$y$$-coordinate $$−1$$. Then the $$y$$ coordinate climbs to $$2$$, goes back to $$0$$, up to $$2$$ again, and finally down to $$0$$. So the absolute minimum is $$−1$$, and it occurs in the first and third position. There are five $$u$$’s after the third position. So this Dyck path is in the block $$B_5$$ of our partition. Now comes the crucial question. Why were there five $$u$$’s after that last absolute minimum in position 3? Try with the same path and $$i = 3$$. Figure out why there are three $$u$$’s after the last absolute minimum in the resulting path. All this discussion should explain why when $$i = 5$$, the set of all Catalan paths is mapped into the set $$B_5$$. Keeping $$i = 5$$ for a while, try to see why this correspondence between Catalan paths and $$B_5$$ is a bĳection. Then, if you need to, do the same thing with $$i = 3$$. This should give you enough insight to do the general case.

55. What would the lower limit of the sum have to be for this problem to be a routine application of the binomial theorem?

56. What does the binomial theorem give you for $$(x − y)^n$$?

57. Consider $$(x + y)^m(x + y)^n$$. Additional Hint: What does $$\binom{m+n}{k}$$ count? What does $$\binom{m}{i} \binom{m}{k-1}$$ count?

58. For example when $$n = 3$$, we have $$\binom{3}{0} = \binom{3}{3}$$ and $$\binom{3}{1} = \binom{3}{2}$$. The number of subsets of even size is $$\binom{3}{0} + \binom{3}{2}$$ and the number of subsets of odd size is $$\binom{3}{1} + \binom{3}{3}$$, and the two sums can be paired off into equal terms. When we subtract the number of subsets of odd size from the number of subsets of even size, the pairing also gives us $$\binom{3}{0} - \binom{3}{1} + \binom{3}{2} - \binom{3}{3} = 0$$.

59. Take the derivative of something interesting.

61. To prove that each function from a set $$S$$ of size $$n$$ to a set of size less than $$n$$ is not one-to-one, we must prove that regardless of the function $$f$$ that we choose, there are always two elements, say $$x$$ and $$y$$, such that $$f(x) = f(y)$$.

62. The previous exercise could help you prove that if $$f$$ is one-to-one, then it is onto. Additional Hint: The sum principle can help you show that if $$f$$ is an onto function, then $$f$$ is one-to-one.

63. The statement of the generalized pigeonhole principle involves the number of elements in a block, so a counting principle is likely to help you.

64. You may choose a specific number for $$n$$ if you want to. Notice that the last two digits of the powers of a prime other than two cannot represent an even number.

65. While this sounds like a pigeonhole principle problem, the ordinary pigeonhole principle doesn’t guarantee three of something.

67. What usually makes it hard for students to start this problem is the fact that we just defined what $$R(4, 4)$$ is, and not what it means for a number not to be $$R(4, 4)$$. So to get started, try to write down what it means to say $$R(4, 4)$$ is not $$8$$. You will see that there are two things that can keep $$R(4, 4)$$ from being $$8$$. You need to figure out which one happens and explain why. One such explanation could involve the graph $$K_8$$.

68. Review Problem 65 and your solution of it.

69. Let $$a_i$$ be the number of acquaintances of person $$i$$. Can you explain why the sum of the numbers $$a_i$$ is even?

70. Often when there is a counter-example, there is one with a good deal of symmetry. (Caution: there is a difference between often and always!) One way to help yourself get a symmetric example, if there is one, is to put $$8$$ vertices into a circle. Then, perhaps, you might draw green edges in some sort of regular fashion until it is impossible to draw another green edge between any two of the vertices without creating a green triangle.

71. In Problem 68 you showed that $$R(4, 3) ≤ 10$$. In Problem 70 you showed that $$R(4, 3) > 8$$. Thus $$R(4, 3)$$ is either $$9$$ or $$10$$. Deciding which is the case is just plain hard. But there is a relevant problem we have done that we haven’t used yet.

72. We wish to prove that $$\binom{n}{i} = \dfrac{n!}{i!(n−i)!}$$. Mathematical induction allows us to assume that $$\binom{n-1}{j} = \dfrac{(n−1)!}{j!(n−1−j)!}$$ for every $$j$$ between $$0$$ and $$n − 1$$. How does this put us into a position to use the Pascal relation? What special cases will be left over?

73. What sort of relationship do you know between values of the form $$\binom{n}{i}$$ and values of the form $$\binom{n−1}{j}$$?

75. We did something rather similar in our example of the inductive proof that a set with $$n$$ elements has $$2n$$ subsets. The work you did in a previous problem may be similar to part of what you need to do here.

76a. This may look difficult because one can’t decide in advance on whether to try to induct on $$m$$, on $$n$$, or on their sum. In some sense, it doesn’t matter which you choose to induct on, though inducting on the sum would look more complicated. For most people inducting on n fits their way of working with exponents best.

76b. Here it matters whether you choose to induct on $$m$$ or $$n$$. However, it matters only in the sense that you need to use more tools in one case. In one case, you are likely to need the rule $$(cd)^n = c^n d^n$$, which we haven’t proved. (However, you might be able to prove that by induction!) In either case, you may find part (a) handy

79. We didn’t explicitly say to use induction here, but, especially in this context, induction is a natural tool to try here. But we don’t have a variable $$n$$ to induct on. That means you have to choose one. So what do you think is most useful. The number of blocks in the partition? The size of the first block of the partition? The size of the set we are partitioning? Or something else?

80. Think about how you might have gone from the number of double decker cones to the number of triple decker cones in Problem 6.

81. Perhaps the first thing one needs to ask is why proving that if there are $$\binom{m+n−2}{m−1}$$ people in a room, then there are either at least $$m$$ mutual acquaintances or at least $$n$$ mutual strangers proves that $$R(m, n)$$ exists. Can you see why this tells us that there is some number $$R$$ of people such that if $$R$$ people are in a room, then there are $$m$$ mutual acquaintances or $$n$$ mutual strangers? And why does that mean the Ramsey Number exists? Additional Hint: Naturally it should come as no surprise that you will use double induction, and you can use either form. As you think about how to use induction, the Pascal relation will come to mind. This suggests that you want to make assumptions involving $$\binom{m+n−3}{m−1}$$ people in a room, or $$\binom{m+n−3}{m−2}$$ people in a room. Now you have to figure out what these assumptions are and how they help you prove the result! Recall that we have made progress before by choosing one person and asking whether this person is acquainted with at least some number of people or unacquainted with at least some other number of people.

82. One expects to need double induction again here. But only because of the location of the problem and because the sum looks like double induction. And those reasons aren’t enough to mean you have to use double induction. If you had this result in hand already, then you could us it with double induction to give a second proof that Ramsey Numbers exist. Additional Hint: What you do need to show is that if there are $$R(m −1, n) + R(m, n−1)$$ people in a room, then there are either m mutual acquaintances or n mutual strangers. As with earlier problems, it helps to start with a person and think about the number of people with whom this person is acquainted or nonacquainted. The generalized pigeonhole principle tells you something about these numbers.

83b. If you could find four mutual acquaintances, you could assume person 1 is among them. And by the generalized pigeonhole principle and symmetry, so are two of the people to the first, second, fourth and eighth to the right. Now there are lots of possibilities for that fourth person. You now have the hard work of using symmetry and the definition of who is acquainted with whom to eliminate all possible combinations of four people. Then you have to think about nonacquaintances.

86a. What is the definition of $$R(n, n)$$?

86b. If you average a bunch of numbers and each one is bigger than one, what can you say about the average?

86c. Note that there are $$2^{\binom{n}{2}}$$ graphs on a set of $$n$$ vertices.

86d. A notation for the sum over all colorings $$c$$ of $$K_m$$ is

$$\sum_{c:c \text{ is a coloring of } K_m} ,$$

and a notation for the sum over all subsets $$N$$ of $$M$$ that have size $$n$$ is

$$\sum_{N:N⊆M, |N|=n}$$

86e. If you interchange the order of summation so that you sum over subsets first and colorings second, you can take advantage of the fact that for a fixed subset $$N$$, you can count count the number of colorings in which it is monochromatic.

86f. You have an inequality involving $$m$$ and $$n$$ that tells you that $$R(n, n) > m$$. Suppose you could work with that inequality in order to show that if the inequality holds, then $$m$$ is bigger than something. What could you conclude about $$R(n, n)$$?

87. Remember, a subset of $$[n]$$ either does or doesn’t contain $$n$$.

90b. A first order recurrence for $$a_n$$ gives us $$a_n$$ as a function of $$a_{n−1}$$.

91. Suppose you already knew the number of moves needed to solve the puzzle with $$n − 1$$ rings.

92. If we have $$n −1$$ circles drawn in such a way that they define $$r_{n−1}$$ regions, and we draw a new circle, each time it crosses another circle, except for the last time, it finishes dividing one region into two parts and starts dividing a new region into two parts. Additional Hint: Compare $$r_n$$ with the number of subsets of an $$n$$-element set.

98. You might try working out the cases $$n = 2, 3, 4$$ and then look for a pattern. Alternately, you could write $$a_{n−1} = ba_{n−2} + d$$, substitute the right hand side of this expression into $$a_n = ba_{n−1} + d$$ to get a recurrence involving only $$a_{n−2}$$, and then repeat a similar process with $$a_{n−2}$$ and perhaps $$a_{n−3}$$ and see a pattern that is developing.

102a. There are several ways to see how to do this problem. One is to draw pictures of graphs with one edge, two edges, three edges, perhaps four edges and figure out the sum of the degrees. Another is to ask what deleting an edge does to the sum of the degrees. Another is to ask what a given edge “contributes” to the sum of the degrees.

102b. To make your inductive step, think about what happens to a graph if you delete an edge.

102d. Suppose that instead of summing the degree of $$v$$ over all vertices $$v$$, you sum some quantity defined for each edge $$e$$ over all the edges.

103. Whatever you say should be consistent with what you already know about degrees of vertices.

108. What happens if you choose an edge and delete it, but not its endpoints?

109. One approach to the problem is to use facts that we already know about degrees, vertices and edges. Another approach is to try deleting an edge from a tree with more than one vertex and analyze the possible numbers of vertices of degree one in what is left over.

111. When you get to four and especially five vertices, draw all the unlabeled trees you can think of, and then figure out in how many different ways you can put labels on the vertices.

112b. Do some examples.

112c. Is it possible for $$a_1$$ to be equal to one of the $$b_j$$s?

112d. You have seen that the sequence $$b$$ determines $$a_1$$. Does it determine any other $$a_j$$s? If you knew all the $$a_j$$s and all the $$b_j$$s, could you reconstruct the tree? What are the possible values of $$b_1$$? $$b_j$$?

113. What vertex or vertices in the sequence $$b_1, b_2,..., b_{n−1}$$ can have degree $$1$$?

115. If a vertex has degree $$1$$, how many times does it appear in the Prüfer code of the tree? What about a vertex of degree $$2$$?

116. How many vertices appear exactly once in the Prüfer code of the tree and how many appear exactly twice?

118. Think of selecting one edge of the tree at a time. Given that you have chosen some edges and have a graph whose connected components are trees, what is a good way to choose the next edge? To prove your method correct, use contradiction by assuming there is a spanning tree with lower total cost. Additional Hint: Think of selecting one edge of the tree at a time. But now do it in such a way that one connected component is a tree and the other connected components have just one vertex. What is a good way to make the component that is a tree into a tree with one more vertex? To prove your method works, use contradiction by assuming there is a spanning tree with lower total cost.

119a. If you have a spanning tree of $$G$$ that contains $$e$$, is the graph that results from that tree by contracting $$e$$ still a tree?

122c. If you decide to put it on a shelf that already has a book, you have two choices of where to put it on that shelf.

122e. Among all the places you could put books, on all the shelves, how many are to the immediate left of some book? How many other places are there?

123. How can you make sure that each shelf gets at least one book before you start the process described in Problem 122?

124. What is the relationship between the number of ways to distribute identical books and the number of ways to distribute distinct books?

125. Look for a relationship between a multiset of shelves and a way of distributing identical books to shelves

126. Note that $$\binom{n+k−1}{k} = \binom{n+k−1}{n−1}$$. So we have to figure out how choosing either $$k$$ elements or $$n − 1$$ elements out of $$n + k − 1$$ elements constitutes the choice of a multiset. We really have no idea what set of $$n + k − 1$$ objects to use, so why not use $$[n + k −1]$$? If we choose $$n −1$$ of these objects, there are $$k$$ left over, the same number as the number of elements of our multiset. Since our multiset is supposed to be chosen from an $$n$$-element set, perhaps we should let the $$n$$-element set be $$[n]$$. From our choice of $$n − 1$$ numbers, we have to decide on the multiplicity of $$1$$ through $$n$$. For example with $$n = 4$$ and $$k = 6$$, we have $$n + k − 1 = 9$$. Here, shown with underlines, is a selection of $$3 = n − 1$$ elements from $$[9]: 1, 2, \underline{3}, 4, \underline{5}, 6, 7, \underline{8}, 9$$. How do the underlined elements give us a multiset of size $$6$$ chosen from an $$[4]$$-element set? In this case, $$1$$ has multiplicity $$2$$, $$2$$ has multiplicity $$1$$, $$3$$ has multiplicity $$2$$, and $$4$$ has multiplicity $$1$$.

127. A solution to the equations assigns a nonnegative number to each of $$1, 2,...,m$$ so that the nonnegative numbers add to $$r$$. Does such an assignment have a combinatorial meaning?

128. Can you think of some way of guaranteeing that each recipient gets $$m$$ objects (assuming $$k ≥ m\;n$$) right at the beginning of the process of passing the objects out?

129. We already know how to place $$k$$ distinct books onto $$n$$ distinct shelves so that each shelf gets at least one. Suppose we replace the distinct books with identical ones. If we permute the distinct books before replacement, does that affect the final outcome? There are other ways to solve this problem.

130. Do you see a relationship between compositions and something else we have counted already?

131. If we line up $$k$$ identical books, how many adjacencies are there in between books?

133. Imagine taking a stack of $$k$$ books, and breaking it up into stacks to put into the boxes in the same order they were originally stacked. If you are going to use $$n$$ boxes, in how many places will you have to break the stack up into smaller stacks, and how many ways can you do this? Additional Hint: How many different bookcase arrangements correspond to the same way of stacking $$k$$ books into n boxes so that each box has at least one book?

134. The number of partitions of $$[k]$$ into $$n$$ parts in which $$k$$ is not in a block relates to the number of partitions of $$k − 1$$ into some number of blocks in a way that involves $$n$$. With this in mind, review how you proved Pascal’s (recurrence) equation.

137. What if the question asked about six sandwiches and two distinct bags? How does having identical bags change the answer?

138. What are the possible sizes of parts?

139. Suppose we make a list of the $$k$$ items. We take the first $$k_1$$ elements to be the blocks of size $$1$$. How many elements do we need to take to get $$k_2$$ blocks of size two? Which elements does it make sense to choose for this purpose?

141. To see how many broken permutations of a $$k$$ element set into $$n$$ parts do not have $$k$$ is a part by itself, ask yourself how many broken permutations of $$[7]$$ result from adding $$7$$ to the one of the two permutations in the broken permutation $$\{14, 2356\}$$.

142b. Here it is helpful to think about what happens if you delete the entire block containing $$k$$ rather than thinking about whether $$k$$ is in a block by itself or not.

143. You can think of a function as assigning values to the blocks of its partition. If you permute the values assigned to the blocks, do you always change the function?

144. The Prüfer code of a labeled tree is a sequence of $$n − 2$$ entries that must be chosen from the vertices that do not have degree $$1$$. The sequence can be though of as a function from the set $$[n − 2]$$ to the set of vertices that do not have degree $$1$$. What is special about this function?

145. When you add the number of functions mapping onto $$J$$ over all possible subsets $$J$$ of $$N$$, what is the set of functions whose size you are computing?

148. What if the $$j_i$$’s don’t add to $$k$$? Additional Hint: Think about listing the elements of the $$k$$-element set and labeling the first $$j_1$$ elements with label number $$1$$.

149. The sum principle will help here.

150. How are the relevant $$j_i$$’s in the multinomial coefficients you use here different from the $$j_i$$’s in the previous problem.

151. Think about how binomial coefficients relate to expanding a power of a binomial and note that the binomial coefficient $$\binom{n}{k}$$ and the multinomial coefficient $$\binom{n}{k,n−k}$$ are the same.

152a. We have related Stirling numbers to powers $$n^k$$. How are binomial coefficients related to falling factorial powers?

152b. In the equation $$\sum_{j=0}^{n} n^j-S(k, j) = n^k$$, we might try substituting $$x$$ for $$n$$. However we don’t know what $$\sum_{j=0}^{x}$$ means when $$x$$ is a variable. Is there anything other than n that makes a suitable upper limit for the sum? (Think about what you know about $$S(k, j)$$).

153. For the last question, you might try taking advantage of the fact that $$x = x + 1 − 1$$.

154. What does induction have to do with Equation (3.1)? Additional Hint: What could you assume inductively about $$x^{\underline{k−1}}$$ if you were trying to prove $$x^{\underline{k}} = \sum_{n=0}^{k} s(k, n)x^n$$?

156a. There is a solution for this problem similar to the solution to Problem 154.

156b. Is the recurrence you got familiar?

156d. Show that $$(−x)^{\underline{k}} = (−1)^kx^{\underline{k}}$$ and $$(−x)^{\underline{k}} = (−1)^kx^{\underline{k}}$$. Additional Hint: The first hint lets you write an equation for $$(−1)^kx^{\underline{k}}$$ as a rising factorial of something else and then use what you know about expressing rising factorials in terms of falling factorials, after which you have to convert back to factorial powers of $$x$$.

162. How can you start with a partition of $$k$$ and make it into a new partition of $$k + 1$$ that is guaranteed to have a part of size one, even if the original partition didn’t?

163. Draw a line through the top-left corner and bottom-right corner of the topleft box.

164. The largest part of a partition is the maximum number of boxes in a row of its Young diagram. What does the maximum number of boxes in a column tell us?

165. Draw all self conjugate partitions of integers less than or equal to $$8$$. Draw all partitions of integers less than or equal to $$8$$ into distinct odd parts (many of these will have just one part). Now try to see how to get from one set of drawings to the other in a consistent way.

166. Draw the partitions of six into even parts. Draw the partitions of six into parts used an even number of times. Look for a relationship between one set of diagrams and the other set of diagrams. If you have trouble, repeat the process using $$8$$ or even $$10$$ in place of $$6$$.

167. Draw a partition of ten into four parts. Assume each square has area one. Then draw a rectangle of area $$40$$ enclosing your diagram that touches the top of your diagram, the left side of your diagram, and the bottom of your diagram. How does this rectangle give you a partition of $$30$$ into four parts?

168c. Consider two cases, $$m′ > m$$ and $$m′ = m$$.

168d. Consider two cases, $$n′ > n$$ and $$n′ = n$$.

169. Suppose we take two repetitions of this complementation process. What rows and columns do we remove from the diagram? Additional Hint: To deal with an odd number of repetitions of the complementation process, think of it as an even number plus $$1$$. Thus ask what kind of partition gives us the partition of one into one part after this complementation process.

170. How many compositions are there of $$k$$ into $$n$$ parts? What is the maximum number of compositions that could correspond to a given partition of $$k$$ into $$n$$ parts?

171a. These two operations do rather different things to the number of parts, and you can describe exactly what only one of the operations does. Think about the Young diagram.

171b. Think about the Young diagram. In only one of the two cases can you give an exact answer to the question.

171c. Here the harder part requires that, after removal, you consider a range of possible numbers being partitioned and that you give an upper bound on the part size. However, it lets you describe the number of parts exactly.

171d. One of the two sets of partitions of smaller numbers from the previous part is more amenable to finding a recurrence than the other. The resulting recurrence does not have just two terms though.

171h. If there is a sum equal to zero, there may very well be a partition of zero.

172. How does the number of compositions of $$k$$ into $$n$$ distinct parts compare to the number of compositions of $$k$$ into $$n$$ parts (not necessarily distinct)? What do compositions have to do with partitions?

173. While you could simply display partitions of $$7$$ into three parts and partitions of $$10$$ into three parts, we hope you won’t. Perhaps you could write down the partitions of $$4$$ into two parts and the partitions of $$5$$ into two distinct parts and look for a natural bĳection between them. So the hope is that you will discover a bĳection from the set of partitions of $$7$$ into three parts and the partitions of $$10$$ into three distinct parts. It could help to draw the Young diagrams of partitions of $$4$$ into two parts and the partitions of $$5$$ into two distinct parts.

174. In the case $$k = 4$$ and $$n = 2$$, we have $$m = 5$$. In the case $$k = 7$$ and $$n = 3$$, we have $$m = 10$$.

175. What can you do to a Young diagram for a partition of $$k$$ into $$n$$ distinct parts to get a Young diagram of a partition of $$k − n$$ into some number of distinct parts?

176. For any partition of $$k$$ into parts $$λ_1$$, $$λ_2$$, etc. we can get a partition of $$k$$ into odd parts by factoring the highest power of two that we can from each $$λ_i$$, writing $$λ_i = γ_i · 2_k^i$$. Why is $$γ_i$$ odd? Now partition $$k$$ into $$2^{k_1}$$ parts of size $$γ_1$$, $$2^{k_2}$$ parts of size $$γ_2$$, etc. and you have a partition of $$k$$ into odd parts.

177. Suppose we have a partition of $$k$$ into distinct parts. If the smallest part, say $$m$$, is smaller than the number of parts, we may add one to each of the $$m$$ largest parts and delete the smallest part, and we have changed the parity of the number of parts, but we still have distinct parts. On the other hand, suppose the smallest part, again say $$m$$, is larger than or equal to the number of parts. Then we can subtract $$1$$ from each part larger than $$m$$, and add a part equal to the number of parts larger than $$m$$. This changes the parity of the number of parts, but if the second smallest part is $$m + 1$$, the resulting partition does not have distinct parts. Thus, this method does not work. Further, if it did always work, the case $$k \neq \dfrac{3j^2+j}{2}$$ would be covered also. However, you can modify this method by comparing $$m$$ not to the total number of parts, but to the number of rows at the top of the Young diagram that differ by exactly one from the row above. Even in this situation, there are certain slight additional assumptions you need to make, so this hint leaves you a lot of work to do. (It is reasonable to expect problems because of that exceptional case.) However, it should lead you in a useful direction.

183. Substitute something for $$A$$, $$P$$ and $$B$$ in your formula from Problem 181.

184. For example, to get the cost of the fruit selection $$APB$$ you would want to get $$x^{20}x^{25}x^{30} = x^{75}$$.

186. Consider the example with $$n = 2$$. Then we have two variables, $$x1$$ and $$x2$$. Forgetting about $$x_2$$, what sum says we either take $$x_1$$ or we don’t? Forgetting about $$x_1$$, what sum says we either take $$x_2$$ or we don’t? Now, what product says we either take $$x_1$$ or we don’t and we either take $$x_2$$ or we don’t?

188. For the last two questions, try multiplying out something simpler first, say $$(a_0+a_1x+a_2x^2)(b_0+b_1x+b_2x^2)$$. If this problem seems difficult the part that seems to cause students the most problems is converting the expression they get for a product like this into summation notation. If you are having this kind of problem, expand the product (a_0 + a_1x + a_2x^2)(b_0 + b_1x + b_2x^2) and then figure out what the coefficient of $$x^2$$ is. Try to write that in summation notation.

189. Write down the formulas for the coefficients of $$x^0$$, $$x^1$$, $$x^2$$ and $$x^3$$ in

$\left( \sum_{i=0}^{n} a_ix^i \right) \left( \sum_{j=0}^{m} b_jx^j \right).$

190. How is this problem different from Problem 189? Is this an important difference from the point of view of the coefficient of $$x^k$$?

191. If this problem appears difficult, the most likely reason is because the definitions are all new and symbolic. Focus on what it means for $$\sum_{k=0}^{\infty} c_kx^k$$ to be the generating function for ordered pairs of total value $$k$$. In particular, how do we get an ordered pair with total value $$k$$? What do we need to know about the values of the components of the ordered pair?

192b. You might try applying the product principle for generating functions to an appropriate power of the generating function you got in the first part of this problem. Additional Hint: In Problem 125 you found a formula for the number of $$k$$-element multisets chosen from an $$n$$-element set. Suppose you use this formula for ak in $$\sum_{k=0}^{\infty} a_kx^k$$. What do you get the generating function for?

195. While you could use calculus techniques, there is a much simpler approach. Note that $$1 + x = 1 − (−x)$$. Additional Hint: Can you see a way to use Problem 194?

197. Look for a power of a polynomial to get started. Additional Hint: The polynomial referred to in the first hint is a quotient of two polynomials. The power of the denominator can be written as a power series.

198. Interpret Problem 197 in terms of multisets.

199e. When you factor out $$x_1x_2 ··· x_n$$ from the enumerator of trees, the result is a sum of terms of degree $$n − 2$$. (The degree of $$x_1^{i_1} x_2^{i_2} ··· x_n^{i_n}$$ is $$i_1 + i_2 + ··· + i_n$$). Additional Hint: Write down the picture (using $$x$$s) of a tree on five vertices with two vertices of degree one, of one with three vertices of degree one, and with four vertices of degree $$1$$. Factor $$x_1x_2x_3x_4x_5$$ out of the picture and look at what is left. How is it related to your vertices of degree one? Now remove the vertices of degree $$1$$ from the tree and write down the picture of the tree that remains. What is special about the vertices of degree $$1$$ of that tree. (You can just barely learn something from this with five vertex trees, so you might want to experiment a bit with six or seven vertex trees.)

200. This is a good place to apply the product principle for picture enumerators.

201a. The product principle for generating functions helps you break the generating function into a product of ten simpler ones.

201b. $$m$$ was $$10$$ in the previous part of this problem.

203a. Don’t be afraid of writing down a product of infinitely many power series.

203b. From the fifth factor on, there is no way to choose a $$q^i$$ that has $$i$$ nonzero and less than five from the factor.

203d. Describe to yourself how to get the coefficient of a given power of $$q$$.

204. If infinitely many of the polynomials had a nonzero coefficient for $$q$$, would the product make any sense?

205. $$(1+ q^2 + q^4)(1+ q^3 + q^9)$$ is the generating function for partitions of an integer into at most two twos and at most two threes.

206. $$(1+ q^2 + q^4)(1+ q^3 + q^9)$$ is the generating function for partitions of an integer into at most two twos and at most two threes. (This is intentionally the same hint as in the previous problem, but it has a different point in this problem.)

207. In the power series $$\sum_{j=0}^{\infty} q^{2ij}$$, the $$2ij$$ has a different interpretation if you think of it as $$(2i) · j$$ or if you think of it as $$i · (2j)$$.

208. Note that

$$\dfrac{1 − q^2}{1 − q} · \dfrac{1 − q^4}{1 − q^2} · \dfrac{1 − q^6}{1 − q^3} · \dfrac{1 − q^8}{1 − q^4} = \dfrac{(1 − q^6)(1 − q^8)}{(1 − q)(1 − q^3)}$$.

209. Note that $$q^i + q^{3i} + q^{5i} + ··· = q^i (1 + q^2 + q^4 + ···)$$.

210a. We want to calculate the number of partitions whose Young diagrams fit into a two by two square. These partitions have at most two parts and the parts have size at most two. Thus they are partitions of $$1$$, $$2$$, $$3$$, or $$4$$. However, not all partitions of $$3$$ or $$4$$ have diagrams that fit into a two by two square. Try writing down the relevant diagrams.

210b. They are the generating function for the number of partitions whose Young diagram fits into a rectangle $$n−1$$ units wide and $$1$$ unit deep or into a rectangle $$1$$ unit wide and $$n − 1$$ units deep respectively.

210c. How can you get a diagram of a partition counted by partition is counted by $$\left[ \begin{array}{ll} m+n \\ \;\;\;n \end{array} \right]_q$$ from one whose partition is counted by $$\left[ \begin{array}{ll} m+n \\ \;\;\;m \end{array} \right]_q$$?

210e.iii. Think about geometric operations on Young Diagrams

210f. How would you use the Pascal recurrence to prove the corresponding result for binomial coefficients?

210g. For finding a bĳection, think about lattice paths.

210h. If you could prove $$\left[ \begin{array}{ll} m+n \\ \;\;\;n \end{array} \right]_q$$ is a polynomial function of $$q$$, what would that tell you about how to compute the limit as $$q$$ approaches $$−1$$? Additional Hint: Try computing a table of values of $$\left[ \begin{array}{ll} m+n \\ \;\;\;n \end{array} \right]_q$$ with $$q = −1$$ by using the recurrence relation. Make a pretty big table so you can see what is happening.

211c. You may run into a product of the form $$\sum_{i=0}^{\infty} a^i x^i \sum_{j=0}^{\infty} a^j x^j$$. Note that in the product, the coefficient of $$x^k$$ is $$\sum_{i=0}^{k} a^i b^{k-i} = \sum_{i=0}^{k} \dfrac{a^i}{b^i}$$.

214. Our recurrence becomes $$a_n = a_{n−1} + a_{n−2}$$.

217.

$$\dfrac{5x + 1}{(x − 3)(x − 5)} = \dfrac{cx + 5c + dx − 3d}{(x − 3)(x − 5)}$$

gives us

$$5x = cx + dx$$

$$1=5c − 3d$$.

218. To have

$$\dfrac{ax + b}{(x − r1)(x − r2)} = \dfrac{c}{x − r_1} + \dfrac{d}{x − r_2}$$

we must have

$$cx − r_2c + dx − r_1d = ax + b$$.

222a. Once again it will save a lot of tedious algebra if you use the symbols $$r_1$$ and $$r_2$$ for the solutions as in Problem 221 and substitute the actual values of the solutions once you have a formula for $$a_n$$ in terms of $$r_1$$ and $$r_2$$.

224a. A Catalan path could touch the $$x$$-axis several times before it reaches $$(2n, 0)$$. Its first touch can be any point $$(2i, 0)$$ between $$(2, 0)$$ and $$(2n, 0)$$. For the path to touch first at $$(2i, 0)$$, the path must start with an upstep and then proceed as a Dyck path from $$(1, 1)$$ to $$(2i−1, 1)$$. From there it must take a downstep. Can you see a bĳection between such Dyck paths and Catalan paths of a certain kind?

224b. Does the right-hand side of the recurrence remind you of some products you have worked with?

224c.

$$\dfrac{1 · 3 · 5 ···(2i − 3)}{i!} = \dfrac{(2i − 2)!}{(i − 1)!2^i i!}$$.

226. Try drawing a Venn Diagram.

228. Try drawing a Venn Diagram.

231b. For each student, how big is the set of backpack distributions in which that student gets the correct backpack? It might be a good idea to first consider cases with $$n = 3$$, $$4$$, and $$5$$. Additional Hint: For each pair of students (say Mary and Jim, for example) how big is the set of backpack distributions in which the students in this pair get the correct backpack. What does the question have to do with unions or intersections of sets. Keep on increasing the number of students for which you ask this kind of question.

232. Try induction. Additional Hint: We can apply the formula of Problem 226 to get

$$$$\begin{split} \left| \bigcup_{i=1}^{n} A_i \right| &= \left| \left( \bigcup_{i=1}^{n-1} A_i \right) ∪ A_n \right| \\ &= \left| \bigcup_{i=1}^{n-1} A_i \right| + |A_n| - \left| \left( \bigcup_{i=1}^{n-1} A_i \right) ∩ A_n \right| \\ &= \left| \bigcup_{i=1}^{n-1} A_i \right| + |A_n| - \left| \bigcup_{i=1}^{n-1} A_i ∩ A_n \right| \end{split}$$$$

233b. Let $$T$$ be the set of all $$i$$ such that $$x ∈ A_i$$. In terms of $$x$$, what is different about the $$i$$ in $$T$$ and those not in $$T$$? Additional Hint: You may come to a point where the binomial theorem would be helpful.

235. Notice that it is straightforward to figure out how many ways we may pass out the apples so that child $$i$$ gets five or more apples: give five apples to child $$i$$ and then pass out the remaining apples however you choose. And if we want to figure out how many ways we may pass out the apples so that a given set $$C$$ of children each get five or more apples, we give five to each child in $$C$$ and then pass out the remaining $$k − 5|C|$$ apples however we choose.

236. Start with two questions that can apply to any inclusion-exclusion problem. Do you think you would be better off trying to compute the size of a union of sets or the size of a complement of a union of sets? What kinds of sets (that are conceivably of use to you) is it easy to compute the size of? (The second question can be interpreted in different ways, and for each way of interpreting it, the answer may help you see something you can use in solving the problem.) Additional Hint: Suppose we have a set $$S$$ of couples whom we want to seat side by side. We can think of lining up $$|S|$$ couples and $$2n − 2|S|$$ individual people in a circle. In how many ways can we arrange this many items in a circle?

237. Reason somewhat as you did in Problem 236, noting that if the set of couples who do sit side-by-side is nonempty, then the sex of the person at each place at the table is determined once we seat one couple in that set. Additional Hint: Think in terms of the sets $$A_i$$ of arrangements of people in which couple $$i$$ sits side-by-side. What does the union of the sets $$A_i$$ have to do with the problem?

239. What does Problem 238 have to do with this question?

242a. For each edge in $$F$$ to connect two vertices of the same color, we must have all the vertices in a connected component of the graph with vertex set $$V$$ and edge set $$F$$ colored the same color.

242c. How does the number you are trying to compute relate to the union of the sets $$A_i$$?

243. One way to get a proper coloring of $$G − e$$ is to start with a proper coloring of $$G$$ and remove $$e$$. But there are other colorings of $$G$$ that become proper when you remove $$e$$.

246. One approach would be to try to guess the result by doing a bunch of examples and use induction to prove you are right. If you try this, what will you be able to use to make the induction step work? There are other approaches as well.

253a. What do you want $$\varphi^n ◦ \varphi^{−1}$$ to be?

254. If $$σ^i = σ^j$$ and $$i \neq j$$, what can you conclude about $$ι$$?

256b. What does it mean for one function to be the inverse of another one?

261. Once you know where the corners of the square go under the action of an isometry, how much do you know about the isometry?

264. In how many ways can you choose a place to which you can move vertex $$1$$? Having done that, in how many ways can you place the three vertices adjacent to vertex $$1$$?

265a. In how many ways can you choose a place to which you can move vertex $$1$$? Having done that, in how many ways can you place the three vertices adjacent to vertex $$1$$?

265b. Why is it sufficient to focus on permutations that take vertex $$1$$ to itself?

270. If a subgroup contains, say, $$ρ^3$$ and some flip, how many elements of $$D_4$$ must it contain?

272. If the list $$(i σ(i) σ^2(i) ... σ^n(i))$$ does not have repeated elements but the list $$(i σ(i) σ^2(i) ... σ^n(i) σ^{n+1}(i))$$ does have repeated elements, then which element or elements are repeats?

277. The element $$k$$ is either in a cycle by itself or it isn’t.

286. Before you try to show that $$\overline{\overline{σ}}$$ actually is a permutation of the colorings, it would be useful to verify the second part of the definition of a group action, namely that $$\overline{\overline{σ}} ◦ \overline{\overline{\varphi}} = \overline{\overline{σ ◦ \varphi}}$$.

289. If $$z ∈ Gx$$ and $$z ∈ G y$$, how can you use elements of $$G$$ to explain the relationship between $$x$$ and $$y$$? Additional Hint: Suppose $$σ$$ is a fixed member of $$G$$. As $$τ$$ ranges over $$G$$, which elements of $$G$$ occur as $$τσ$$?

295. How does the size of a multiorbit compare to the size of $$G$$?

301. We are asking for the number of orbits of some group on lists of four $$R$$s, six $$B$$s, and seven $$G$$s.

305. There are five kinds of elements in the rotation group of the cube. For example, there are six rotations by $$90$$ degrees or $$270$$ degrees around an axis connecting the centers of two opposite faces and there are $$8$$ rotations (of $$120$$ degrees and $$240$$ degrees, respectively) around an axis connecting two diagonally opposite vertices.

306. Is it possible for a nontrivial rotation to fix any coloring?

309. There are $$48$$ elements in the group of automorphisms of the graph. Additional Hint: For this problem, it may be easier to ask which group elements fix a coloring rather than which colorings are fixed by a group element.

326. The group of automorphisms of the graph has $$48$$ elements and contains $$D_6$$ as a subgraph. Additional Hint: The permutations with four one-cycles and the two-cycle $$(1 \; 4)$$, $$(2 \; 5)$$, or $$(3 \; 6)$$ are in the group of automorphisms. Once you know the cycle structure of $$D_6$$ and $$(1\; 4)D_6 = \{(1\; 4)σ|σ ∈ D_6\}$$, you know the cycle structure of every element of the group.

327. What does the symmetric group on five vertices have to do with this problem?

329c. In the relation of a function, how many pairs $$(x, f(x))$$ have the same $$x$$-value?

332. For the second question, how many arrows have to leave the empty set? How many arrows have to leave a set of size one?

339. What is the domain of $$g ◦ f$$?

345. If we have scoops of vanilla, chocolate, and strawberry sitting in a circle in a dish, can we distinguish between VCS and VSC?

349. To show a relation is an equivalence relation, you need to show it satisfies the definition of an equivalence relation.

353. To get you started, in Problem 38 the equivalence classes correspond to seating arrangements.

361. You’ve probably guessed that the sum is $$n^2$$. To prove this by contradiction, you have to assume it is false, that is, that there is an $$n$$ such that $$1+3+ 5 + ··· + 2n − 1 \neq n^2$$. Then the method of Problem 360 says there must be a smallest such $$n$$ and suggests we call it $$k$$. Why do you know that $$1+3+5+ ··· + 2k − 3=(k − 1)2$$? What happens if you add $$2n − 1$$ to both sides of the equation?

365. You’ve probably already seen that, with small values of $$n$$, sometimes $$n^2$$ and sometimes $$2^n$$ is bigger. But if you keep experimenting one of the functions seems to get bigger and stay bigger than the other. The number $$n = b$$ where this change occurs is a good choice for a base case. So as not to spoil the problem for you, we won’t say here what this value of $$b$$ is. However, you shouldn’t be surprised later in the proof if you need to use the assumption that $$n/g\;t\;b$$. Additional Hint: You may have reached the point of assuming that $$2^{k−1} > (k − 1)^2$$ and found yourself wondering how to prove that $$2^k > k^2$$. A natural thing to try is multiplying both sides of $$2^{k−1} > (k − 1)^2$$ by $$2$$. This ends up giving you $$2^k > 2k^2 − 4k + 2$$. Based on previous experience it is natural for you to expect to see how to turn this new right hand side into $$k^2$$ but not see how to do it. Here is the hint. You only need to show that the right hand side is greater than or equal to $$k^2$$. For this purpose, you need to show that one of the two $$k^2$$s in $$2k^2$$ somehow balances out the $$−4k$$. See if you can figure out how the fact that you are only considering $$k$$s with $$k > b$$ can help you out.

366. When you suspect an argument is not valid, it may be helpful to explicitly try several values of $$n$$ to see if it makes sense for them. Often small values of $$n$$ are adequate to find the flaw. If you find one flaw, it invalidates everything that comes afterwards (unless, of course, you can fix the flaw).

370. You might start out by ignoring the word unique and give a proof of the simpler theorem that results. Then look at your proof to see how you can include uniqueness in it.

378. What is the power series representation of $$e^{x^2}$$?

381. There is only one element that you may choose. In the first case, you either choose it or you don’t.

387b. At some point, you may find the binomial theorem to be useful.

391. Notice that any permutation is a product of a derangement of the elements not fixed by the permutation times a permutation whose cycle decomposition consists of one-cycles.

397. If $$f(x) = \sum_{i=0}^{\infty} a_i \dfrac{x^i}{i!}$$ and $$g(x) = \sum_{j=0}^{\infty} b_j \dfrac{x^j}{j!}$$, what is the coefficient of $$\dfrac{x^n}{n!}$$ in $$f(x)g(x)$$? Don’t be surprised if your answer has a binomial coefficient in it. In fact, the binomial coefficient should help you finish the problem.

399. Since the sets of a $$k$$-set structure are nonempty and disjoint, the $$k$$-element set of sets can be arranged as a $$k$$-tuple in $$k!$$ ways.

403. The alternate definition of a funciton in Section 3.1.2 can be restated to say that a function from a $$k$$-element set $$K$$ to an $$n$$-element set $$N$$ can be thought of as an $$n$$-tuple of sets, perhaps with some empty, whose union is $$K$$. In order to think of the function as an $$n$$-tuple, we number the elements of $$N$$ as number $$1$$ through number $$n$$. Then the $$i^{\text{th}}$$ set in the $$n$$-tuple is the set of elements mapped to the $$i^{\text{th}}$$ element of $$N$$ in our numbering?

404. Don’t be surprised if you see a hyperbolic sine or hyperbolic cosine in your answer. If you aren’t familiar with these functions, look them up in a calculus book.

407. The EGF for $$\sum_{i=1}^{n} \binom{n}{k} k$$ is $$\sum_{n=1}^{\infty} \sum_{i=1}^{n} \dfrac{n!}{k!(n−k)!} k \dfrac{x^n}{n!}$$. You can cancel out the $$n!$$ terms and the $$k$$ terms. Now try to see if what is left can be regarded as the product of two EGFs.

421a. To apply the exponential formula, we must take the exponential function of an EGF whose constant term is zero, or in other words, for a species of structures that has no structures that use the empty set.

421b. Once you know the vertex set of a graph, all you have to do to specify the graph is to specify its set of edges.

421d. What is the calculus definition of $$\log (1 + y)$$?

421f. Look for a formula that involves summing over all partitions of the integer $$n$$.