# Combinatorial Mathematics - Fall 2004 Typos

This page lists the typographical errors that have been discovered in the Fall 2004 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.

## Category 1: Mathematical typos/corrections to text

• p26 Exr1.1.26: "partitions" should be "compositions"
• p35 Exr1.2.12d: the limits of summation on the right side should also run from 1 to n (Chelsea Walton)
• p38 Exr1.2.42: Throughout the problem, k should be assumed to be a natural number (Vo Vang). Part (a) requires in addition that k\ge2, and the degree of the polynomial is k-2, not k-1 (Chelsea Walton)
• p45 after Thm1.3.12: there is a superfluous i at the end of the computation of the Bertrand ballot probability. In the subsequent sentence, the reference to "Exercise 3" should be to "Exercise 23"
• p54 Exr1.3.39: "and the set" should be "to the set"
• p57 Exm2.0.3: In the last recurrence, "an-1" should be "ak-1" (Robert Proctor)
• p63 Exm2.1.7: specifying initial values for all (0,k) suffices only if we allow k to be any integer (Robert Proctor)
• p75 Exm2.2.8: "a0=1" should be "a0=0" (Vo Thuang Vong)
• p80 Thm2.2.16: The last step in the proof is not correct. It needs dim(VA)=k, not dim(VD)=k. This holds because the k sequences in VA generated by letting one of the first k terms be 1 and the others be 0 are linearly independent.
• p85 Exr2.2.21: since c\alpha^n is a single term in a sequence, notation is needed like {c\alpha^n}n=0\infty to refer to the sequence (John Ganci)
• p85 Exr2.2.23: "of is" should be "is" (John Ganci)
• p87 Prop2.3.2: the substitution bn= an- an-1 should be for n\ge2, not n\ge1
• p93 Alg2.3.13: Step 2 needs the requirement that a(k) and b(k+j) are relatively prime for each nonnegative integer j (Bruce Sagan)
• p108-9 Exm3.1.19: the rising factorial appears on both ends of the expression; delete the first occurrence
• p123 Exr3.2.12: the index of summation should be n, not k
• p124 Exr3.2.20: the summation should run to t, not n
• p131 Exm3.3.8: the exponent on x in the last expression in the display should be n, not k
• p152 Prop3.4.4: in the last display, "7/72" should be "17/72" (Robert Proctor)
• p163 Exr3.4.19: the universe of partitions for this problem should be those into distinct parts, and the exceptional values are not only the sums of m+i for i from 1 to m but also the sums of m+i for i from 0 to m-1 (Bruce Sagan). Explanation of the term "Pentagonal Number Theorem" will be added
• p168 Thm4.1.3: "belonging to no sets" should be "not belonging to all sets"
• p176 Exm4.1.19: sign(\sigma) should be defined to be +1 or -1, not just positive or negative
• p195 Exr4.1.56: there should be no vertical edges in the graph (Bruce Sagan)
• p230 Exm4.3.28: In the diagonal tableau, 9 and 3 should be exchanged, which also changes the strip shape. The final tableau is unchanged.
• p256 Prop5.2.3: In the proof, "\sum ki/l" should be \sum ki/l" (Ashutosh Mahajan)
• p274 Def5.3.21: "that traversed each at" should be "that traverses each edge at" (Dennis Lin)
• p278 Exr5.3.33: "multigraph" should be "graph"
• p298-9 Def6.1.9, etc.: To avoid conflict with the use of deficiency and the notation def(S) for matching in general graphs, the term here is being changed to defect'', with notation df(S)
• p296 Cor6.1.4: "k > 1" should be "k\ge1" (Garth Isaak)
• p307 Thm6.2.10: In the statement, it needs to be specified that G is an n-vertex graph
• p328 Exr6.3.8: "the best solution is to give" should be "overtime is minimized by giving", since uniqueness of optimality is not requested (Garth Isaak)
• p375 Exr7.3.23: The statement of sufficiency of Ore's Condition is Corollary 7.3.6, not Theorem 7.3.5. Prove that Theorem 7.3.10 implies Corollary 7.3.6.
• p401 Exr8.2.22: The statement must be restricted to k\ge3 (Dennis Lin)
• p413 Exr8.3.22: "K2m" should be "K2m"
• p458 Exr9.2.8: One must either exclude drawings in which incident edges cross or modify the second statement to say "every two nonincident edges cross an even number of times
• p490 Thm10.1.22: in the statement of the theorem, "|Tn(P)|" should be "f(n)". Also, it should be noted in the statement that P is a k-by-k matrix (Bruce Sagan)
• p491 Thm10.1.22: in the large display, "f(n'2/k)" should be "f(n'/k2)"
• p497 Exr10.1.10: the upper bound needs the ceiling function applied to it, and it is only necessary to specify once that n is at least 3
• p595 Thm12.2.8: "(0,j), (1,j)" should be "(0,k), (1,k)" (Sourabh Bhattacharya)
• p603 Exr 12.2.15: "construct a subgraph" should be "construct a spanning subgraph" (Michael Barrus). Also, "hypergraph graph" should be "hypercube graph"
• p603 Exr12.2.20: "word S" should be "word", and "12342134" should be "123421341" (Michael Barrus)
• p621 Lem12.4.19: The condition that L must be distributive should be added to the statement of the lemma (Aaron Mosier)
• p634 Exr12.4.15: Part (b) is total nonsense (it was intended for the order relation in the next problem). (Brent Solie)
• p695 Exr14.1.22: "E(Kn)" should be "E(Kn)"
• p705 Thm14.2.10: the clause "there are k choices of c for the edge xy" is wrong. The point is that for each of the k choices of a color from L(x), there are at most k/(2e) events that exist for that color on edges incident to x.
• p743 Thm14.4.15: "ck" should be "ci" (Sujay Sanghavi)
• p879 Exm17.1.24: The discussion of the triple (21,6,1) is nonsense. It is corrected by changing the triple to (43,7,1)
• p889 Cor17.2.7: "(v,b,q+1,q+1,1)" should be "(v,q+1,1)"
• p890 Exm17.2.9: Again change (21,6,1) to (43,7,1)
• p904 Exr17.2.8: Part (b) should be restricted to k\ge3
• p945 Exr18.1.28: Part (b) is false; there is a counterexample within the cycle matroid of K4 (Ashutosh Mahajan)
• p957 Cor18.2.15: "r(e)" should be "r(E)" (Garth Isaak)
• p962 Before Prop15.3.5: strike "connected" twice; the dual of every matroid is a matroid with the same components. The proposition repeats Exr15.1.42, which will be removed.
• p1015 line5: "k!n" should be "k|n" (Garth Isaak)
• p1023 Thm19.2.25: the two instances of "flow" in the statement should be "feasible flow"

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

