Introduction to Combinatorics

1st Edition - April 28, 1972
Authors: Gerald Berman, K. D. Fryer
Language: English
eBook ISBN:
9 7 8 - 1 - 4 8 3 2 - 7 3 8 2 - 2

Introduction to Combinatorics focuses on the applications, processes, methodologies, and approaches involved in combinatorics or discrete mathematics. The book first offers… Read more

Purchase options

LIMITED OFFER

Save 50% on book bundles

Immediately download your ebook while waiting for your print delivery. No promo code is needed.

Institutional subscription on ScienceDirect

Request a sales quote

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.

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