# Appendix D: Hints to Selected Problems

- Page ID
- 77608

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\id}{\mathrm{id}}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\kernel}{\mathrm{null}\,}\)

\( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\)

\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\)

\( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)

\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)

\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vectorC}[1]{\textbf{#1}} \)

\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)1. Answer the questions in Problem 2 for the case of five schools.

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

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

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

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

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

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

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

59. Take the derivative of something interesting.

68. Review Problem 65 and your solution of it.

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

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

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.

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

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?

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

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

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?

138. What are the possible sizes of parts?

149. The sum principle will help here.

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

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

156b. Is the recurrence you got familiar?

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

168c. Consider two cases, \(m′ > m\) and \(m′ = m\).

168d. Consider two cases, \(n′ > n\) and \(n′ = n\).

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

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

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).\]

198. Interpret Problem 197 in terms of multisets.

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

201b. \(m\) was \(10\) in the previous part of this problem.

202. Think about conjugate partitions.

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

203d. Describe to yourself how to get the coefficient of a given power of \(q\).

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

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

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

214. Our recurrence becomes \(a_n = a_{n−1} + a_{n−2}\).

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

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

\(cx − r_2c + dx − r_1d = ax + b\).

221. You can save yourself a tremendous amount of frustrating algebra if you arbitrarily choose one of the solutions and call it \(r_1\) and call the other solution \(r_2\) and solve the problem using these algebraic symbols in place of the actual roots.^{1} Not only will you save yourself some work, but you will get a formula you could use in other problems. When you are done, substitute in the actual values of the solutions and simplify.

222d. Think about how the binomial theorem might help you.

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

\(\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.

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

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

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

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?

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

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

295. How does the size of a multiorbit compare to the size of \(G\)?

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

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?

339. What is the domain of \(g ◦ f\)?

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

377. An earlier problem may help you put your answer into a simpler form.

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

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

392. A binomial coefficient is likely to appear in your answer.

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\).