• p26 Exr1.1.25: The first half repeats Exr1.1.6. Exr1.1.6 will be eliminated.
• p29 intro: The publication date on the Graham-Knuth-Patashnik text is 1989, not 1988. This book is cited five times in the text, and four of them have the wrong date. There is also a second edition with the date of 1994. (Will Mitchell)
• p39 Exr1.2.45: This pretty exercise should be (!) but needs a hint: To explain the left side, view each list as a list of pairs of successive elements, and consider the four types of pairs.
• p49 Exr1.3.6: This duplicates Exr1.3.2 (after correcting two instances of "m" to "n") and will be deleted
• p146 Exr3.3.9: The work for an,k is now done in Exm3.3.8, so this exercise will be restricted to bn,k (Garth Isaak)
• p192 Exr4.1.40: To avoid confusion, B and B' in part (b) will change to B1 and B2 (Bruce Sagan)
• p304 Exr6.1.35,36,38: These exercises use augmenting paths and hence are moving to Section 6.2.
• p504-5: this application has been rewritten more concisely
• p584: Thm12.1.19: "2-element completes" should be "2-element chain completes" (Ryan Stout)

## Category 3: Minor typos and corrections

Note: Corrections involving addition, deletion, or alteration of one punctuation mark will be implemented without being listed here. Some corrections to capitalization are also omitted.
• pxv error page: the path given to this error page omitted the final directory "580" and the tilde before "west" (Aaron Mosier)
• p26 Exr1.1.25: "Given" should be "Give" (Robert Proctor)
• p39 Exr1.2.47: "Andrew" should be "Andrews"
• p66 Exr2.1.13: "classical Fibonacci recurrence" should be "classical Fibonacci numbers"
• p68 Exr2.1.26: "k+1-jth" should be "(k+1-j)th" (John Ganci)
• p71 Exr2.1.47: "maximum his money" should be "maximize his money" (John Ganci)
• p97 Exr2.3.3: "recurrence prove that" should be "recurrence to prove that"
• p151 before Prop3.4.4: "sometimes be use to find" should be "sometimes be used to find" (Vo Thuang Vong)
• p155 Thm3.4.12: "less that the length" should be "less than the length" (Vo Thuang Vong)
• p173 Thm4.1.14: "totoal" should be "total" (Ryan Stout)
• p176 Exm4.1.19: "set of inversion changes" should be "set of inversions changes"
• p179 Thm4.1.22: "We want the each" should be "We want each" (Ryan Stout)
• p182 Thm4.1.26: "fixes the disjoint-path system" should be "fixes the disjoint-path systems"
• p194 Exr4.1.54: "disjoint-path system" should be "disjoint-path systems"
• p331 Lem7.1.5: "k+1-connected" should be "(k+1)-connected"
• p341 Def7.2.3: "of a such a family" should be "of such a family" (Ryan Stout)
• p374 Exr7.3.11: "prefect matching" should be "perfect matching"
• p405 before Rem8.3.2: "irrevelant" should be "irrelevant" (Ryan Stout)
• p480 intro: "Ramsey's Theory" should be "Ramsey Theory"
• p481 top: "a k-connected graphs" should be "a k-connected graph"
• p505 Lem10.2.6: "n, Let P a" should be "n, let P be a" (Ryan Stout)
• p507 Def10.2.8: add missing parenthesis
• p522 top: "if if" should be "if" (Ryan Stout)
• p537 Prop11.1.2: "than moving a vertex" should be "then moving a vertex" (Hogyeong Jeong)
• p559 Conj11.2.20: "containing in I" should be "contained in I". On the next page, "Kleitman " should be "Kleitman " (Bruce Sagan)
• p565 Exr11.2.29: "ideal of subset" should be "ideal of subsets"
• p579 last line: "asometimes denoted as Bn" should be "as Bn" (Ryan Stout)
• p582 Def12.1.17: "is set" should be "is a set" (Ryan Stout)
• p598 Rem12.2.13: "allows provides" should be "provides" (Sourabh Bhattacharya)
• p705 Thm14.2.10: "k/e" should be "k/e"
• p715 App14.3.2: "find determine" should be "compute" (Sourabh Bhattacharya)
• p870 second parg: "we general" should be "we study general" (Ryan Stout)

Archive of corrections to earlier versions: Fall 2003, Fall 2002.