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