# 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 "x" (SB)
• 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 "Nr(x)"
• 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 hypergraph"
• 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" (SB)
• 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 (SB)
• 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 "\delta0,k" (SB)
• p123, line 3: "within in" should be "within" (SB)
• p124, Thm1.4.23: "two of terminal points" should be "two of the terminal points"
• p171, Exm1.6.21: "see either component" should be "since either component"
• p175, before Def1.6.29: "[1971]" should be "[1971])"
• 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 Baym)
• 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 xp.''
• 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 4-bead necklaces.
• 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 [xk/k!]y(x)=[yk-1/(k-1)!](\phi(y))k, or [xk]y(x)=(1/k)[yk-1](\phi(y))k, where 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 [1978]
• 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)