Introduction to Enumerative and Analytic Combinatorics / Miklos Bona.

Format:

Book

Author/Creator:

Bóna, Miklós, author.

Series:

Discrete mathematics and its applications.

Discrete Mathematics and Its Applications

Language:

English

Subjects (All):

Combinatorial analysis--Textbooks.

Combinatorial analysis.

Combinatorial enumeration problems--Textbooks.

Combinatorial enumeration problems.

Physical Description:

1 online resource (567 pages)

Edition:

Third edition.

Place of Publication:

Boca Raton, FL : CRC Press, [2025]

Summary:

These award-winning textbook targets the gap between introductory texts in discrete mathematics and advanced graduate texts in enumerative combinatorics. The author's goal is to make combinatorics more accessible to encourage student interest and to expand the number of students studying this rapidly expanding field.

Contents:

Cover

Half Title

Series Page

Title Page

Copyright Page

Dedication

Contents

Foreword to the first edition

Preface to the third edition

Acknowledgments

Frequently used notation

I. Methods

1. Basicmethods

1.1. When we add and when we subtract

1.1.1. When we add

1.1.2. When we subtract

Quick Check

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.3. When we divide

1.3.1. The division principle

1.3.2. Subsets

1.4. Applications of basic counting principles

1.4.1. Bijective proofs

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.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.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

II. Topics

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.5. Graphs and generating functions

5.5.1. Trees counted by Cayley's formula

5.5.2. Rooted trees

5.5.3. Connected graphs

5.5.4. Eulerian graphs

5.6. The Lagrange Inversion Formula

5.7. Notes

5.8. Chapter review

5.9. Exercises

5.10. Solutions to exercises

5.11. Supplementary exercises

6. Extremal combinatorics

6.1. Extremal graph theory

6.1.1. Bipartite graphs

6.1.2. Turán's theorem

6.1.3. Graphs excluding cycles

6.1.4. Graphs excluding complete bipartite graphs

6.2. Hypergraphs

6.2.1. Hypergraphs with pairwise intersecting edges

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

III. An Advanced Method

7. Analytic combinatorics

7.1. Exponential growth rates

7.1.1. Rational functions

7.1.2. Singularity analysis

7.2. Polynomial precision

7.2.1. Rational functions again

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

IV. Special Topics

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.

Quick Check

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.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

Appendix The method of mathematical induction

A.1. Weak induction

A.2. Strong induction

Bibliography

Index.

Notes:

Previous edition: 2016.

Includes bibliographical references and index.

Description based on publisher supplied metadata and other sources.

Description based on print version record.

ISBN:

9781003304272

1003304273

9781040312179

1040312179

9781040312155

1040312152

OCLC:

1518033512

Publisher Number:

CIPO000194266