``Combinatorics: A Core Course'' - Typos
This page lists the typographical errors that have been discovered in
the Fall 2002 pre-publication version of
Combinatorics: A Core Course, by Douglas B. West.
This page is of interest only to the few persons having a copy of this
draft, particularly the students in my course and possibly reviewers.
Please send comments and corrections on the book to west @ math.uiuc.edu.
Contributors are noted in parentheses. Shivi Bansal has been particularly
attentive to reporting typos; these are denoted "(SB)"
Category 1: Mathematical typos/corrections to text
- p16, Rem1.1.3: the first sum is missing the summand "i" (SB)
- p55, Thm1.2.24: the second sum in the second paragraph
should not have k! in the denominator (SB)
- p57, Rem1.2.31: the displayed formulas should have "0" in place of
- p67, Thm1.2.53: "by more" should be "by less" (SB)
- p72, Exr1.2.11c: the last "4" should be in the exponent (John Fischer)
- p74, Exr1.2.25: the last "\pi" should be "i" (SB)
- p78, Exr1.2.60: Add "and perimeter n" to the end of the first
sentence, and chang "n" to "k" in part (a) (SB)
- p83, Exm1.3.5: "other than D0" should be
"other than Dn" (SB)
- p94, Thm1.3.23: left paren missing in part (C) (Michael Baym)
- p123, Thm1.4.21 (reviewer version only!): "followed by an integer
or another bar" should be "followed by a larger integer or another bar"
- p132, Exr1.4.29: "CHn-tr-t" should be the binomial coefficient
n-t choose r-t
- p202, Def2.1.24: "ei=vivi+1"
should be "ei=vi-1vi" (SB)
- p239, Exr2.2.23: change ceiling to floor in the hint (SB)
- p249, Thm2.3.8: The clause "Since \kappa(Kn)=n-1" is
no longer needed now that the definition of k-connected requires at
least k+1 vertices (Reza Ziaei and Nirman Kumar)
- p253, Thm2.3.22: in the next-to-last line on the page,
"X'" and "Y'" should be "X" and "Y"
- p257, Lem2.3.30: "Otherwise, S must separate G" should be
"Otherwise, S must separate G-y" (SB)
- p259, Lem2.3.36: in the last paragraph, the subscript on G should
be induced subgraph notation. Note that the v introduced at the
end of the previous paragraph is the guaranteed companion of zu
- p260, Lem2.3.39: the first "G" should be "H" (SB)
- p261, Cor2.3.41: in the containment inequalities specifying the main
case in the last paragraph, "S" should be "S\cap D" (SB)
- p289, Thm2.4.12: the inequality "g(u)\le g(v)-r(D)" should be
"g(u)\ge g(v)-r(D)" (Reza Ziaei)
- p295, Lem2.4.26: the proof given is not adequate; when G contains
K4, a shortest even cycle in G may have two chords
(Nirman Kumar and Reza Ziaei). When G is not triangle-free, the
desired even cycle can be formed using an edge or two of a largest complete
subgraph Q and a path that leaves and re-enters Q
- p370, Exm3.1.6: in the last line, ``n'' should not be used as
both a parameter and a dummy variable (SB)
- p385, Exm3.2.3: the lower bound in the figure should be switched (SB)
- p388, after Thm3.2.5: the mixture of "m"s and "n"s in
the improved upper bounds should all be "n"s
- p420, before Lem3.3.4: the denominator in the last formula should be
24, not 4 (SB)
- p421, Thm3.3.5: in the fourth line of the page, the expected number
of cliques is missing a factor of n\choose r (SB)
- p462, Exm3.4.33: "M(e)" should be "Me"
- p463, Exm3.4.34: "M(5,4)" should be "M5,4"
- p484, Exr3.4.9: "Nr(x)" should be
- p535, Thm4.1.10: In the display, the middle formula is missing the
expectation (Andrew Mehler)
- p719, Exr5.1.7: "L" should be "M"
- p720, Exr5.1.15: "k hypergraph" should be "k-uniform
- p735, Exr5.2.2: in both parts, the conclusions concern odd primes
occurring to odd powers (Kevin Milans, Supratim Deb)
- p902, Exr6.4.55: this must be restricted to matroid basis graphs with
at least three vertices
Category 2: Typos and minor corrections
- pX: "four independent advance course" should be "four independent
advanced courses" (Chris Hutchens)
- p23, after Thm1.1.20: "Equivalently results" should be "Equivalent results"
- p31, after Def1.1.35: "deleted the" should be "deleting the" (SB)
- p32, before Thm1.1.38: Exercise 97 was not included in this printing
- p57, Rem1.2.29: "of binomial type" should be "is of binomial type" (SB)
- p63, before Thm1.2.46: "different between" should be "difference between",
and "products of generating function" should be "products of generating
functions" (Chris Hutchens)
- p75, Exr1.2.35: "indentity" should be "identity"
- p76, Exr1.2.48: "indentity" should be "identity"
- p83, Exm1.3.12: "roor" should be "root" (SB)
- p97, Exm1.3.27: "\delta0k" should be
- p123, line 3: "within in" should be "within" (SB)
- p124, Thm1.4.23: "two of terminal points" should be "two of the terminal
- p171, Exm1.6.21: "see either component" should be "since either
- p175, before Def1.6.29: "" should be ")"
- p209, Cor2.1.46: "adding" should be "add" (SB)
- p217, Exr2.1.79: "multigraph graph" should be "multigraph"
- p231, Exm2.2.18: "them" should be "then" (SB)
- p241, Exr2.2.43: the problem should end "Reduce this problem to a problem
of finding a perfect matching of minimum total weight in a complete graph with
weights on the edges." The last two sentences printed for this problem form
the statement of another problem.
- p306, Exr 2.4.3: "(given by" should be "; that is," (John Fischer)
- p352, before Thm2.5.59: parenthesis missing in table
- p380, Exr3.1.3: "subsets" should be "subset" (SB)
- p464, Thm3.4.36: "Chains chains" should be "We consider chains", and
the next sentence should be "When we reach a new chain, the values of f
on some . . ."
- p469, Rem2.4.47: "Exercises 41-59" refers to Exercises 41 and 59, not to
the exercises between them
- p541, before Thm4.1.20: "probabilities remains" should be
"probability remains" (SB)
- p548, Exr4.1.4: "prove" should be "proved"
- p576, Exr4.2.9: "known" should be "knowing"
- p577, Exr4.2.13: "would needed" should be "would be needed", and
"Q" should be "Qk"
- p678, before Thm4.5.43: the "??" refers to Thm4.5.43
- p727, Lem5.2.14: "xi" is the missing summand
- p729, bottom: "fo" should be "for"
- p854, second parg: The result is "by" Chudnovsky and Seymour (Michael
- p901, Exr6.4.40: the paragraph symbol is extraneous
- p902, Exr6.4.49: the ?? refers to Thm 6.4.43
- p903, Exr6.4.42: "rX" should be "r(X)"
Category 3: Comments and clarifications
- p85, Exm1.3.7: "??? [1998, p581]" should be "Singmaster [1998, p581]"
(mentioned in a book review in the Monthly) (Chris Hutchens)
- p119, Thm1.4.14: The last two sentences have been reworded for clarity
as ``Hence a contributes \SE k0n\CH pk (x-1)k to the
right side. Since \CH pk=0 for k>p, this simplifies by the
Binomial Theorem to (1+x-1)p and then
- p121-126: The section on signed involutions has been rewritten.
It now starts by stating the general method. Next inclusion-exclusion is a
special case of signed involution rather than a vehicle for developing it.
Eulerian numbers are next, since this use of signed involution is very similar
to that in inclusion-exclusion; the proof has been rewritten to reflect that.
Finally, the terminology and presentation for lattice n-paths has been
simplified; the theorem and proof are phrased only for the counting problem,
with the generating function left as an exercise.
- p166-170: The treatment of the pattern inventory has been simplified a
bit, and it has been moved before the discussion of classical groups and
isomorphism classes of graphs, since it is natural to mention it after the
- p175: the paragraph following Thm 1.6.28 has been rewritten as
"The role of differentiation in the inversion formula is to extract a
coefficient in a power series. In the language of formal power series,
the essence of the Lagrange Formula for inverting the relationship
x=y/\phi(y) is that
we use [xk] to denote the operator that extracts the
coefficient of xk from a formal series in x. In the computation above, kk-1 is the specified coefficient in
the expansion of eky."
- p189, Exr1.6.26: reference should be Stanley 
- p241-3, Exr2.2.46 and Exr2.2.56: note the relationship between these two
problems; they will be combined
- p471, before Thm3.4.51: this "common abuse of notation" is being eliminated
from this text
- p472-4, Cor3.4.53, Thm3.4.57, Cor3.4.58: reference is made to the "Whitney
numbers" - this is another name for the rank sizes. The name is not needed in
the context of the material of this section, and these will change to "rank
sizes" (Erin Wolf)