Introduction to Combinatorics focuses on the applications, processes, methodologies, and approaches involved in combinatorics or discrete mathematics. The book first offers information on introductory examples, permutations and combinations, and the inclusion-exclusion principle. Discussions focus on some applications of the inclusion-exclusion principle, derangements, calculus of sets, permutations, combinations, Stirling's formula, binomial theorem, regions of a plane, chromatic polynomials, and a random walk. The text then examines linear equations with unit coefficients, recurrence relations, and generating functions. Topics include derivatives and differential equations, solution of difference equations by means of generating functions, recurrence relations, summation method, difference methods, combinations with repetitions, solutions bounded below, and solutions bounded above and below. The publication takes a look at generating functions and difference equations, ramifications of the binomial theorem, finite structures, coloring problems, maps on a sphere, and geometry of the plane. The manuscript is a valuable reference for researchers interested in combinatorics.
Inhalt
Preface
Acknowledgments
1. Introductory Examples
1.1 A Simple Enumeration Problem
1.2 Regions of a Plane
1.3 Counting Labeled Trees
1.4 Chromatic Polynomials
1.5 Counting Hairs
1.6 Evaluating Polynomials
1.7 A Random Walk
Part I. Enumeration
2. Permutations and Combinations
2.1 Permutations
2.2 r-Arrangements
2.3 Combinations
2.4 The Binomial Theorem
2.5 The Binomial Coefficients
2.6 The Multinomial Theorem
2.7 Stirling's Formula
3. The Inclusion-Exclusion Principle
3.1 A Calculus of Sets
3.2 The Inclusion-Exclusion Principle
3.3 Some Applications of the Inclusion-Exclusion Principle
3.4 Derangements
4. Linear Equations with Unit Coefficients
4.1 Solutions Bounded Below
4.2 Solutions Bounded Above and Below
4.3 Combinations with Repetitions
5. Recurrence Relations
5.1 Recurrence Relations
5.2 Solution by Iteration
5.3 Difference Methods
5.4 A Fibonacci Sequence
5.5 A Summation Method
5.6 Chromatic Polynomials
6. Generating Functions
6.1 Some Simple Examples
6.2 The Solution of Difference Equations by Means of Generating Functions
6.3 Some Combinatorial Identities
6.4 Additional Examples
6.5 Derivatives and Differential Equations
Part II. Existence
7. Some Methods of Proof
7.1 Existence by Construction
7.2 The Method of Exhaustion
7.3 The Dirichlet Drawer Principle
7.4 The Method of Contradiction
8. Geometry of the Plane
8.1 Convex Sets
8.2 Tiling a Rectangle
8.3 Tessellations of the Plane
8.4 Some Equivalence Classes
9. Maps on a Sphere
9.1 Euler's Formula
9.2 Regular Maps in the Plane
9.3 Platonic Solids
10. Coloring Problems
10.1 The Four Color Problem
10.2 Coloring Graphs
10.3 More about Chromatic Polynomials
10.4 Chromatic Triangles
10.5 Sperner's Lemma
11. Finite Structures
11.1 Finite Fields
11.2 The Fano Plane
11.3 Coordinate Geometry
11.4 Projective Configurations
Part III. Applications
12. Probability
12.1 Combinatorial Probability
12.2 Ultimate Sets
13. Ramifications of the Binomial Theorem
13.1 Arithmetic Power Series
13.2 The Binomial Distribution
13.3 Distribution of Objects into Boxes
13.4 Stirling Numbers
13.5 Gaussian Binomial Coefficients
14. More Generating Functions and Difference Equations
14.1 The Partition of Integers
14.2 Triangulation of Convex Polygons
14.3 Random Walks
14.4 A Class of Difference Equations
15. Fibonacci Sequences
15.1 Representations of Fibonacci Sequences
15.2 Diagonal Sums of the Pascal Triangle
15.3 Sequences of Plus and Minus Signs
15.4 Counting Hares
15.5 Maximum or Minimum of a Unimodal Function
16. Arrangements
16.1 Systems of Distinct Representatives
16.2 Latin Squares
16.3 The Kirkman Schoolgirl Problem
16.4 Balanced Incomplete Block Designs
16.5 Difference Sets
16.6 Magic Squares
16.7 Room Squares
Answers to Selected Exercises
Index