Combinatorics: A Guided Tour
Combinatorics is mathematics of enumeration, existence, construction, and optimization questions concerning finite sets. This text focuses on the first three types of questions and covers basic counting and existence principles, distributions, generating functions, recurrence relations, Polya theory, combinatorial designs, error correcting codes, partially ordered sets, and selected applications to graph theory including the enumeration of trees, the chromatic polynomial, and introductory Ramsey theory. The only prerequisites are single-variable calculus and familiarity with sets and basic proof techniques. The text emphasizes the brands of thinking that are characteristic of combinatorics: bijective and combinatorial proofs, recursive analysis, and counting problem classification. It is flexible enough to be used for undergraduate courses in combinatorics, second courses in discrete mathematics, introductory graduate courses in applied mathematics programs, as well as for independent study or reading courses.
What makes this text a guided tour are the approximately 350 reading questions spread throughout its eight chapters. These questions provide checkpoints for learning and prepare the reader for the end-of-section exercises of which there are over 470. Most sections conclude with Travel Notes that add color to the material of the section via anecdotes, open problems, suggestions for further reading, and biographical information about mathematicians involved in the discoveries.
What people are saying - Write a review
We haven't found any reviews in the usual places.
2-lists algebra answer antichain assume BIBD bijective proof binary code binary numbers binomial theorem blocks chromatic polynomial codewords combinatorial proof compute construct contains corresponding counting questions cycle index define digit disjoint distinct recipients distributions edges element equals the number equation equivalence class equivalence relation exactly example Exercise Fibonacci Fibonacci numbers Figure Find four graph G Hamming Hasse diagram Hint identity incidence matrix inclusion-exclusion induction integer partition isomorphic labeled least linear extension mathematical minimum distance Mobius function Mobius inversion multiset n-set notation number of partitions one-to-one orbit ordered pairs parameters passwords perfect code permutations pigeonhole principle poset positive integers possible problem product principle properties prove real numbers recurrence relation red-blue coloring result satisfying Section sequence specify square Steiner triple systems Stirling numbers subset lattice sum principle symmetric term theory tiling total order tree upper bound varieties vertex vertices width(P write