Discrete Mathematics (Oxford Science Publications)

This text is a carefully structured, coherent, and comprehensive course of discrete mathematics. The approach is traditional, deductive, and straightforward, with no unnecessary abstraction. It is self-contained including all the fundamental ideas in the field. It can be approached by anyone with basic competence in arithmetic and experience of simple algebraic manipulations. Students of computer science whose curriculum may not allow the study of many ancillary mathematics courses will find it particularly useful. Mathematics students seeking a first approach to courses such as graph theory, combinatorics, number theory, coding theory, combinatorial optimization, and abstract algebra will also enjoy a clear introduction to these more specialized fields. The main changes to this new edition are to present descriptions of numerous algorithms on a form close to that of a real programming language. The aim is to enable students to develop practical programs from the design of algorithms. Students of mathematics and computer science seeking an eloquent introduction to discrete mathematics will be pleased by this work. Numbers and Counting Integers Arithmetic Ordering the integers Recursive definitions The principle of induction Quotient and remainder Divisibility The greatest common divisor Factorization into primes Miscellaneous exercises Functions and counting Functions Surjections, injections, bijections Counting The pigeonhole principle Finite or infinite? Miscellaneous exercises Principles of counting The addition principle Counting sets of pairs Euler's function Functions, words, and selections Injections as ordered selections without repetition Permutations Miscellaneous exercises Subsets and designs Binomial numbers Unordered selections with repetition The binomial theorem The sieve principle Some arithmetical applications Designs t-designs Miscellaneous exercises Partition, classification, and distribution Partitions of a set Classification and equivalence relations Distributions and the multinomial numbers Partitions of a positive integer Classification of permutations Odd and even permutations Miscellaneous exercises Modular arithmetic Congruences Zm and its arithmetic Invertible elements of Z Cyclic constructions for designs Latin squares Miscellaneous exercises Graphs and Algorithms Algorithms and their efficiency What is an algorithm? The language of programs Algorithms and programs Proving that an algorithm is correct Efficiency of algorithms Growth rates: the O notation Comparison of algorithms Introduction to sorting algorithms Miscellaneous exercises Graphs Graphs and their representation Isomorphism of graphs Valency Paths and cycles Trees Colouring the vertices of a graph The greedy algorithm for vertex-colouring Miscellaneous exercises Trees, sorting, and searching Counting the leaves on a rooted tree Trees and sorting algorithms Spanning trees and the MST problem Depth-first search Breadth-first search The shortest-path problem Miscellaneous exercises Bipartite graphs and matching problems Relations and bipartite graphs Edge-colourings of graphs Application of edge-colouring latin squares Matchings Maximum matchings Transversals for families of finite sets Miscellaneous exercises Digraphs, networks, and flows Digraphs Networks and critical paths Flows and cuts The max-flow min-cut theorem The labelling algorithm for network flows Miscellaneous exercises Recursive techniques Generalities about recursion Linear recursion Recursive bisection Recursive optimization The framework of dynamic programming Examples of the dynamic programming method Miscellaneous exercises Algebraic Methods Groups The axioms for a group Examples of groups Basic algebra in groups The order of a group element Isomorphism of groups Cyclic groups Subgroups Cosets and Lagrange's theorem Characterization of cyclic groups Miscellaneous exercises Groups of Permutations Definitions and examples Orbits and stabilizers The size of an orbit The number of orbits Representation of groups by permutations Applications to group theory Miscellaneous exercises Rings, fields, and polynomials Rings Invertible elements of a ring Fields Polynomials The division algorithm for polynomials The Euclidean algorithm for polynomials Factorization of polynomials in theory Factorization of polynomials in practice Miscellaneous exercises Finite fields and some applications A field with nine elements The order of a finite field Construction of finite fields The primitive element theorem Finite fields and latin squares Finite geometry and designs Projective planes Squares in finite fields Existence of finite fields Miscellaneous exercises Error-correcting codes Words, codes, and errors Linear codes Construction of linear codes Correcting errors in linear codes Cyclic codes Classification and properties of cyclic codes Miscellaneous exercises Generating functions Power series and their algebraic properties Partial fractions The binomial theorem for negative exponents Generating functions The homogeneous linear recursion Nonhomogeneous linear recursions Miscellaneous exercises Partitions of a positive integer Partitions and diagrams Conjugate partitions Partitions and generating functions Generating functions for restricted partitions A mysterious identity The calculation of p(n) Miscellaneous exercises Symmetry and Counting The cycle index of a group of permutations Cyclic and dihedral symmetry Symmetry in three dimensions The number of inequivalent colourings Sets of colourings and their generating functions Pólya's theorem Miscellaneous exercises Discrete mathematics deals with calculations involving a finite number of steps rather than limiting processes. It is not a new field, but the recent rapid growths in the areas of computer science, statistics, and operations research have served to stimulate interest in and shape structure of this branch of mathematics. Using a traditional deductive approach, this book looks into the fundamental ideas in discrete mathematics, including graph theory, combinatorics, number theory, coding theory, combinatorial optimization and abstract algebra