离散数学引论 英文PDF电子书下载

1．Counting and Binomial Coefficients 1

1.1 Basic Principles 1

1.2 Factorials 2

1.3 Selections 3

1.4 Binomial Coefficients and Pascal's Triangle 6

1.5 Selections with Repetitions 10

1.6 A Useful Matrix Inversion 13

2．Recurrence 19

2.1 Some Examples 19

2.2 The Auxiliary Equation Method 23

2.3 Generating Functions 26

2.4 Derangements 28

2.5 Sorting Algorithms 32

2.6 Catalan Numbers 34

3．Introduction to Graphs 43

3.1 The Concept of a Graph 43

3.2 Paths in Graphs 46

3.3 Trees 47

3.4 Spanning Trees 50

3.5 Bipartite Graphs 52

3.6 Planarity 54

3.7 Polyhedra 60

4．Travelling Round a Graph 69

4.1 Hamiltonian Graphs 69

4.2 Planarity and Hamiltonian Graphs 71

4.3 The Travelling Salesman Problem 74

4.4 Gray Codes 76

4.5 Eulerian Graphs 78

4.6 Eulerian Digraphs 81

5．Partitions and Colourings 89

5.1 Partitions of a Set 89

5.2 Stirling Numbers 91

5.3 Counting Functions 94

5.4 Vertex Colourings of Graphs 96

5.5 Edge Colourings of Graphs 99

6．The Inclusion-Exclusion Principle 107

6.1 The Principle 107

6.2 Counting Surjections 112

6.3 Counting Labelled Trees 113

6.4 Scrabble 114

6.5 The Ménage Problem 115

7．Latin Squares and Hall's Theorem 121

7.1 Latin Squares and Orthogonality 121

7.2 Magic Squares 125

7.3 Systems of Distinct Representatives 127

7.4 From Latin Squares to Affine Planes 131

8．Schedules and 1-Factorisations 137

8.1 The Circle Method 137

8.2 Bipartite Tournaments and 1-Factorisations of Kn,n 142

8.3 Tournaments from Orthogonal Latin Squares 145

9．Introduction to Designs 149

9.1 Balanced Incomplete Block Designs 149

9.2 Resolvable Designs 156

9.3 Finite Projective Planes 159

9.4 Hadamard Matrices and Designs 161

9.5 Difference Methods 165

9.6 Hadamard Matrices and Codes 167

Appendix 179

Solutions 183

Further Reading 195

Bibliography 197

Index 199