# Combinatorics Topics

## 1. Sets, Set Operations, and some Important Functions

## 2. Permutations and Combinations

- The Addition and Subtraction Principles
- The Multiplication and Division Principles
- The Pigeonhole Principle
- The Generalized Pigeonhole Principle
- Increasing or Decreasing Subsequences of Finite Sequences
- Techniques for Solving Counting Problems
- Solving Counting Problems with Groupings
- Permutations of Elements in Sets
- Circular Permutations
- Combinations of Elements in Sets
- Counting Lattice Paths

## 3. Pascal's Triangle and The Binomial Theorem

- Pascal's Triangle
- The Fibonacci Sequence
- The Combinatorial Derivation of the Fibonacci Sequence
- A Closed Form of the Fibonacci Sequence
- Pascal's Formula
- Binomial Coefficients
- Binomial Coefficient Identities
- Sums of Binomial Coefficients
- Vandermonde's Identity
- The Formula for the Finite Sum of Consecutive Positive Integers
- The Generalized Binomial Coefficient Formula
- The Binomial Theorem
- Counting the Number of Subsets of a Finite Set

## 4. Combinations from Multisets, The Trinomial Theorem and The Multinomial Theorem

- Permutations of Elements in Multisets with Infinite Repetition Numbers
- Permutations of Elements in Mulitsets with Finite Repetition Numbers
- Combinations of Elements in Multisets with Infinite Repetition Numbers
- The Urn Problem with Indistinguishable Balls
- Nonnegative Integral Solutions to Simple Equations
- Trinomial Coefficients
- Trinomial Coefficient Identities
- The Trinomial Theorem
- Multinomial Coefficients
- Multinomial Coefficient Identities
- The Multinomial Theorem
- Newton's Generalization of The Binomial Theorem

## 5. Chains, Antichains, the Inclusion-Exclusion Principle, and Derangements

- Chains of Subsets of a Set
- Antichains of Subsets of a Set
- The Intersection of a Chain and Antichain
- The Lubell-Yamamoto-Meshalkin Inequality
- Sperner's Antichain Theorem
- The Inclusion-Exclusion Principle
- Combinations of Elements in Multisets with Finite Repetition Numbers
- Restricted Nonnegative Integral Solutions to Simple Equations
- Derangements
- Estimating the Number of Derangements of Elements from a Finite Set
- A Recurrence Relation for the Derangement Numbers

## 6. Algorithms for Generating Permutations and Combinations

- Generating All Permutations of a Set
- Mobile Generating of All Permutations of a Set
- Inversions of Permutations
- Even and Odd Permutations
- Evaluating Determinants with Inversions of Permutations
- The Inversion Sequence of a Permutation
- Generating Permutations with Inversion Sequences
- An Alternative Method for Generating Permutations with Inversion Sequences
- Generating All Combinations of a Set
- Generating k-Combinations of a Set

## 7. Relations on Sets and Partial/Total Orders

- Relations on Sets
- The Empty, Universal, and Identity Relations on a Set
- The Number of Distinct Relations on a Finite Set
- Partial Orders and Strict Partial Orders on Sets
- Linear Extensions of Partial Orders on Finite Sets
- Total Orders on Sets
- Total Orders from Permutations of a Set
- Equivalence Relations
- Equivalence Classes
- Different Representatives for Equivalence Classes
- Hasse Diagrams
- The Matrix Representation of a Relation
- Matrix Representations of Various Types of Relations

## 8. Generating Functions and Systems of Distinct Representatives

- Some Important Infinite Series
- Generating Functions
- More on Generating Functions
- Determining Generating Functions
- Using Generating Functions to Solve Counting Problems
- Positive Integer Partitions
- Exponential Generating Functions
- More on Exponential Generating Functions
- Systems of Distinct Representatives
- Hall's Marriage Theorem

# 9. Recurrence Relations

- Linear Recurrence Relations
- Characteristic Equations of Linear Recurrence Relations
- Vandermonde Matrices
- Distinct Roots - Linear Homogeneous Recurrence Relations with CC
- Solving LHRRs with CCs and Distinct Roots of the Characteristic Equation
- Repeated Roots - Linear Homogeneous Recurrence Relations with CC
- Solving LHRRs with CCs and Repeated Roots of the Characteristic Equation
- Solving Linear Homogeneous Recurrence Relations with Generating Functions

# 10. Special Counting Sequences and the Calculus of Finite Differences

- The Catalan Numbers
- A Recurrence Relation for the Catalan Numbers
- The Difference Operator
- More Properties of the Difference Operator
- Higher Order Differences
- Taylor's Theorem for the Calculus of Finite Differences
- Difference Sequences
- Difference Tables of Sequences
- The Antidifference Operator
- The Fundamental Theorem of the Calculus of Finite Differences

# 11. Designs

- Block Designs
- Balanced Incomplete Block Designs
- The Replication Number of a Balanced Incomplete Block Design
- The Block Number of a Balanced Incomplete Block Design
- Symmetric Balanced Incomplete Block Designs
- The Existence of Balanced Incomplete Block Designs
- The Sum Construction of Balanced Incomplete Block Designs
- The Complement Construction of Balanced Incomplete Block Designs
- The Incidence Matrix of a Balanced Incomplete Block Design
- Basic Properties of Incidence Matrices of Balanced Incomplete Block Designs
- Isomorphisms and Automorphisms of Balanced Incomplete Block Designs

- Difference Sets
- Partial Difference Sets
- The Trivial Difference Sets
- Paley Difference Sets
- The (v, k, λ) Parameters of Paley Difference Sets
- Twin Prime Difference Sets
- Difference Sets in Non-Abelian Groups
- The Development of a Difference Set
- Singer Difference Sets
- The Bruck-Ryser-Chowla Theorem

Submit an Error: Do you think that you see an error in any of the pages? Click the link and let us know so that we can fix it as soon as possible! All help is greatly appreciated with there being so many possible errors that can be overlooked. |

###### References

- 1. Discrete and Combinatorial Mathematics (5th Edition) by Ralph P. Grimaldi.

- 2. Combinatorial Designs: Constructions and Analysis by Douglas R. Stinson.