Errata - Applied Discrete Structures

As errors in the printed version appear, they will be logged here.

Version 2.0 - March 2013

• Page 22Exercise 3 in section 1.3 should be "...\(\mathcal{P}(\{a,b,c,d\})\)" to be consistent with the given solution. (Found by Raymond Berger, Eckerd College)
• Page 26, the two lines above Example 1.5.1 should be replaced with

  In the expression $\displaystyle{\sum _{k=1}^n a_k}$,

  • The variable \(k\) is referred to as the index, or the index of summation.
  • The expression \(a_k\) is the general term of the series. It defines the numbers that are being added together in the series.
  • The value of \(k\) below the summation symbol is the initial index and the value above the summation symbol is the terminal index.
  • It is understood that the series is a sum of the general terms where the index starts with the initial index and increases by one up to and including the terminal index.

  (Found by Jim Propp)

• Page 33 First line of Example 2.1.3 should be "... questionnaire consisting of ten questions." (Found by Alex DeCourcy)
• Page 36 - The equation in Theorem 2.2.1 should end with the product \( \prod_{j=0}^{k-1} (n-j)\) .
• Page 42 The second line of Example 2.4.2 should be

  ...abc, abd, acd, and bcd are the only listings possible.

  (Found by Alex DeCourcy)
• Page 44: first line, the last line of Example 2.4.8: The equals sign after \( \binom{4}{2} \) should be removed.
• Page 51: 6th line from the top should be:

  q follows from p.

• Page 63 Exercise 3 (c ): the first premise should be $$p \rightarrow (q \rightarrow r)$$
• Page 103 (middle of Section 5.6): The 16th line from the bottom should be

  (4) There exist matrices A where $A^{2}=A$ with $A \ne I$ and $A \ne -I$.

• Page 72 Exercise 3 should read "..., U(x): x is published in the United State."
• Page 130, Section 7.1, exercise 1(c) should be $$\dots where\hspace{0.25 cm} h = \dots$$ (Found by a student at Luzurne County CC)
• Page 180, Section 9.1, The edges in Figure 9.1.1 are mislabled. The graph should look like this:
  

  

  Sage code for this graph is

  G1=DiGraph( { 's':{'a':'1','b':'0'},'a':{'b':'0'}, 'b':{'a':'1','b':'0'}});
G1.show(pos={"s":[0,0],"a":[-1,1],"b":[1,1.3]},edge_labels=True)
  

  (Found by a student at Luzurne County CC)
• Page 203: In the paragraph headed "A Note on What Is Possible and What Is Impossible." It should be noted that there are time complexities between exponential and polynomial, and that algorithms for find Hamiltonian paths also do not currently exist with these intermediate times. Their non-existence has not been proven.
• Page 212 Example 9.5.7: in the second line of this example, $$w(e_3)-f_1(e_3)$$ should be equal to 15, not 5. The flow function f₁ is defined in the paragraph with heading MAXIMAL FLOW.
• Page 303 First line of Example 12.3.6 should read "...the two vectors (3, 1) and (1,4) generate..." (found be Vince DiChiacchio)
• Page 353 First line. The list of production rules should be $$A \rightarrow b B, B \rightarrow c C, C \rightarrow a A, C \rightarrow b C , C \rightarrow c C, C \rightarrow c$$.
• Page 383 Below the 9th line from the top, there is a column of six equations that imply a column of three equations. In the column of six, the last two equations should be $$b_5 = a_1 +_2 a_3\\b_6= a_2 +_2 a_3$$ (found be Vince DiChiacchio)
• Page 395 Fourth line from the top of the page should end with

  "... the equation $a x = b$, $a\ne 0$. We"

• Page 413 Solution to Section 1.4, exercise #5 (d) should be 51. (The wording of this problem is terrible and will be revised!)(Found by Alex DeCourcy)
• Page 414 (page 247 of Part 1): The solutions to (b) and (c ) should be switched.
• Page 415 Solution to Section 2.3, Exercise 7 should be

  Since 17 participated in both activities, 30 of the tennis players only played tennis and 25 of the swimmers only swam. Therefore, 17+30+25=72 of those who were surveyed participated in an activity and so 18 did not.

  Note: You could alternatively compute the number who participated as 47+42-17=72.(Found by Alex DeCourcy)
• Page 418 (page 251 of Part 1): Solution to 1 (c ) in Section 3.2, the right-most column heading should be \( p \lor \lnot p \)
• Page 435 (page 275 of Part 1), solution to exercise 3(iii): the relation is not symmetric and not transitive. (Found by a student at Luzurne County CC)
• Page 459 (of the full version)- solutions to Section 11.4 exercises - the solutions are completely mixed up. Click here for the corrected solutions. (Found by a student at Luzurne County CC)
• Page 490 (of the full version) Solutions to section 16.3 - Number 5(d): the polynomial in this part is reducible over $ {\mathbb{Z}}_2 $, but its factorization is $ (x^2 + x + 1)^2 $. (found by William Jozefczyk)

Version 1.0 - March 2012

• Page 23 - Exercise #4(b) - the subscript on the left should be i, not 1. (Found by a student at Luzurne County CC)
• Page 39 - The end of Example 2.4.8 should be \( . . . = 6 x^2 y^2 \). (Found by a student at Luzurne County CC)
• Page 36 (Section 2.3): Exercise 7 is flawed. It should be replaced with

  A survey of 90 people, 47 of them played tennis and 42 of them swam. If 17 of the them participated in both activities, how many of them participated in neither.

• Page 51 Fifth line below the heading Hierarchy of Logical Operations: The first sentence on that line should end with "\( . . . (p \land q) \lor r. \)"
• Page 52 Exercise 2(e): All parentheses should be dropped to read \( \lnot p \lor \lnot q \).
• Page 378 7th line of Example 16.8.1: funciton -> function
• Page 388 (Section 16.3) The proof of Theorem 16.3.4 was not properly formatted. It should be

  Proof: Let \(a \in F\) be a zero of \(f(x)\). Then \(f(x) = (x - a) \cdot q_1(x)\), \(q_1(x)\in F[x]\), by Theorem 16.3.3. If \(b \in F\) is a zero of \(q_1(x)\), then again by Theorem 16.3.3, \(f(x) = (x - a)(x - b)q_2(x)\), \(q_2(x)\in F[x]\). Continue this process, which must terminate in at most $n$ steps since the degree of \(q_k(x)\) would be \(n-k\). $\blacksquare $

• Solution to Problem 1 of Section 3.7: P(n) should be \(1 + 3 + 5 + \cdots + (2n-1) = n^2 \). Also, in the first line of the induction step, there is a space missing between "some" and "\(n\ge 1 \)".