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: The first "r-bad" should be "i-bad".
- 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.