DISCRETE MATHEMATICS
FIFTH EDITION
John A. Dossey
Illinois State University
Albert D. Otto
Illinois State University
Lawrence E. Spence
Illinois State University
Charles Vanden Eynden
Illinois State University
INSTRUCTOR’S
SOLUTIONS MANUAL

Contents
1 An Introduction to Combinatorial Problems and Techniques 1
1.1 The Time to Complete a Project . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 A Matching Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 A Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Algorithms and Their Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . 4
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Sets, Relations, and Functions 6
2.1 Set Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Partial Ordering Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.6 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3 Coding Theory 14
3.1 Congruence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 The Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.3 The RSA Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.4 Error-Detecting and Error-Correcting Codes . . . . . . . . . . . . . . . . . . 17
3.5 Matrix Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.6 Matrix Codes That Correct All Single-Digit Errors . . . . . . . . . . . . . . . 19
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
iii

Table of Contents
4 Graphs 22
4.1 Graphs and Their Representations . . . . . . . . . . . . . . . . . . . . . . . . 22
4.2 Paths and Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.3 Shortest Paths and Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.4 Coloring a Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.5 Directed Graphs and Multigraphs . . . . . . . . . . . . . . . . . . . . . . . . 30
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5 Trees 36
5.1 Properties of Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.2 Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.3 Depth-First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.4 Rooted Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.5 Binary Trees and Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.6 Optimal Binary Trees and Binary Search Trees . . . . . . . . . . . . . . . . . 51
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6 Matching 63
6.1 Systems of Distinct Representatives . . . . . . . . . . . . . . . . . . . . . . . 63
6.2 Matchings in Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6.3 A Matching Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.4 Applications of the Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.5 The Hungarian Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
7 Network Flows 68
7.1 Flows and Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
7.2 A Flow Augmentation Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 70
7.3 The Max-Flow Min-Cut Theorem . . . . . . . . . . . . . . . . . . . . . . . . 73
7.4 Flows and Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
iv

Loading page 4...

Table of Contents
8 Counting Techniques 78
8.1 Pascal’s Triangle and the Binomial Theorem . . . . . . . . . . . . . . . . . . 78
8.2 Three Fundamental Principles . . . . . . . . . . . . . . . . . . . . . . . . . . 78
8.3 Permutations and Combinations . . . . . . . . . . . . . . . . . . . . . . . . . 79
8.4 Arrangements and Selections with Repetitions . . . . . . . . . . . . . . . . . 79
8.5 Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
8.6 The Principle of Inclusion-Exclusion . . . . . . . . . . . . . . . . . . . . . . . 81
8.7 Generating Permutations and r-Combinations . . . . . . . . . . . . . . . . . 82
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
9 Recurrence Relations and Generating Functions 84
9.1 Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
9.2 The Method of Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
9.3 Linear Difference Equations with Constant Coefficients . . . . . . . . . . . . 91
9.4∗ Analyzing the Efficiency of Algorithms with Recurrence Relations . . . . . . 94
9.5 Counting with Generating Functions . . . . . . . . . . . . . . . . . . . . . . . 99
9.6 The Algebra of Generating Functions . . . . . . . . . . . . . . . . . . . . . . 100
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
10 Combinatorial Circuits and Finite State Machines 105
10.1 Logical Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
10.2 Creating Combinatorial Circuits . . . . . . . . . . . . . . . . . . . . . . . . . 107
10.3 Karnaugh Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
10.4 Finite State Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
v

Loading page 5...

Table of Contents
Appendices 120
A An Introduction to Logic and Proof 120
A.1 Statements and Connectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
A.2 Logical Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
A.3 Methods of Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
B Matrices 130
vi

Loading page 6...

Loading page 7...

Loading page 8...

1.2 A Matching Problem
1.2 A MATCHING PROBLEM
2. 720 4. 210 6. 84 8. 1680
10. 19,958,400 12. 1
8 14. 5040 16. 126
18. 210 20. 119 22. 1320 24. 5040
26. 240 28. 1200
1.3 A KNAPSACK PROBLEM
2. T 4. F 6. F 8. F
10. T 12. T 14. T 16. no
18. yes; 32
20. ∅, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4},
{1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}; 16
22. 128 24. 1024 26. 256 28. 26
30. {1, 4, 6, 7, 8, 9, 10, 11, 12}
1.4 ALGORITHMS AND THEIR EFFICIENCY
2. yes; 0 4. no
6. no 8. −1, 9, 84; 3, 17, 84
10.

Loading page 9...

Loading page 10...

Loading page 11...

Loading page 12...

Loading page 13...

Chapter 2 Sets, Relations, and Functions
2.3 PARTIAL ORDERING RELATIONS
2. not antisymmetric 4. partial ordering
6. not antisymmetric 8. not antisymmetric
10.
1
3
4
2
12.
{1, 2, 3, 4}

