Welcome to the **Combinatorics** page. Here you can browse an array of combinatorics topics from permutations and combinations to the binomial and multinomial theorems to chains and antichains and much more! This page lists few graph theory topics, but the Graph Theory section can be read alongside for a richer experience with combinatorics. Regardless, this section contains:

- An overview of sets (particularly finite sets) and set operations, a brief introduction of multisets, the floor and ceiling functions on a real number, factorial function, and Stirling's approximation formula for the factorial function.
- An introduction to the addition/subtraction principles, multiplication/division principles, the pigeonhole principles, and simple permutations and combinations of elements from a finite set.
- A look at Pascal's triangle and it's relation to the binomial coefficients and their identities, Vandermonde's identity, deriving the sum of consecutive positive integers formula, and the binomial theorem.
- An extension of the binomial coefficients/theorem to the multinomial coefficients, the multinomial theorem, and permutations/combinations of elements from multisets.
- A look at chains, antichains, and determining the size of the largest chains and antichains (with Sperner's Theorem) and using the Lubell-Yamamoto-Meshalkin inequality to prove this. We also look at the inclusion-exclusion principle and derangements.
- An introduction to basic algorithms for generating all permutations and combinations of elements in a finite set or all $k$-permutations/combinations and permutation inversions.
- An introduction to relations on a single set $X$, classification of relations, partial and total orders, equivalence relations, and the Hasse diagrams and matrix representations of these relations.
- A look at generating functions and exponential generating functions to solve counting problems; systems of distinct representatives and Hall's Marriage Theorem showing the existence of SDRs.
- An overview of linear recurrence relations and techniques for solving linear homogeneous recurrence relations with constant coefficients.
- Insight into the Catalan numbers and the calculus of finite differences.

# 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
- 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