第1页 / 共995页
第2页 / 共995页
第3页 / 共995页
第4页 / 共995页
第5页 / 共995页
第6页 / 共995页
第7页 / 共995页
第8页 / 共995页
Mathematics for Computer Science 2017版.pdf
I Proofs
Introduction
0.1 References
1 What is a Proof?
1.1 Propositions
1.2 Predicates
1.3 The Axiomatic Method
1.4 Our Axioms
1.5 Proving an Implication
1.6 Proving an ``If and Only If''
1.7 Proof by Cases
1.8 Proof by Contradiction
1.9 Good Proofs in Practice
1.10 References
Problem 1.1
Problem 1.2
Problem 1.3
Problem 1.4
Problem 1.5
Problem 1.6
Problem 1.7
Problem 1.8
Problem 1.9
Problem 1.10
Problem 1.11
Problem 1.12
Problem 1.13
Problem 1.14
Problem 1.15
Problem 1.16
Problem 1.17
Problem 1.18
Problem 1.19
Problem 1.20
Problem 1.21
Problem 1.22
Problem 1.23
Problem 1.24
Problem 1.25
Problem 1.26
2 The Well Ordering Principle
2.1 Well Ordering Proofs
2.2 Template for Well Ordering Proofs
2.3 Factoring into Primes
2.4 Well Ordered Sets
Problem 2.1
Problem 2.2
Problem 2.3
Problem 2.4
Problem 2.5
Problem 2.6
Problem 2.7
Problem 2.8
Problem 2.9
Problem 2.10
Problem 2.11
Problem 2.12
Problem 2.13
Problem 2.14
Problem 2.15
Problem 2.16
Problem 2.17
Problem 2.18
Problem 2.19
Problem 2.20
Problem 2.21
Problem 2.22
Problem 2.23
3 Logical Formulas
3.1 Propositions from Propositions
3.2 Propositional Logic in Computer Programs
3.3 Equivalence and Validity
3.4 The Algebra of Propositions
3.5 The SAT Problem
3.6 Predicate Formulas
3.7 References
Problem 3.1
Problem 3.2
Problem 3.3
Problem 3.4
Problem 3.5
Problem 3.6
Problem 3.7
Problem 3.8
Problem 3.9
Problem 3.10
Problem 3.11
Problem 3.12
Problem 3.13
Problem 3.14
Problem 3.15
Problem 3.16
Problem 3.17
Problem 3.18
Problem 3.19
Problem 3.20
Problem 3.21
Problem 3.22
Problem 3.23
Problem 3.24
Problem 3.25
Problem 3.26
Problem 3.27
Problem 3.28
Problem 3.29
Problem 3.30
Problem 3.31
Problem 3.32
Problem 3.33
Problem 3.34
Problem 3.35
Problem 3.36
Problem 3.37
Problem 3.38
Problem 3.39
Problem 3.40
Problem 3.41
4 Mathematical Data Types
4.1 Sets
4.2 Sequences
4.3 Functions
4.4 Binary Relations
4.5 Finite Cardinality
Problem 4.1
Problem 4.2
Problem 4.3
Problem 4.4
Problem 4.5
Problem 4.6
Problem 4.7
Problem 4.8
Problem 4.9
Problem 4.10
Problem 4.11
Problem 4.12
Problem 4.13
Problem 4.14
Problem 4.15
Problem 4.16
Problem 4.17
Problem 4.18
Problem 4.19
Problem 4.20
Problem 4.21
Problem 4.22
Problem 4.23
Problem 4.24
Problem 4.25
Problem 4.26
Problem 4.27
Problem 4.28
Problem 4.29
Problem 4.30
Problem 4.31
Problem 4.32
Problem 4.33
Problem 4.34
Problem 4.35
Problem 4.36
Problem 4.37
5 Induction
5.1 Ordinary Induction
5.2 Strong Induction
5.3 Strong Induction vs. Induction vs. Well Ordering
Problem 5.1
Problem 5.2
Problem 5.3
Problem 5.4
Problem 5.5
Problem 5.6
Problem 5.7
Problem 5.8
Problem 5.9
Problem 5.10
Problem 5.11
Problem 5.12
Problem 5.13
Problem 5.14
Problem 5.15
Problem 5.16
Problem 5.17
Problem 5.18
Problem 5.19
Problem 5.20
Problem 5.21
Problem 5.22
Problem 5.23
Problem 5.24
Problem 5.25
Problem 5.26
Problem 5.27
Problem 5.28
Problem 5.29
Problem 5.30
Problem 5.31
Problem 5.32
Problem 5.33
6 State Machines
6.1 States and Transitions
6.2 The Invariant Principle
6.3 Partial Correctness & Termination
6.4 The Stable Marriage Problem
Problem 6.1
Problem 6.2
Problem 6.3
Problem 6.4
Problem 6.5
Problem 6.6
Problem 6.7
Problem 6.8
Problem 6.9
Problem 6.10
Problem 6.11
Problem 6.12
Problem 6.13
Problem 6.14
Problem 6.15
Problem 6.16
Problem 6.17
Problem 6.18
Problem 6.19
Problem 6.20
Problem 6.21
Problem 6.22
Problem 6.23
Problem 6.24
Problem 6.25
Problem 6.26
Problem 6.27
Problem 6.28
Problem 6.29
Problem 6.30
Problem 6.31
Problem 6.32
7 Recursive Data Types
7.1 Recursive Definitions and Structural Induction
7.2 Strings of Matched Brackets
7.3 Recursive Functions on Nonnegative Integers
7.4 Arithmetic Expressions
7.5 Games as a Recursive Data Type
7.6 Induction in Computer Science
Problem 7.1
Problem 7.2
Problem 7.3
Problem 7.4
Problem 7.5
Problem 7.6
Problem 7.7
Problem 7.8
Problem 7.9
Problem 7.10
Problem 7.11
Problem 7.12
Problem 7.13
Problem 7.14
Problem 7.15
Problem 7.16
Problem 7.17
Problem 7.18
Problem 7.19
Problem 7.20
Problem 7.21
Problem 7.22
Problem 7.23
Problem 7.24
Problem 7.25
Problem 7.26
Problem 7.27
Problem 7.28
Problem 7.29
Problem 7.30
Problem 7.31
Problem 7.32
8 Infinite Sets
8.1 Infinite Cardinality
8.2 The Halting Problem
8.3 The Logic of Sets
8.4 Does All This Really Work?
Problem 8.1
Problem 8.2
Problem 8.3
Problem 8.4
Problem 8.5
Problem 8.6
Problem 8.7
Problem 8.8
Problem 8.9
Problem 8.10
Problem 8.11
Problem 8.12
Problem 8.13
Problem 8.14
Problem 8.15
Problem 8.16
Problem 8.17
Problem 8.18
Problem 8.19
Problem 8.20
Problem 8.21
Problem 8.22
Problem 8.23
Problem 8.24
Problem 8.25
Problem 8.26
Problem 8.27
Problem 8.28
Problem 8.29
Problem 8.30
Problem 8.31
Problem 8.32
Problem 8.33
Problem 8.34
Problem 8.35
Problem 8.36
Problem 8.37
Problem 8.38
Problem 8.39
II Structures
Introduction
9 Number Theory
9.1 Divisibility
9.2 The Greatest Common Divisor
9.3 Prime Mysteries
9.4 The Fundamental Theorem of Arithmetic
9.5 Alan Turing
9.6 Modular Arithmetic
9.7 Remainder Arithmetic
9.8 Turing's Code (Version 2.0)
9.9 Multiplicative Inverses and Cancelling
9.10 Euler's Theorem
9.11 RSA Public Key Encryption
9.12 What has SAT got to do with it?
9.13 References
Problem 9.1
Problem 9.2
Problem 9.3
Problem 9.4
Problem 9.5
Problem 9.6
Problem 9.7
Problem 9.8
Problem 9.9
Problem 9.10
Problem 9.11
Problem 9.12
Problem 9.13
Problem 9.14
Problem 9.15
Problem 9.16
Problem 9.17
Problem 9.18
Problem 9.19
Problem 9.20
Problem 9.21
Problem 9.22
Problem 9.23
Problem 9.24
Problem 9.25
Problem 9.26
Problem 9.27
Problem 9.28
Problem 9.29
Problem 9.30
Problem 9.31
Problem 9.32
Problem 9.33
Problem 9.34
Problem 9.35
Problem 9.36
Problem 9.37
Problem 9.38
Problem 9.39
Problem 9.40
Problem 9.41
Problem 9.42
Problem 9.43
Problem 9.44
Problem 9.45
Problem 9.46
Problem 9.47
Problem 9.48
Problem 9.49
Problem 9.50
Problem 9.51
Problem 9.52
Problem 9.53
Problem 9.54
Problem 9.55
Problem 9.56
Problem 9.57
Problem 9.58
Problem 9.59
Problem 9.60
Problem 9.61
Problem 9.62
Problem 9.63
Problem 9.64
Problem 9.65
Problem 9.66
Problem 9.67
Problem 9.68
Problem 9.69
Problem 9.70
Problem 9.71
Problem 9.72
Problem 9.73
Problem 9.74
Problem 9.75
Problem 9.76
Problem 9.77
Problem 9.78
Problem 9.79
Problem 9.80
Problem 9.81
Problem 9.82
Problem 9.83
Problem 9.84
10 Directed graphs & Partial Orders
10.1 Vertex Degrees
10.2 Walks and Paths
10.3 Adjacency Matrices
10.4 Walk Relations
10.5 Directed Acyclic Graphs & Scheduling
10.6 Partial Orders
10.7 Representing Partial Orders by Set Containment
10.8 Linear Orders
10.9 Product Orders
10.10 Equivalence Relations
10.11 Summary of Relational Properties
Problem 10.1
Problem 10.2
Problem 10.3
Problem 10.4
Problem 10.5
Problem 10.6
Problem 10.7
Problem 10.8
Problem 10.9
Problem 10.10
Problem 10.11
Problem 10.12
Problem 10.13
Problem 10.14
Problem 10.15
Problem 10.16
Problem 10.17
Problem 10.18
Problem 10.19
Problem 10.20
Problem 10.21
Problem 10.22
Problem 10.23
Problem 10.24
Problem 10.25
Problem 10.26
Problem 10.27
Problem 10.28
Problem 10.29
Problem 10.30
Problem 10.31
Problem 10.32
Problem 10.33
Problem 10.34
Problem 10.35
Problem 10.36
Problem 10.37
Problem 10.38
Problem 10.39
Problem 10.40
Problem 10.41
Problem 10.42
Problem 10.43
Problem 10.44
Problem 10.45
Problem 10.46
Problem 10.47
Problem 10.48
Problem 10.49
Problem 10.50
Problem 10.51
Problem 10.52
Problem 10.53
Problem 10.54
Problem 10.55
Problem 10.56
Problem 10.57
Problem 10.58
Problem 10.59
11 Communication Networks
11.1 Routing
11.2 Routing Measures
11.3 Network Designs
Problem 11.1
Problem 11.2
Problem 11.3
Problem 11.4
Problem 11.5
Problem 11.6
Problem 11.7
Problem 11.8
12 Simple Graphs
12.1 Vertex Adjacency and Degrees
12.2 Sexual Demographics in America
12.3 Some Common Graphs
12.4 Isomorphism
12.5 Bipartite Graphs & Matchings
12.6 Coloring
12.7 Simple Walks
12.8 Connectivity
12.9 Forests & Trees
12.10 References
Problem 12.1
Problem 12.2
Problem 12.3
Problem 12.4
Problem 12.5
Problem 12.6
Problem 12.7
Problem 12.8
Problem 12.9
Problem 12.10
Problem 12.11
Problem 12.12
Problem 12.13
Problem 12.14
Problem 12.15
Problem 12.16
Problem 12.17
Problem 12.18
Problem 12.19
Problem 12.20
Problem 12.21
Problem 12.22
Problem 12.23
Problem 12.24
Problem 12.25
Problem 12.26
Problem 12.27
Problem 12.28
Problem 12.29
Problem 12.30
Problem 12.31
Problem 12.32
Problem 12.33
Problem 12.34
Problem 12.35
Problem 12.36
Problem 12.37
Problem 12.38
Problem 12.39
Problem 12.40
Problem 12.41
Problem 12.42
Problem 12.43
Problem 12.44
Problem 12.45
Problem 12.46
Problem 12.47
Problem 12.48
Problem 12.49
Problem 12.50
Problem 12.51
Problem 12.52
Problem 12.53
Problem 12.54
Problem 12.55
Problem 12.56
Problem 12.57
Problem 12.58
Problem 12.59
Problem 12.60
Problem 12.61
Problem 12.62
Problem 12.63
13 Planar Graphs
13.1 Drawing Graphs in the Plane
13.2 Definitions of Planar Graphs
13.3 Euler's Formula
13.4 Bounding the Number of Edges in a Planar Graph
13.5 Returning to K5 and K3,3
13.6 Coloring Planar Graphs
13.7 Classifying Polyhedra
13.8 Another Characterization for Planar Graphs
Problem 13.1
Problem 13.2
Problem 13.3
Problem 13.4
Problem 13.5
Problem 13.6
Problem 13.7
Problem 13.8
Problem 13.9
III Counting
Introduction
14 Sums and Asymptotics
14.1 The Value of an Annuity
14.2 Sums of Powers
14.3 Approximating Sums
14.4 Hanging Out Over the Edge
14.5 Products
14.6 Double Trouble
14.7 Asymptotic Notation
Problem 14.1
Problem 14.2
Problem 14.3
Problem 14.4
Problem 14.5
Problem 14.6
Problem 14.7
Problem 14.8
Problem 14.9
Problem 14.10
Problem 14.11
Problem 14.12
Problem 14.13
Problem 14.14
Problem 14.15
Problem 14.16
Problem 14.17
Problem 14.18
Problem 14.19
Problem 14.20
Problem 14.21
Problem 14.22
Problem 14.23
Problem 14.24
Problem 14.25
Problem 14.26
Problem 14.27
Problem 14.28
Problem 14.29
Problem 14.30
Problem 14.31
Problem 14.32
Problem 14.33
Problem 14.34
Problem 14.35
Problem 14.36
Problem 14.37
Problem 14.38
Problem 14.39
Problem 14.40
Problem 14.41
15 Cardinality Rules
15.1 Counting One Thing by Counting Another
15.2 Counting Sequences
15.3 The Generalized Product Rule
15.4 The Division Rule
15.5 Counting Subsets
15.6 Sequences with Repetitions
15.7 Counting Practice: Poker Hands
15.8 The Pigeonhole Principle
15.9 Inclusion-Exclusion
15.10 Combinatorial Proofs
15.11 References
Problem 15.1
Problem 15.2
Problem 15.3
Problem 15.4
Problem 15.5
Problem 15.6
Problem 15.7
Problem 15.8
Problem 15.9
Problem 15.10
Problem 15.11
Problem 15.12
Problem 15.13
Problem 15.14
Problem 15.15
Problem 15.16
Problem 15.17
Problem 15.18
Problem 15.19
Problem 15.20
Problem 15.21
Problem 15.22
Problem 15.23
Problem 15.24
Problem 15.25
Problem 15.26
Problem 15.27
Problem 15.28
Problem 15.29
Problem 15.30
Problem 15.31
Problem 15.32
Problem 15.33
Problem 15.34
Problem 15.35
Problem 15.36
Problem 15.37
Problem 15.38
Problem 15.39
Problem 15.40
Problem 15.41
Problem 15.42
Problem 15.43
Problem 15.44
Problem 15.45
Problem 15.46
Problem 15.47
Problem 15.48
Problem 15.49
Problem 15.50
Problem 15.51
Problem 15.52
Problem 15.53
Problem 15.54
Problem 15.55
Problem 15.56
Problem 15.57
Problem 15.58
Problem 15.59
Problem 15.60
Problem 15.61
Problem 15.62
Problem 15.63
Problem 15.64
Problem 15.65
Problem 15.66
Problem 15.67
Problem 15.68
Problem 15.69
Problem 15.70
Problem 15.71
Problem 15.72
Problem 15.73
Problem 15.74
Problem 15.75
Problem 15.76
Problem 15.77
16 Generating Functions
16.1 Infinite Series
16.2 Counting with Generating Functions
16.3 Partial Fractions
16.4 Solving Linear Recurrences
16.5 Formal Power Series
16.6 References
Problem 16.1
Problem 16.2
Problem 16.3
Problem 16.4
Problem 16.5
Problem 16.6
Problem 16.7
Problem 16.8
Problem 16.9
Problem 16.10
Problem 16.11
Problem 16.12
Problem 16.13
Problem 16.14
Problem 16.15
Problem 16.16
Problem 16.17
Problem 16.18
Problem 16.19
Problem 16.20
Problem 16.21
Problem 16.22
Problem 16.23
Problem 16.24
Problem 16.25
IV Probability
Introduction
17 Events and Probability Spaces
17.1 Let's Make a Deal
17.2 The Four Step Method
17.3 Strange Dice
17.4 The Birthday Principle
17.5 Set Theory and Probability
17.6 References
Problem 17.1
Problem 17.2
Problem 17.3
Problem 17.4
Problem 17.5
Problem 17.6
Problem 17.7
Problem 17.8
Problem 17.9
Problem 17.10
Problem 17.11
Problem 17.12
18 Conditional Probability
18.1 Monty Hall Confusion
18.2 Definition and Notation
18.3 The Four-Step Method for Conditional Probability
18.4 Why Tree Diagrams Work
18.5 The Law of Total Probability
18.6 Simpson's Paradox
18.7 Independence
18.8 Mutual Independence
18.9 Probability versus Confidence
Problem 18.1
Problem 18.2
Problem 18.3
Problem 18.4
Problem 18.5
Problem 18.6
Problem 18.7
Problem 18.8
Problem 18.9
Problem 18.10
Problem 18.11
Problem 18.12
Problem 18.13
Problem 18.14
Problem 18.15
Problem 18.16
Problem 18.17
Problem 18.18
Problem 18.19
Problem 18.20
Problem 18.21
Problem 18.22
Problem 18.23
Problem 18.24
Problem 18.25
Problem 18.26
Problem 18.27
Problem 18.28
Problem 18.29
Problem 18.30
Problem 18.31
Problem 18.32
Problem 18.33
Problem 18.34
Problem 18.35
Problem 18.36
Problem 18.37
19 Random Variables
19.1 Random Variable Examples
19.2 Independence
19.3 Distribution Functions
19.4 Great Expectations
19.5 Linearity of Expectation
Problem 19.1
Problem 19.2
Problem 19.3
Problem 19.4
Problem 19.5
Problem 19.6
Problem 19.7
Problem 19.8
Problem 19.9
Problem 19.10
Problem 19.11
Problem 19.12
Problem 19.13
Problem 19.14
Problem 19.15
Problem 19.16
Problem 19.17
Problem 19.18
Problem 19.19
Problem 19.20
Problem 19.21
Problem 19.22
Problem 19.23
Problem 19.24
Problem 19.25
Problem 19.26
Problem 19.27
Problem 19.28
Problem 19.29
Problem 19.30
Problem 19.31
Problem 19.32
Problem 19.33
Problem 19.34
Problem 19.35
Problem 19.36
Problem 19.37
20 Deviation from the Mean
20.1 Markov's Theorem
20.2 Chebyshev's Theorem
20.3 Properties of Variance
20.4 Estimation by Random Sampling
20.5 Confidence in an Estimation
20.6 Sums of Random Variables
20.7 Really Great Expectations
Problem 20.1
Problem 20.2
Problem 20.3
Problem 20.4
Problem 20.5
Problem 20.6
Problem 20.7
Problem 20.8
Problem 20.9
Problem 20.10
Problem 20.11
Problem 20.12
Problem 20.13
Problem 20.14
Problem 20.15
Problem 20.16
Problem 20.17
Problem 20.18
Problem 20.19
Problem 20.20
Problem 20.21
Problem 20.22
Problem 20.23
Problem 20.24
Problem 20.25
Problem 20.26
Problem 20.27
Problem 20.28
Problem 20.29
Problem 20.30
Problem 20.31
Problem 20.32
Problem 20.33
Problem 20.34
Problem 20.35
Problem 20.36
Problem 20.37
Problem 20.38
21 Random Walks
21.1 Gambler's Ruin
21.2 Random Walks on Graphs
Problem 21.1
Problem 21.2
Problem 21.3
Problem 21.4
Problem 21.5
Problem 21.6
Problem 21.7
Problem 21.8
Problem 21.9
Problem 21.10
Problem 21.11
Problem 21.12
Problem 21.13
V Recurrences
Introduction
22 Recurrences
22.1 The Towers of Hanoi
22.2 Merge Sort
22.3 Linear Recurrences
22.4 Divide-and-Conquer Recurrences
22.5 A Feel for Recurrences
Problem 22.1
Problem 22.2
Problem 22.3
Problem 22.4
Bibliography
Glossary of Symbols
Index
“mcs” — 2017/4/4 — 11:03 — page i — #1
Mathematics for Computer Science
revised Tuesday 4th April, 2017, 11:03
Eric Lehman
Google Inc.
F Thomson Leighton
Department of Mathematics
and the Computer Science and AI Laboratory,
Massachussetts Institute of Technology;
Akamai Technologies
Albert R Meyer
Department of Electrical Engineering and Computer Science
and the Computer Science and AI Laboratory,
Massachussetts Institute of Technology
2016, Eric Lehman, F Tom Leighton, Albert R Meyer. This work is available under the
terms of the Creative Commons Attribution-ShareAlike 3.0 license.
“mcs” — 2017/4/4 — 11:03 — page ii — #2
“mcs” — 2017/4/4 — 11:03 — page iii — #3
Contents
I Proofs
Introduction 3
0.1 References
4
1 What is a Proof? 5
9
8
5
Propositions
Predicates
The Axiomatic Method
1.1
1.2
1.3
1.4 Our Axioms
Proving an Implication
1.5
Proving an “If and Only If”
1.6
Proof by Cases
1.7
1.8
Proof by Contradiction
1.9 Good Proofs in Practice
1.10 References
15
19
8
11
13
16
17
2 The Well Ordering Principle 29
29
Template for Well Ordering Proofs
Factoring into Primes
32
2.1 Well Ordering Proofs
2.2
2.3
2.4 Well Ordered Sets
3 Logical Formulas 47
33
30
48
Propositions from Propositions
Propositional Logic in Computer Programs
Equivalence and Validity
The Algebra of Propositions
The SAT Problem 62
Predicate Formulas
63
3.1
3.2
3.3
3.4
3.5
3.6
3.7 References
57
54
68
52
4 Mathematical Data Types 95
Sets
95
Sequences
Functions
4.1
100
4.2
101
4.3
4.4 Binary Relations
4.5
Finite Cardinality
103
107
“mcs” — 2017/4/4 — 11:03 — page iv — #4
iv
Contents
127
Strong Induction
Strong Induction vs. Induction vs. Well Ordering
136
143
5
6
Induction 127
5.1 Ordinary Induction
5.2
5.3
State Machines 163
6.1
6.2
6.3
6.4
States and Transitions
The Invariant Principle
Partial Correctness & Termination
The Stable Marriage Problem 177
163
164
172
207
215
7 Recursive Data Types 207
217
211
Strings of Matched Brackets
7.1 Recursive Definitions and Structural Induction
7.2
7.3 Recursive Functions on Nonnegative Integers
7.4 Arithmetic Expressions
7.5 Games as a Recursive Data Type
7.6
Infinite Sets 253
8.1
8.2
8.3
8.4 Does All This Really Work?
Infinite Cardinality
The Halting Problem 263
The Logic of Sets
Induction in Computer Science
222
226
254
267
271
8
II Structures
Introduction 295
9 Number Theory 297
297
309
302
The Greatest Common Divisor
Prime Mysteries
The Fundamental Theorem of Arithmetic
9.1 Divisibility
9.2
9.3
9.4
9.5 Alan Turing
9.6 Modular Arithmetic
9.7 Remainder Arithmetic
9.8
9.9 Multiplicative Inverses and Cancelling
9.10 Euler’s Theorem 329
9.11 RSA Public Key Encryption
320
Turing’s Code (Version 2.0)
323
334
318
314
311
325
“mcs” — 2017/4/4 — 11:03 — page v — #5
v
Contents
9.12 What has SAT got to do with it?
9.13 References
337
336
10 Directed graphs & Partial Orders 375
384
381
377
378
10.1 Vertex Degrees
10.2 Walks and Paths
10.3 Adjacency Matrices
10.4 Walk Relations
10.5 Directed Acyclic Graphs & Scheduling
10.6 Partial Orders
10.7 Representing Partial Orders by Set Containment
398
10.8 Linear Orders
10.9 Product Orders
398
10.10 Equivalence Relations
10.11 Summary of Relational Properties
385
399
393
401
11 Communication Networks 433
433
11.1 Routing
11.2 Routing Measures
11.3 Network Designs
12 Simple Graphs 453
434
437
453
455
457
12.1 Vertex Adjacency and Degrees
12.2 Sexual Demographics in America
12.3 Some Common Graphs
12.4 Isomorphism 459
12.5 Bipartite Graphs & Matchings
466
12.6 Coloring
12.7 Simple Walks
12.8 Connectivity
12.9 Forests & Trees
12.10 References
471
473
478
461
486
13 Planar Graphs 525
536
525
525
13.1 Drawing Graphs in the Plane
13.2 Definitions of Planar Graphs
13.3 Euler’s Formula
13.4 Bounding the Number of Edges in a Planar Graph
13.5 Returning to K5 and K3;3
13.6 Coloring Planar Graphs
13.7 Classifying Polyhedra
13.8 Another Characterization for Planar Graphs
538
541
539
544
397
537
“mcs” — 2017/4/4 — 11:03 — page vi — #6
vi
Contents
III Counting
Introduction 553
14 Sums and Asymptotics 555
556
568
14.1 The Value of an Annuity
562
14.2 Sums of Powers
14.3 Approximating Sums
564
14.4 Hanging Out Over the Edge
14.5 Products
574
14.6 Double Trouble
577
14.7 Asymptotic Notation
15 Cardinality Rules 605
580
605
606
613
616
15.1 Counting One Thing by Counting Another
15.2 Counting Sequences
15.3 The Generalized Product Rule
15.4 The Division Rule
15.5 Counting Subsets
15.6 Sequences with Repetitions
15.7 Counting Practice: Poker Hands
15.8 The Pigeonhole Principle
626
635
15.9 Inclusion-Exclusion
15.10 Combinatorial Proofs
641
15.11 References
621
645
609
618
16 Generating Functions 683
683
16.1 Infinite Series
16.2 Counting with Generating Functions
16.3 Partial Fractions
16.4 Solving Linear Recurrences
16.5 Formal Power Series
699
16.6 References
694
691
702
685
IV Probability
Introduction 721
17 Events and Probability Spaces 723
17.1 Let’s Make a Deal
723
“mcs” — 2017/4/4 — 11:03 — page vii — #7
vii
Contents
17.2 The Four Step Method
17.3 Strange Dice
17.4 The Birthday Principle
17.5 Set Theory and Probability
17.6 References
733
746
724
740
742
18 Conditional Probability 755
755
756
18.1 Monty Hall Confusion
18.2 Definition and Notation
18.3 The Four-Step Method for Conditional Probability
18.4 Why Tree Diagrams Work
18.5 The Law of Total Probability
18.6 Simpson’s Paradox
18.7 Independence
772
18.8 Mutual Independence
18.9 Probability versus Confidence
760
770
774
778
768
19 Random Variables 807
758
807
19.1 Random Variable Examples
19.2 Independence
19.3 Distribution Functions
19.4 Great Expectations
819
19.5 Linearity of Expectation
809
830
20 Deviation from the Mean 861
810
20.1 Markov’s Theorem 861
20.2 Chebyshev’s Theorem 864
20.3 Properties of Variance
868
20.4 Estimation by Random Sampling
20.5 Confidence in an Estimation
20.6 Sums of Random Variables
20.7 Really Great Expectations
877
879
888
874
21 Random Walks 913
21.1 Gambler’s Ruin
21.2 Random Walks on Graphs
913
923
V Recurrences
Introduction 941
22 Recurrences 943
“mcs” — 2017/4/4 — 11:03 — page viii — #8
viii
Contents
943
22.1 The Towers of Hanoi
22.2 Merge Sort
22.3 Linear Recurrences
22.4 Divide-and-Conquer Recurrences
22.5 A Feel for Recurrences
946
950
964
957
Bibliography 971
Glossary of Symbols 975
Index 979
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
