Enumerative Combinatorics
Purchasing Options
Features
Summary
Enumerative Combinatorics presents elaborate and systematic coverage of the theory of enumeration. The first seven chapters provide the necessary background, including basic counting principles and techniques, elementary enumerative topics, and an extended presentation of generating functions and recurrence relations. The remaining seven chapters focus on more advanced topics, including, Stirling numbers, partitions of integers, partition polynomials, Eulerian numbers and Polya's counting theorem.
Extensively classroom tested, this text was designed for introductory- and intermediate-level courses in enumerative combinatorics, but the far-reaching applications of the subject also make the book useful to those in operational research, the physical and social science, and anyone who uses combinatorial methods. Remarks, discussions, tables, and numerous examples support the text, and a wealth of exercises-with hints and answers provided in an appendix--further illustrate the subject's concepts, theorems, and applications.
Table of Contents
BASIC COUNTING PRINCIPLES
Introduction
Sets, Relations and Maps
The Principles of Addition and Multiplication
Discrete Probability
Sums and Products
PERMUTATIONS AND COMBINATIONS
Introduction
Permutations
Combinations
Divisions and Partitions of a Finite set
Integer Solutions of a Linear Equation
Lattice Paths
Probabilistic Applications
FACTORIALS, BINOMIAL AND MULTINOMIAL COEFFICIENTS
Introduction
Factorials
Binomial Coefficients
Multinomial Coefficients
THE PRINCIPLE OF INCLUSION AND EXCLUSION
Introduction
Number of Elements in a Union of Sets
Number of Elements in a Given Number of Sets
Bonferroni Inequalities
Number of Elements of a Given Rank
PERMUTATIONS WITH FIXED POINTS AND SUCCESSIONS
Introduction
Permutations with Fixed Points
Ranks of Permutations
Permutations with Successions
Circular Permutations with Successions
GENERATING FUNCTIONS
Introduction
Univariate Generating Functions
Combinations and Permutations
Moment Generating Functions
Multivariate Generating Functions
RECURRENCE RELATIONS
Introduction
Basic Notions
Recurrence Relations of the First Order
The Method of Characteristic Roots
The Method of Generating Functions
STIRLING NUMBERS
Introduction
Stirling Numbers of the First and Second Kind
Explicit Expressions and Recurrence Relations
Generalized Factorial Coefficients
Non-Central Stirling and Related Numbers
DISTRIBUTIONS AND OCCUPANCY
Introduction
Classical Occupancy and Modifications
Ordered Distributions and Occupancy
Balls of General Specification and Distinguishable Urns
Generating Functions
PARTITIONS OF INTEGERS
Introduction
Recurrence Relations and Generating Functions
A Universal Generating Function
Interrelations among Partition Numbers
Combinatorial Identities
PARTITION POLYNOMIALS
Introduction
Exponential Bell Partition Polynomials
General Partition Polynomials
Logarithmic Partition Polynomials
Potential Partition Polynomials
Inversion of Power Series
Touchard Polynomials
CYCLES OF PERMUTATIONS
Introduction
Permutations with a Given Number of Cycles
Even and Odd Permutations
Permutations with Partially Ordered Cycles
EQUIVALENCE CLASSES
Introduction
Cycle Indicator of a Permutation Group
Orbits of Elements of a Finite Set
Models of Colorings of a Finite Set
RUNS OF PERMUTATIONS AND EULERIAN NUMBERS
Introduction
Eulerian Numbers
Carlitz Numbers
Permutations with a Given Number of Runs
Permutations with Repetition and a Given Number of Runs
HINTS AND ANSWERS TO EXERCISES
BIBLIOGRAPHY
INDEX
Each chapter also contains Bibliographic Notes and Exercises
Editorial Reviews
"The broad field of applications of combinatorial methods makes this book useful to anyone interested in operations research, physical, or social sciences…. Provides a comprehensive coverage of enumerative combinatorics, and gives many illuminating examples and interesting historical notes… students of combinatorics will find the book very useful as there are many theorems, all with complete proofs, and many exercises with hints and answers."
-Journal of the Operational Research Society, Vol 55, no. 2, 2004
"Overall, this is a well-written book. In particular, I like the vast amount of exercises ranging in difficulty from very easy to quite hard, as well as the remarks following most of the definitions and theorems where a particular concept or result presented is discussed and extensions or generalizations of it are pointed out. Also, I like the brief bibliographic notes, mainly of historical interest, at the end of each chapter."
– Sergey Kitaev, Mathematics Institute, Reykjavík University, in SIGACT News, October 2008