{3, 4}{1, 2} {1, 3} {1, 4} {2, 3} {2, 4}
14. R = {(a, a), (b, b), (b, a), (c, c), (c, b), (c, a), (d, d), (d, a)}
16. R = {(1, 1), (2, 2), (2, 1), (2, 4), (4, 4), (8, 8), (8, 4)}
18. The maximal elements are {1}, {2}, and {3}; the only minimal element is {1, 2, 3}.
20. The only minimal element is 0; there are no maximal elements.
22. One possible sequence is 1, 3, 2, 4.
24. One possible sequence is 1, 3, 2, 6, 4, 12.
26. Let S denote the set of residents of Illinois and R be defined so that x R y means that
x is a sister of y

Loading page 14...

2.3 Partial Ordering Relations
32.
(9, 4)
(9, 2)
(8, 4)
(8, 2)
(7, 4)
(7, 2)
(9, 6)
(9, 3)
(8, 6)
(8, 3)
(7, 6)
(7, 3)
36. (a) Suppose that y is element of S such that x R y is false. If there is no element
y1 in S such that y1 R y, then y is a minimal element of S, contradicting that x
is the unique minimal element of S. Thus there must be such an element y1. If
there is no element y2 in S such that y2 R y1, then y1 is a minimal element of S,
another contradiction. So there must be such an element y2. Because S is finite,
continuing in this manner must produce a minimal element yk of S different from
x. Because x is the unique minimal element of S, the assumption that there is
an element y of S such that x R y is false must be incorrect. Thus x R s is true
for every s ∈ S.
(b) Let Z denote the set of integers and S = Z ∪ {∅}. Let R be the relation defined
on S by x R y if and only if one of the following holds: (i) x, y ∈ Z and x ≤ y, or
(ii) x = y = ∅. Then ∅ is the unique minimal element in

Loading page 15...

Loading page 16...

2.5 Mathematical Induction
2.5 MATHEMATICAL INDUCTION
2. 7, 9, 13, 21, 37, 69
4. xn =
{x if n = 1
x · xn−1 if n ≥ 2
6. Let xn denote the nth odd positive integer. Then xn =
{1 if n = 1
xn−1 + 2 if n ≥ 2.
8. If k = 1, the sets {x1, x2, . . . , xk} and {x2, x3, . . . , xk+1} are disjoint.
10. If k = 0, the induction hypothesis cannot be applied to ak−1.
28. s0 + s1 + · · · + sn = (n + 1) (s0 + nd
2
)
2.6 APPLICATIONS
2. 56 4. 924
6. 120 8. 715
10. n 12. r!
14. 31 16. 4096

Loading page 17...

Loading page 18...

Chapter 2 Supplementary Exercises
52. Let S denote the set of all subsets of {1, 2, 3} that contain at most two elements, and
let R be the relation “is a subset of.” If A = {1}, B = {2}, and C = {3}, then
A ∨ B = {1, 2}, B ∨ C = {2, 3}, and A ∨ C = {1, 3}, but (A ∨ B) ∨ C does not exist.
54. [n] = {−n, n}
56. f (x) =
⎧
⎨
⎩
x if x ≡ 0 (mod 3)
x − 1 if x ≡ 1 (mod 3)
x − 2 if x ≡ 2 (mod 3)
13

Loading page 19...

Chapter 3
Coding Theory
3.1 CONGRUENCE
2. The quotient q is 3, and the remainder r is 0.
4. q = 12 and r = 7 6. q = −4 and r = 17
8. q = −6 and r = 9 10. p ≡ q (mod m)
12. p ≡ q (mod m) 14. p ≡ q (mod m)
16. p ≡ q (mod m) 18. [5]
20. [4] 22. [2]
24. [8] 26. [3]
28. [5] 30. [3]
32. [6] 34. [1]
36. [4] 38. 11 A.M.
40. 5 42. 3
44. February, March, and November
46. [2] = [10] = [−6]; [7] = [39] = [−1] = [−17]; [45] = [−3]
14

Loading page 20...

Loading page 21...

Loading page 22...

Loading page 23...

Loading page 24...

Loading page 25...

Loading page 26...

Loading page 27...

Loading page 28...

Loading page 29...

Loading page 30...

Loading page 31...

Solution Manual for Discrete Mathematics (Classic Version), 5th Edition

Study Now!

Document Details

Related Documents

Test Bank for Biocalculus: Calculus for Life Sciences, 1st Edition

Test Bank for Current Medical Diagnosis and Treatment 2023 (Ie), 62nd Edition (Chapters 27)

Test Bank For Math in Our World, 4th Edition

Single Variable Calculus, 8th Edition Test Bank

Test Bank for Calculus: Concepts and Contexts, Enhanced 4th Edition

Test Bank For Discrete Mathematics With Applications, 5th Edition

Test Bank for Calculus, 10th Edition

Test Bank for Calculus of a Single Variable, 10th Edition

Test Bank For College Geometry: A Problem Solving Approach with Applications, 2nd Edition

Test Bank for Precalculus Enhanced with Graphing Utilities, 6th Edition