Solomon Golomb’s Course on Undergraduate Combinatorics

Description

This textbook offers an accessible introduction to combinatorics, infused with Solomon Golomb’s insights and illustrative examples. Core concepts in combinatorics are presented with an engaging narrative that suits undergraduate study at any level. Featuring early coverage of the Principle of Inclusion-Exclusion and a unified treatment of permutations later on, the structure emphasizes the cohesive development of ideas. Combined with the conversational style, this approach is especially well suited to independent study. Falling naturally into three parts, the book begins with a flexible Chapter Zero that can be used to cover essential background topics, or as a standalone problem-solving course. The following three chapters cover core topics in combinatorics, such as combinations, generating functions, and permutations. The final three chapters present additional topics, such as Fibonacci numbers, finite groups, and combinatorial structures. Numerous illuminating examples are included throughout, along with exercises of all levels. Three appendices include additional exercises, examples, and solutions to a selection of problems. Solomon Golomb’s Course on Undergraduate Combinatorics is ideal for introducing mathematics students to combinatorics at any stage in their program. There are no formal prerequisites, but readers will benefit from mathematical curiosity and a willingness to engage in the book’s many entertaining challenges. Foreword : Golombinatorics Solomon W. Golomb Acknowledgement Preface Introduction Table of Contents Chapter Zero: Basic Techniques Section 0.1. Set Theoretic Counting Section 0.2. Extremal Value Principle Section 0.3. Mean Value Principle Section 0.4. Pigeonhole Principle Section 0.5. Mathematical Induction Section 0.6 Critical Measures Practice Questions Chapter One: Combinations Section 1.1. Combinations without Repetitions Section 1.2. Combinations with Repetitions Section 1.3. Combinatorial Identities Section 1.4. Binomial Theorem Section 1.5. Multinomial Theorem Section 1.6. Probability Practice Questions Chapter Two: Generating Functions and Recurrence Relations Section 2.1. Generating Functions of Sequences Section 2.2. Direct Counting with Generating Functions Section 2.3. Recurrence Relations and Iterations Section 2.4. The Method of Characteristic Equations Section 2.5. The Method of Generating Functions Section 2.6. Dirichlet Generating Functions Practice Questions Chapter Three: Permutations Section 3.1. Permutations with or without Repetitions Section 3.2. Exponential Generating Functions Section 3.3. Derangements Section 3.4. Rook Polynomials Section 3.5. Cycles Section 3.6. Comma-free Dictionaries Practice Questions Chapter Four: Special Numbers Section 4.1. Fibonacci Numbers Section 4.2. Fibonacci Identities Section 4.3. Catalan Numbers Section 4.4. Stirling Numbers Section 4.5. Other Special Numbers Section 4.6. Ramsey Numbers Chapter Five: Counting under Symmetries Section 5.1. Finite Groups Section 5.2. Designs and Patterns Section 5.3. Cycle Indices Section 5.4. Inventory Functions Section 5.5. Necklaces Section 5.6. Combinatorial Symmetries Chapter Six: Combinatorial Structures Section 6.1. Finite Fields and Geometries Section 6.2. Latin Squares Section 6.3. Block Designs Section 6.4. Difference Sets Section 6.5. Triple Systems Section 6.6. Convenient Buildings Appendix A: Additional Exercises Appendix B: Additional Examples Appendix C: Solutions to Odd-numbered Exercises Bibliography Index