Discrete mathematics has now established its place in most undergraduate mathematics courses. This textbook provides a concise, readable and accessible introduction to a number of topics in this area, such as enumeration, graph theory, Latin squares and designs. It is aimed at second-year undergraduate mathematics students, and provides them with many of the basic techniques, ideas and results. It contains many worked examples, and each chapter ends with a large number of exercises, with hints or solutions provided for most of them. As well as including standard topics such as binomial coefficients, recurrence, the inclusion-exclusion principle, trees, Hamiltonian and Eulerian graphs, Latin squares and finite projective planes, the text also includes material on the ménage problem, magic squares, Catalan and Stirling numbers, and tournament schedules.
Author(s): Ian Anderson
Series: Springer Undergraduate Mathematics Series
Edition: 1
Publisher: Springer
Year: 2002
Language: English
Pages: 200
Ian Anderson "A First Course in Discrete Mathematics" (2002) ......Page 1
Preface ......Page 6
Contents ......Page 8
1.1 Basic Principles ......Page 10
1.2 Factorials ......Page 11
1.3 Selections ......Page 12
1.4 Binomial Coefficients and Pascal’s Triangle ......Page 15
1.5 Selections with Repetitions ......Page 19
1.6 A Useful Matrix Inversion ......Page 22
2.1 Some Examples ......Page 28
2.2 The Auxiliary Equation Method ......Page 32
2.3 Generating Functions ......Page 35
2.4 Derangements ......Page 37
2.5 Sorting Algorithms ......Page 41
2.6 Catalan Numbers ......Page 43
3.1 The Concept of a Graph ......Page 52
3.2 Paths in Graphs ......Page 55
3.3 Trees ......Page 56
3.4 Spanning Trees ......Page 59
3.5 Bipartite Graphs ......Page 61
3.6 Planarity ......Page 63
3.7 Polyhedra ......Page 69
4.1 Hamiltonian Graphs ......Page 78
4.2 Planarity and Hamiltonian Graphs ......Page 80
4.3 The Travelling Salesman Problem ......Page 83
4.4 Gray Codes ......Page 85
4.5 Eulerian Graphs ......Page 87
4.6 Eulerian Digraphs ......Page 90
5.1 Partitions of a Set ......Page 98
5.2 Stirling Numbers ......Page 100
5.3 Counting Functions ......Page 103
5.4 Vertex Colourings of Graphs ......Page 105
5.5 Edge Colourings of Graphs ......Page 108
6.1 The Principle ......Page 116
6.2 Counting Surjections ......Page 121
6.3 Counting Labelled Trees ......Page 122
6.4 Scrabble ......Page 123
6.5 The Ménage Problem ......Page 124
7.1 Latin Squares and Orthogonality ......Page 130
7.2 Magic Squares ......Page 134
7.3 Systems of Distinct Representatives ......Page 136
7.4 From Latin Squares to Affine Planes ......Page 140
8.1 The Circle Method ......Page 146
8.2 Bipartite Tournaments and 1-Factorisations of Kn,n ......Page 151
8.3 Tournaments from Orthogonal Latin Squares ......Page 154
9.1 Balanced Incomplete Block Designs ......Page 158
9.2 Resolvable Designs ......Page 165
9.3 Finite Projective Planes ......Page 168
9.4 Hadainard Matrices and Designs ......Page 170
9.5 Difference Methods ......Page 174
9.6 Hadamard Matrices and Codes ......Page 176
Appendix ......Page 188
Solutions ......Page 192
Further Reading ......Page 204
Bibliography ......Page 206
Index ......Page 208
