combinatoricsheader.png
Screen%20Shot%202015-08-17%20at%2011.11.18%20AM.png

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

3. Pascal's Triangle and The Binomial Theorem

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

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

6. Algorithms for Generating Permutations and Combinations

7. Relations on Sets and Partial/Total Orders

8. Generating Functions and Systems of Distinct Representatives

9. Recurrence Relations

10. Special Counting Sequences and the Calculus of Finite Differences

11. Designs

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License