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 [1981]"
should be "Kleitman [1979]" (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.