Part I. Numbers and Counting Page 1 1. Integers Page 3 1.1. Arithmetic Page 3 1.2. Ordering the integers Page 5 1.3. Recursive definitions Page 8 1.4. The principle of induction Page 11 1.5. Quotient and remainder Page 14 1.6. Divisibility Page 17 1.7. The greatest common divisor Page 18 1.8. Factorization into primes Page 21 1.9. Miscellaneous exercises Page 25 2. Functions and counting Page 27 2.1. Functions Page 27 2.2. Surjections, injections, bijections Page 29 2.3. Counting Page 33 2.4. The pigeonhole principle Page 36 2.5. Finite or infinite? Page 38 2.6. Miscellaneous exercises Page 42 3. Principles of counting Page 44 3.1. The addition principle Page 44 3.2. Counting sets of pairs Page 46 3.3. Euler's function Page 49 3.4. Functions, words, and selections Page 52 3.5. Injections as ordered selections without repetition Page 54 3.6. Permutations Page 55 3.7. Miscellaneous exercises Page 59 4. Subsets and designs Page 62 4.1. Binomial numbers Page 62 4.2. Unordered selections with repetition Page 66 4.3. The binomial theorem Page 68 4.4. The sieve principle Page 71 4.5. Some arithmetical applications Page 74 4.6. Designs Page 79 4.7. t-designs Page 83 4.8. Miscellaneous exercises Page 86 5. Partition, classification, and distribution Page 89 5.1. Partitions of a set Page 89 5.2. Classification and equivalence relations Page 92 5.3. Distributions and the multinomial numbers Page 95 5.4. Partitions of a positive integer Page 100 5.5. Classification of permutations Page 101 5.6. Odd and even permutations Page 105 5.7. Miscellaneous exercises Page 110 6. Modular arithmetic Page 113 6.1. Congruences Page 113 6.2. ℤₘ and its arithmetic Page 115 6.3. Invertible elements of ℤ Page 119 6.4. Cyclic constructions for designs Page 122 6.5. Latin squares Page 126 6.6. Miscellaneous exercises Page 129 Part II. Graphs and Algorithms Page 131 7. Algorithms and their efficiency Page 133 7.1. What is an algorithm? Page 133 7.2. The language of programs Page 135 7.3. Algorithms and programs Page 139 7.4. Proving that an algorithm is correct Page 142 7.5. Efficiency of algorithms Page 145 7.6. Growth rates: the O notation Page 148 7.7. Comparison of algorithms Page 150 7.8. Introduction to sorting algorithms Page 153 7.9. Miscellaneous exercises Page 156 8. Graphs Page 158 8.1. Graphs and their representation Page 158 8.2. Isomorphism of graphs Page 161 8.3. Valency Page 163 8.4. Paths and cycles Page 165 8.5. Trees Page 169 8.6. Colouring the vertices of a graph Page 171 8.7. The greedy algorithm for vertex-colouring Page 173 8.8. Miscellaneous exercises Page 177 9. Trees, sorting, and searching Page 180 9.1. Counting the leaves on a rooted tree Page 180 9.2. Trees and sorting algorithms Page 184 9.3. Spanning trees and the MST problem Page 189 9.4. Depth-first search Page 193 9.5. Breadth-first search Page 197 9.6. The shortest-path problem Page 201 9.7. Miscellaneous exercises Page 203 10. Bipartite graphs and matching problems Page 206 10.1. Relations and bipartite graphs Page 206 10.2. Edge-colourings of graphs Page 208 10.3. Application of edge-colouring latin squares Page 212 10.4. Matchings Page 215 10.5. Maximum matchings Page 219 10.6. Transversals for families of finite sets Page 222 10.7. Miscellaneous exercises Page 225 11. Digraphs, networks, and flows Page 228 11.1. Digraphs Page 228 11.2. Networks and critical paths Page 231 11.3. Flows and cuts Page 234 11.4. The max-flow min-cut theorem Page 237 11.5. The labelling algorithm for network flows Page 241 11.6. Miscellaneous exercises Page 245 12. Recursive techniques Page 248 12.1. Generalities about recursion Page 248 12.2. Linear recursion Page 250 12.3. Recursive bisection Page 253 12.4. Recursive optimization Page 255 12.5. The framework of dynamic programming Page 258 12.6. Examples of the dynamic programming method Page 261 12.7. Miscellaneous exercises Page 265 Part III. Algebraic Methods Page 269 13. Groups Page 271 13.1. The axioms for a group Page 271 13.2. Examples of groups Page 272 13.3. Basic algebra in groups Page 276 13.4. The order of a group element Page 278 13.5. Isomorphism of groups Page 280 13.6. Cyclic groups Page 282 13.7. Subgroups Page 285 13.8. Cosets and Lagrange's theorem Page 288 13.9. Characterization of cyclic groups Page 293 13.10. Miscellaneous exercises Page 296 14. Groups of Permutations Page 300 14.1. Definitions and examples Page 300 14.2. Orbits and stabilizers Page 303 14.3. The size of an orbit Page 306 14.4. The number of orbits Page 309 14.5. Representation of groups by permutations Page 313 14.6. Applications to group theory Page 316 14.7. Miscellaneous exercises Page 318 15. Rings, fields, and polynomials Page 321 15.1. Rings Page 321 15.2. Invertible elements of a ring Page 323 15.3. Fields Page 324 15.4. Polynomials Page 327 15.5. The division algorithm for polynomials Page 330 15.6. The Euclidean algorithm for polynomials Page 333 15.7. Factorization of polynomials in theory Page 336 15.8. Factorization of polynomials in practice Page 338 15.9. Miscellaneous exercises Page 341 16. Finite fields and some applications Page 344 16.1. A field with nine elements Page 344 16.2. The order of a finite field Page 346 16.3. Construction of finite fields Page 348 16.4. The primitive element theorem Page 350 16.5. Finite fields and latin squares Page 354 16.6. Finite geometry and designs Page 357 16.7. Projective planes Page 361 16.8. Squares in finite fields Page 364 16.9. Existence of finite fields Page 368 16.10. Miscellaneous exercises Page 372 17. Error-correcting codes Page 375 17.1. Words, codes, and errors Page 375 17.2. Linear codes Page 379 17.3. Construction of linear codes Page 382 17.4. Correcting errors in linear codes Page 384 17.5. Cyclic codes Page 389 17.6. Classification and properties of cyclic codes Page 392 17.7. Miscellaneous exercises Page 397 18. Generating functions Page 399 18.1. Power series and their algebraic properties Page 399 18.2. Partial fractions Page 403 18.3. The binomial theorem for negative exponents Page 408 18.4. Generating functions Page 411 18.5. The homogeneous linear recursion Page 414 18.6. Nonhomogeneous linear recursions Page 418 18.7. Miscellaneous exercises Page 421 19. Partitions of a positive integer Page 423 19.1. Partitions and diagrams Page 423 19.2. Conjugate partitions Page 425 19.3. Partitions and generating functions Page 427 19.4. Generating functions for restricted partitions Page 431 19.5. A mysterious identity Page 433 19.6. The calculation of p(n) Page 437 19.7. Miscellaneous exercises Page 439 20. Symmetry and Counting Page 441 20.1. The cycle index of a group of permutations Page 441 20.2. Cyclic and dihedral symmetry Page 444 20.3. Symmetry in three dimensions Page 448 20.4. The number of inequivalent colourings Page 452 20.5. Sets of colourings and their generating functions Page 456 20.6. Pólya's theorem Page 458 20.7. Miscellaneous exercises Page 462