Combinatorial Reasoning : An Introduction to the Art of Counting.

Intro -- Combinatorial Reasoning -- Contents -- Preface -- Features of This Text -- Flexibility for Courses -- Part I The Basics of Enumerative Combinatorics -- 1 Initial Encounters with Combinatorial Reasoning -- 1.1 Introduction -- 1.2 The Pigeonhole Principle -- 1.2.1 Applications to Ranges and Domains of Functions -- 1.2.2 An Application to the Chinese Remainder Theorem -- 1.2.3 Generalizations of the Pigeon Principle -- Problems -- 1.3 Tiling Chessboards with Dominoes -- Problems -- 1.4 Figurate Numbers -- 1.4.1 More General Polygonal Numbers -- Problems -- 1.5 Counting Tilings of Rectangles -- 1.5.1 Tiling a Rectangle with Squares of Two Colors -- 1.5.2 Tiling a 1 × n Rectangle with Exactly r Gray Squares -- 1.5.3 Tiling a 1 × n Rectangle with Squares and Dominoes -- Problems -- 1.6 Addition and Multiplication Principles -- 1.6.1 Addition Principles -- 1.6.2 Multiplication Principle -- 1.6.3 Combining the Addition and Multiplication Principles -- Problems -- 1.7 Summary and Additional Problems -- Problems -- References -- 2 Selections, Arrangements, and Distributions -- 2.1 Introduction -- 2.2 Permutations and Combinations -- 2.2.1 Permutations -- 2.2.2 Combinations -- 2.2.3 Applications to Probability -- Problems -- 2.3 Combinatorial Models -- 2.3.1 Tiling Models -- 2.3.2 Block Walking Models -- 2.3.3 The Committee Selection Model -- 2.3.4 The Flagpole Model -- Problems -- 2.4 Permutations and Combinations with Repetitions -- 2.4.1 Multisets -- 2.4.2 Permutations with Repetition -- 2.4.3 Combinations with Repetition -- Problems -- 2.5 Distributions to Distinct Recipients -- 2.5.1 Distributions of Distinct Objects to Distinct Recipients -- 2.5.2 Distributions of Identical Objects to Distinct Recipients -- 2.5.3 Mixed Distribution Problems -- 2.5.4 Equations for Distributions -- 2.5.5 Counting Functions -- Problems.

2.6 Circular Permutations and Derangements -- 2.6.1 Circular Permutations -- 2.6.2 Derrangements -- Problems -- 2.7 Summary and Additional Problems -- Problems -- Reference -- 3 Binomial Series and Generating Functions -- 3.1 Introduction -- 3.2 The Binomial and Multinomial Theorems -- 3.2.1 The Binomial Theorem -- 3.2.2 The Multinomial Theorem -- Problem -- 3.3 Newtons Binomial Series -- 3.3.1 Generating Function for the Multichoose Coefficients -- 3.3.2 Generalized Binomial Coefficients and Newtons Binomial Series -- Problem -- 3.4 Ordinary Generating Functions -- 3.4.1 Deriving Ordinary Generating Functions -- 3.4.2 Products of Ordinary Generating Functions -- 3.4.3 Counting with Ordinary Generating Functions -- Problem -- 3.5 Exponential Generating Functions -- 3.5.1 Deriving Exponential Generating Functions -- 3.5.2 Products of Exponential Generating Functions -- 3.5.3 Counting with Exponential Generating Functions -- 3.5.4 Comparison between Exponential and Ordinary Generating Functions -- Problems -- 3.6 Summary and Additional Problems -- Problems -- References -- 4 Alternating Sums, Inclusion-Exclusion Principle, Rook Polynomials, and Fibonacci Nim -- 4.1 Introduction -- 4.2 Evaluating Alternating Sums with the DIE Method -- 4.2.1 Using the DIE Method -- 4.2.2 Applications of the DIE Method to Tiling Problems -- Problems -- 4.3 The Principle of Inclusion-Exclusion (PIE) -- 4.3.1 PIE for Three Subsets -- 4.3.2 PIE in General -- 4.3.3 An Application of PIE to Number Theory -- Problems -- 4.4 Rook Polynomials -- 4.4.1 PIE Applications -- 4.4.2 Using Ordinary Generating Functions -- 4.4.3 Another Computational Strategy -- Problems -- 4.5 (OPTIONAL) Zeckendorf Representations and Fibonacci NIM -- 4.5.1 Zeckendorfs Theorem -- 4.5.2 Fibonacci Nim -- Problems -- 4.6 Summary and Additional Problems -- Problems -- References -- 5 Recurrence Relations.

