Introduction to enumerative and analytic combinatorics / Miklós Bóna, University of Florida, Gainesville, Florida, USA
- Author
- Bóna, Miklós
- Uniform Title
- Introduction to enumerative combinatorics
- Published
- Boca Raton : CRC Press, Taylor & Francis Group, [2016]
- Edition
- Second edition.
- Physical Description
- xxii, 534 pages : illustrations (some color) ; 24 cm.
- Series
- Contents
- Machine generated contents note: 1.Basic methods -- 1.1.When we add and when we subtract -- 1.1.1.When we add -- 1.1.2.When we subtract -- 1.2.When we multiply -- 1.2.1.The product principle -- 1.2.2.Using several counting principles -- 1.2.3.When repetitions are not allowed -- 1.2.3.1.Permutations -- 1.2.3.2.Partial lists without repetition -- 1.3.When we divide -- 1.3.1.The division principle -- 1.3.2.Subsets -- 1.3.2.1.The number of k-element subsets of an n-element set -- 1.3.2.2.The binomial theorem for positive integer exponents -- 1.4.Applications of basic counting principles -- 1.4.1.Bijective proofs -- 1.4.1.1.Catalan numbers -- 1.4.2.Properties of binomial coefficients -- 1.4.3.Permutations with repetition -- 1.5.The pigeonhole principle -- 1.6.Notes -- 1.7.Chapter review -- 1.8.Exercises -- 1.9.Solutions to exercises -- 1.10.Supplementary exercises -- 2.Applications of basic methods -- 2.1.Multisets and compositions -- 2.1.1.Weak compositions -- 2.1.2.Compositions -- 2.2.Set partitions -- 2.2.1.Stirling numbers of the second kind -- 2.2.2.Recurrence relations for Stirling numbers of the second kind -- 2.2.3.When the number of blocks is not fixed -- 2.3.Partitions of integers -- 2.3.1.Nonincreasing finite sequences of positive integers -- 2.3.2.Ferrers shapes and their applications -- 2.3.3.Excursion: Euler's pentagonal number theorem -- 2.4.The inclusion[—]exclusion principle -- 2.4.1.Two intersecting sets -- 2.4.2.Three intersecting sets -- 2.4.3.Any number of intersecting sets -- 2.4.3.1.An explicit formula for the numbers S(n, k) -- 2.4.3.2.An application involving linear orders -- 2.4.3.3.Euler's φ function -- 2.4.3.4.Derangements -- 2.4.3.5.Excursion: Another proof of the inclusion-exclusion principle -- 2.5.The twelvefold way -- 2.6.Notes -- 2.7.Chapter review -- 2.8.Exercises -- 2.9.Solutions to exercises -- 2.10.Supplementary exercises -- 3.Generating functions -- 3.1.Power series -- 3.1.1.Generalized binomial coefficients -- 3.1.2.Formal power series -- 3.2.Warming up: Solving recurrence relations -- 3.2.1.Ordinary generating functions -- 3.2.2.Exponential generating functions -- 3.3.Products of generating functions -- 3.3.1.Ordinary generating functions -- 3.3.2.Exponential generating functions -- 3.4.Compositions of generating functions -- 3.4.1.Ordinary generating functions -- 3.4.2.Exponential generating functions -- 3.4.2.1.The exponential formula -- 3.4.2.2.The compositional formula -- 3.5.A different type of generating functions -- 3.6.Notes -- 3.7.Chapter review -- 3.8.Exercises -- 3.9.Solutions to exercises -- 3.10.Supplementary exercises -- 4.Counting permutations -- 4.1.Eulerian numbers -- 4.2.The cycle structure of permutations -- 4.2.1.Stirling numbers of the first kind -- 4.2.2.Permutations of a given type -- 4.3.Cycle structure and exponential generating functions -- 4.4.Inversions -- 4.4.1.Counting permutations with respect to inversions -- 4.5.Advanced applications of generating functions to permutation enumeration -- 4.5.1.The combinatorial meaning of the derivative -- 4.5.2.Multivariate generating functions -- 4.6.Notes -- 4.7.Chapter review -- 4.8.Exercises -- 4.9.Solutions to exercises -- 4.10.Supplementary exercises -- 5.Counting graphs -- 5.1.Trees and forests -- 5.1.1.Trees -- 5.1.2.The notion of graph isomorphisms -- 5.1.3.Counting trees on labeled vertices -- 5.1.4.Forests -- 5.2.Graphs and functions -- 5.2.1.Acyclic functions -- 5.2.2.Parking functions -- 5.3.When the vertices are not freely labeled -- 5.3.1.Rooted plane trees -- 5.3.2.Decreasing binary trees -- 5.4.Graphs on colored vertices -- 5.4.1.Chromatic polynomials -- 5.4.2.Colored graphs -- 5.4.2.1.Counting all k-colored graphs -- 5.4.2.2.Counting colored trees -- 5.5.Graphs and generating functions -- 5.5.1.Trees counted by Cayley's formula -- 5.5.2.Rooted trees -- 5.5.2.1.Ordinary generating functions -- 5.5.2.2.Exponential generating functions -- 5.5.2.3.An application of multivariate generating functions -- 5.5.3.Connected graphs -- 5.5.4.Eulerian graphs -- 5.6.Notes -- 5.7.Chapter review -- 5.8.Exercises -- 5.9.Solutions to exercises -- 5.10.Supplementary exercises -- 6.Extremal combinatorics -- 6.1.Extremal graph theory -- 6.1.1.Bipartite graphs -- 6.1.2.Turan's theorem -- 6.1.3.Graphs excluding cycles -- 6.1.3.1.Convex functions and Jensen's inequality -- 6.1.3.2.Notation in approximate counting -- 6.1.3.3.Refining the results on fC4(n) -- 6.1.3.4.Avoiding longer cycles -- 6.1.4.Graphs excluding complete bipartite graphs -- 6.2.Hypergraphs -- 6.2.1.Hypergraphs with pairwise intersecting edges -- 6.2.1.1.Sunflowers -- 6.2.2.Hypergraphs with pairwise incomparable edges -- 6.3.Something is more than nothing: Existence proofs -- 6.3.1.Property B -- 6.3.2.Excluding monochromatic arithmetic progressions -- 6.3.3.Codes over finite alphabets -- 6.4.Notes -- 6.5.Chapter review -- 6.6.Exercises -- 6.7.Solutions to exercises -- 6.8.Supplementary exercises -- 7.Analytic combinatorics -- 7.1.Exponential growth rates -- 7.1.1.Rational functions -- 7.1.1.1.Motivation -- 7.1.1.2.Theoretical background -- 7.1.2.Singularity analysis -- 7.1.2.1.Motivation -- 7.1.2.2.Analytic functions -- 7.1.2.3.The complex versions of some well-known functions -- 7.1.2.4.Singularities -- 7.1.2.5.The main theorem of exponential asymptotics -- 7.2.Polynomial precision -- 7.2.1.Rational functions again -- 7.2.1.1.Motivation -- 7.2.1.2.Multiple singularities in rational functions -- 7.3.More precise asymptotics -- 7.3.1.Entire functions divided by (1-x) -- 7.3.2.Rational functions one more time -- 7.4.Notes -- 7.5.Chapter review -- 7.6.Exercises -- 7.7.Solutions to exercises -- 7.8.Supplementary exercises -- 8.Symmetric structures -- 8.1.Designs -- 8.2.Finite projective planes -- 8.2.1.Finite projective planes of prime power order -- 8.3.Error-correcting codes -- 8.3.1.Words far apart -- 8.3.2.Codes from designs -- 8.3.3.Perfect codes -- 8.4.Counting symmetric structures -- 8.5.Notes -- 8.6.Chapter review -- 8.7.Exercises -- 8.8.Solutions to exercises -- 8.9.Supplementary exercises -- 9.Sequences in combinatorics -- 9.1.Unimodality -- 9.2.Log-concavity -- 9.2.1.Log-concavity implies unimodality -- 9.2.2.The product property -- 9.2.3.Injective proofs -- 9.2.3.1.Lattice paths again -- 9.3.The real zeros property -- 9.4.Notes -- 9.5.Chapter review -- 9.6.Exercises -- 9.7.Solutions to exercises -- 9.8.Supplementary exercises -- 10.Counting magic squares and magic cubes -- 10.1.A distribution problem -- 10.2.Magic squares of fixed size -- 10.2.1.The case of n = 3 -- 10.2.2.The function Hn (r) for fixed n -- 10.3.Magic squares of fixed line sum -- 10.4.Why magic cubes are different -- 10.5.Notes -- 10.6.Chapter review -- 10.7.Exercises -- 10.8.Solutions to exercises -- 10.9.Supplementary exercises -- A.1.Weak induction -- A.2.Strong induction.
- Subject(s)
- Genre(s)
- ISBN
- 9781482249095 (hbk. ; acid-free paper)
148224909X (hbk. ; acid-free paper) - Note
- "A Chapman & Hall book."
- Bibliography Note
- Includes bibliographical references (pages 525-530) and index.
View MARC record | catkey: 16619357