# Combinatorial Mathematics - Fall 2010 Typos

This page lists the typographical errors that have been discovered in the Fall 2010 pre-publication version of Combinatorial Mathematics, by Douglas B. West. This page is of interest only to those persons having a copy of this draft, particularly the students in my course, other users of the text, and reviewers. Please send comments and corrections on the book to west @ math.uiuc.edu. Contributors are noted in parentheses. Please do not send comments about incorrect page numbers in the index (and note that all page numbers there are odd for TeXnical reasons); however, I do want to know of missing terms that should be added to the index.

## Category 1: Mathematical typos/corrections to text

• p29, Exercise 1.1.35: part (b) should be for "crowns" (which do not flip) instead of necklaces (Christine Kelley)
• p61, Exercise 1.3.46: "[k]" should be "k"
• p89, Application 2.2.18: for the inhomogeneous term, the degree specified for F should be d, not k (Christine Kelley)
• p91, Theorem 2.2.20: Although all four spaces have dimension at most k, this proof does not argue that VC has dimension at least k and hence is incomplete. A proof that mirrors the steps of the generating function method would show A⇒B⇒C⇒D, which would suffice since Lemma 2.2.5 implies that VA does have dimension k. Completing the proof that way requires showing that partial fraction expansion works.
• p92, Theorem 2.2.22: The first expression in the second paragraph is missing the outer summation over n from 1 to ∞ (David Hannasch). Also, the expression for the generating function is the most important result of the theorem and is being added to the theorem statement.
• p110, Exercise 2.3.4: "1/n" should be "1/i" (David Morrison)
• p120, Theorem 3.1.10: Each instance of "[xn]" should be "[xk]", and then the index in each geometric series should be "j" rather than "k"
• p126, Theorem 3.1.25: C(x) is a generating function but is missing the factor xk from the summand.
• p127, Exercise 3.1.9: In part (d), the exponent on (-1) should be k-i (Elyse Yeager)
• p129, Exercise 3.1.24: There is a missing set brace in the description of the legal moves (Adam Azzam)
• p131, Exercise 3.1.44: The probability given for Game 1 should be 1/n when the total is n+1 dollars; A cannot have n dollars when the total is n dollars (the total starts at \$2).
• p155, Example 3.3.18: A step at the end is missing. Integration introduce a constant that must be determined from the initial conditions.
• p184, Exercise 3.4.14: Part (b) should be stated for k≥2
• p201, Example 4.1.22: "every every" should be "every entry"
• p202, Example 4.1.25: "permutations of n" should be "partitions of n".
• p221, Lemma 4.2.5: "define the bijection" should be "define the injections"
• p248, Example 4.3.26: The top line of the strip shape should be shifted right by one position
• p273, Exercise 5.1.32: For part (b), one needs to forbid isolated vertices (Jay Cummings)
• p285, Exercise 5.2.24: "and each graph G, prove that a G with" should be ", prove that each graph G with" (Adam Azzam)
• p296, Exercise 5.3.18: For decomposition, isolated vertices are unimportant. Hence this problem should ask for decomposition into two disconnected subgraphs without isolated vertices, for clarity. The publication date should be 2004.
• p322, Theorem 6.1.17: In the first paragraph, "a vertex cover" should be "an edge cover" (Christine Kelley)
• p329, Lemma 6.2.8: At the end of the first paragraph, add ", where d=def(G) (Christine Kelley)
• p367, after Definition 7.2.3: "family of independent paths" should be "independent family of paths" (similarly elsewhere)
• p368, Theorem 7.2.5: X' and Y' should be X and Y
• p392, Corollary 7.3.8: "e(G̅)" should be "|E(G̅)|"
• p424, Definition 8.2.10: "L-choosable" should be "L-colorable"
• p447, Example 8.3.20: "nonempty bipartite graph" should be "nontrivial bipartite graph", and "α(L(G)," should be "α(L(G)),"
• p470, Exercise 9.1.26: The statement that maximal outerplanar graphs have spanning cycles requires at least three vertices. (Adam Azzam)
• p501, Example 9.3.22: The injective chromatic number of the Petersen graph is 5, not 10
• p564-565, Theorem 10.3.21: The two instances of "inequalities" should be "equalities" (Mu-Tsun Tsai)
• p667, Remark 12.2.30: The set A should be defined using x in Pk-1, so that A winds up in rank k in the product. Now A* is in {(y,q): y∈Pk}. Finally, |A| = Nk-1 and |A*| = Nk. The computation then simplifies as claimed. (David Hannasch)

## Category 2: Comments, clarifications, and cross-references

• p125, Remark 3.1.24: In order to reach the formula for Eulerian numbers more directly, the general idea for the Inversion Principle is being postponed to the next section.
• p127, Exercise 3.1.3: This repeats Exercise 1.1.5 and is being deleted.
• p129, Exercise 3.1.25: Change x to z, since this is the variable associated with the third parameter.
• p133-4, Definition 3.2.2 and Remark 3.2.3: The material on composition is being postponed to the section on the Exponential Formula, where it becomes relevant.
• p321, top paragraph: The "Exercise 18" cited here refers to Section 6.2
• p426, Theorem 8.2.13: The reference to "Ldegsubg" is to Lemma 8.2.11

## Category 3: Minor typos and corrections

Note: Corrections involving addition, deletion, or alteration of one punctuation mark may be implemented without being listed here. Corrections to capitalization may also be omitted.
• pii, Chapter 3: "2.1" should be "3.1" (Ilkyoo Choi)
• p36, top: "Manhattan metric" -> should be "Manhattan metric)"
• p55, top: "Bijections involving binary tree" should be "Bijections involving binary trees" (Oliver Pechenik)
• p82, Lemma 2.2.5: "have observe" should be "have observed"
• p120, bottom: "hard to to" should be "hard to" (Ilkyoo Choi)
• p127, Exercise 3.1.11: The last three lines are extraneous and are being deleted.
• p202, Example 4.1.25: "parity or r" should be "parity of r"
• p209, Remark 4.1.36: "call the Condensation Method" should be "called the Condensation Method" (Oliver Pechenik)
• p232, Exercise 4.2.32: "physical" should be "physically"
• p249, before Definition 4.3.27: "Franch" should be "French"
• p316, Corolllary 6.1.4: "An orientation choose" should be "An orientation chooses"
• p396, Remark 7.3.17: "few of exceptions" should be "few exceptions"
• p414, Example 8.1.14: "but construction" should be "but the construction"
• p418, Exercise 8.1.28: "along path" should be "along a path" (Thomas Mahoney/Oliver Pechenik)
• p432, Exercise 8.2.8: This repeats Proposition 8.2.8 and is being deleted
• p444, Definition 8.3.13: "we view ... is a partition" should be "we view ... as a partition" (Thomas Mahoney/Oliver Pechenik)
• p447, last line: "Fulkerson's reduced" should be "Fulkerson reduced"
• p448, Lemma 8.3.22: "optimial" should be "optimal"
• p739, Theorem 13.1.30: "positing" should be "position"
• p1034-1055: Additions to the index (mostly from Elyse Yeager): "Binomial Inversion", "Principle of Inclusion and Exclusion" ("PIE" is already there), the names of the various Platonic solids; "closure (Hamiltonian)" ("closed (Hamiltonian closure))" is already there, but it also needs addition to the Glossary) (Thomas Mahoney/Oliver Pechenik)

Archive of corrections to earlier versions: Fall 2009, Fall 2008, Fall 2007, Fall 2006, Fall 2005, Fall 2004, Fall 2003, Fall 2002.