5.1 Introduction -- 5.2 The Fibonacci Recurrence Relation -- 5.2.1 The E Operator and Its Application to First-Order Recurrences -- 5.2.2 The E Operator and the Fibonacci Recurrence -- 5.2.3 The Binet Formulas -- Problems -- 5.3 Second-Order Recurrence Relations -- 5.3.1 Solving Homogeneous Second-Order Linear Recurrence Relations -- 5.3.2 A Coupled First-Order System of Linear Recurrence Relations -- 5.3.3 Repeated Eigenvalues -- 5.3.4 Complex Eigenvalues -- 5.3.5 A Connection with Linear Algebra -- Problems -- 5.4 Higher-Order Linear Homogeneous Recurrence Relations -- 5.4.1 Nonrepeated Eigenvalues -- 5.4.2 Repeated Eigenvalues -- Problems -- 5.5 Nonhomogeneous Recurrence Relations -- 5.5.1 Solving for Initial Conditions -- 5.5.2 Finding a Particular Solution -- Problems -- 5.6 Recurrence Relations and Generating Functions -- 5.6.1 Ordinary Generating Functions for Linear Recurrence Relations -- 5.6.2 Generating Functions for More General Recurrence Relations -- Problems -- 5.7 Summary and Additional Problems -- Problems -- References -- 6 Special Numbers -- 6.1 Introducation -- 6.2 Stirling Numbers -- 6.2.1 Polynomials and the Difference Operator -- 6.2.2 Stirling Numbers of the Second Kind -- 6.2.3 Bell Numbers -- 6.2.4 Stirling Numbers of the First Kind -- 6.2.5 Identities for Stirling Numbers -- Problems -- 6.3 Harmonic Numbers -- 6.3.1 Growth Rate of the Harmonic Numbers -- 6.3.2 Connection to Probability -- 6.3.3 Connection to Stirling Numbers -- 6.3.4 The Domino Stacking Problem -- 6.3.5 Summation by Parts -- Problems -- 6.4 Bernoulli Numbers -- 6.4.1 Exponential Generating Functions -- 6.4.2 Sum of Integer kth Powers -- 6.4.3 Bernoulli Numbers and Trigonometric Taylor Series -- Problems -- 6.5 Eulerian Numbers -- 6.5.1 Triangle Identity for Eulerian Numbers -- 6.5.2 The Number of Ascents in a Permutation of [n].

6.5.3 Sums of Integer Powers and Worpitzkys Identity -- Problems -- 6.6 Partition Numbers -- 6.6.1 Unrestricted Partitions -- 6.6.2 Restricted Partition Numbers -- 6.6.3 Eulers Pentagonal Number Theorem -- Problems -- 6.7 Catalan Numbers -- 6.7.1 Triangulations of a Convex Polygonal Region by Its Diagonals -- 6.7.2 Other Occurrences of Catalan Numbers -- Problems -- 6.8 Summary and Additional Problems -- 6.8.1 Counting Functions and Distributions -- Problems -- References -- Part II Two Additional Topics in Enumeration -- 7 Linear Spaces and Recurrence Sequences -- 7.1 Introduction -- 7.2 Vector Spaces of Sequences -- 7.2.1 Three Vector Spaces Associated with a Recurrence Relation -- 7.2.2 The Order of a Recurrence Relation -- 7.2.3 The Ring of Recurrence Sequences -- 7.2.4 Upper Bounds for the Order of a Recurrence Sequence -- 7.2.5 Bases and Representations -- Problems -- 7.3 Nonhomogeneous Recurrences and Systems of Recurrences -- 7.3.1 Nonhomogeneous Recurrences -- 7.3.2 Systems of Linear Recursion Relations -- Problems -- 7.4 Identities for Recurrence Sequences -- 7.4.1 The Operator Method -- 7.4.2 Free and Bound Variables -- 7.4.3 Elementary Applications of the Operator Method -- 7.4.4 Expressing Sums in Closed Form -- 7.4.5 Sums with Binomial Coefficients -- Problems -- 7.5 Summary and Additional Problems -- Problems -- 8 Counting with Symmetries -- 8.1 Introduction -- 8.2 Algebraic Discoveries -- 8.2.1 Groups of Actions -- 8.2.2 Cycle Decomposition -- 8.2.3 A Preview of the Cycle Index and Pattern Inventory -- 8.2.4 More Groups of Symmetries -- 8.2.5 Fixed Points and Stabilizer Subgroups -- 8.2.6 Orbits -- 8.2.7 Comparing the Number of Fixed Points, Stabilizers, and Orbits -- 8.2.8 Colorings and Labelings -- Problems -- 8.3 Burnsides Lemma -- 8.3.1 Equivalence Classes of Colorings -- 8.3.2 The Proof of Burnsides Lemma -- Problems.

8.4 The Cycle Index and Pólyas Method of Enumeration -- 8.4.1 Monomials and the Cycle Index -- 8.4.2 Total Number of Colorings Determined from the Cycle Index -- 8.4.3 Pólyas Inventory Function -- Problems -- 8.5 Summary and Additional Problems -- Problems -- References -- Part III Notations Index, Appendices, and Solutions to Selected Odd Problems -- Index of Notations -- Appendix A: Mathematical Induction -- A.1 Principle of Mathematical Induction -- A.2 Principle of Strong Induction -- A.3 Well Ordering Principle -- Appendix B: Searching the Online Encyclopedia of Integer Sequences (OEIS) -- B.1 Searching a Sequence -- B.2 Searching an Array -- B.3 Other Searches -- B.4 Beginnings of OEIS -- Appendix C: Generalized Vandermonde Determinants -- Hints, Short Answers, and Complete Solutions to Selected Odd Problems -- Problem Answers and Solutions -- Index.

Description based on publisher supplied metadata and other sources.

Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2024. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries.