Introduction to Enumerative Combinatorics - Rilegato

Bona, Miklos

Rilegato

ISBN 10: 007312561X ISBN 13: 9780073125619

Casa editrice: McGraw-Hill Education, 2005

Riassunto

Written by one of the leading authors and researchers in the field, this comprehensive modern text offers a strong focus on enumeration, a vitally important area in introductory combinatorics crucial for further study in the field. Miklós Bóna's text fills the gap between introductory textbooks in discrete mathematics and advanced graduate textbooks in enumerative combinatorics, and is one of the very first intermediate-level books to focus on enumerative combinatorics. The text can be used for an advanced undergraduate course by thoroughly covering the chapters in Part I on basic enumeration and by selecting a few special topics, or for an introductory graduate course by concentrating on the main areas of enumeration discussed in Part II. The special topics of Part III make the book suitable for a reading course.

This text is part of the Walter Rudin Student Series in Advanced Mathematics.

Su questo libro

Contenuti

Foreword

Preface

Acknowledgments

I How: Methods

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

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 Excursion: Composition of Two Generating Functions

3.4.1 Ordinary Generating Functions

3.4.2 Exponential Generating Functions

3.5 Excursion: A Different Type of Generating Function

3.6 Notes

3.7 Chapter Review

3.8 Exercises

3.9 Solutions to Exercises

3.10 Supplementary Exercises

II What: 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 Notes

4.6 Chapter Review

4.7 Exercises

4.8 Solutions to Exercises

4.9 Supplementary Exercises

5 Counting Graphs

5.1 Counting Trees and Forests

5.1.1 Counting Trees

5.2 The Notion of Graph Isomorphisms

5.3 Counting Trees on Labeled Vertices

5.3.1 Counting Forests

5.4 Graphs and Functions

5.4.1 Acyclic Functions

5.4.2 Parking Functions

5.5 When the Vertices Are Not Freely Labeled

5.5.1 Rooted Plane Trees

5.5.2 Binary Plane Trees

5.6 Excursion: Graphs on Colored Vertices

5.6.1 Chromatic Polynomials

5.6.2 Counting k-colored Graphs

5.7 Graphs and Generating Functions

5.7.1 Generating Functions of Trees

5.7.2 Counting Connected Graphs

5.7.3 Counting Eulerian Graphs

5.8 Notes

5.9 Chapter Review

5.10 Exercises

5.11 Solutions to Exercises

5.12 Supplementary Exercises

6 Extremal Combinatorics

6.1 Extremal Graph Theory

6.1.1 Bipartite Graphs

6.1.2 Tur´an’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 What Else: Special Topics

7 Symmetric Structures

7.1 Hypergraphs with Symmetries

7.2 Finite Projective Planes

7.2.1 Excursion: Finite Projective Planes of Prime Power Order

7.3 Error-Correcting Codes

7.3.1 Words Far Apart

7.3.2 Codes from Hypergraphs

7.3.3 Perfect Codes

7.4 Counting Symmetric Structures

7.5 Notes

7.6 Chapter Review

7.7 Exercises

7.8 Solutions to Exercises

7.9 Supplementary Exercises

8 Sequences in Combinatorics

8.1 Unimodality

8.2 Log-Concavity

8.2.1 Log-Concavity Implies Unimodality

8.2.2 The Product Property

8.2.3 Injective Proofs

8.3 The Real Zeros Property

8.4 Notes

8.5 Chapter Review

8.6 Exercises

8.7 Solutions to Exercises

8.8 Supplementary Exercises

9 Counting Magic Squares and Magic Cubes

9.1 An Interesting Distribution Problem

9.2 Magic Squares of Fixed Size

9.2.1 The Case of n = 3

9.2.2 The Function Hn(r) for Fixed n

9.3 Magic Squares of Fixed Line Sum

9.4 Why Magic Cubes Are Different

9.5 Notes

9.6 Chapter Review

9.7 Exercises

9.8 Supplementary Exercises

A The Method of Mathematical Induction

A.1 Weak Induction

A.2 Strong Induction

Bibliography

Index

Frequently Used Notation

Product Description

Book by Bona Miklos

Dettagli dell?edizione

• Editore: McGraw-Hill Education
• Data di pubblicazione: 2005
• ISBN 10: 007312561X
• ISBN 13: 9780073125619
• Rilegatura: Copertina rigida
• Lingua: Inglese
• Numero di pagine: 525