Combinatorics

Introduction

  1. Combinatorics
  2. Mathematicians
  3. Some Books

Basic Methods

  1. Mathematical Induction, Weak Induction, Strong Induction
  2. Pigeon-Hole Principle, Basic Form, Generalized Form
  3. Principle of Inclusion-Exclusion

Permutation and Choice

  1. Permutation: n Distinct Objects, ai Objects of Type i
  2. Lists: n Distinct Objects List of Length k, n Distinct Letters Words of Length k
  3. Subsets: k-Element Subsets of [n], k-Element Multisets with Elements from [n]
  4. Cyclic Permutation

Binomial Theorem

  1. Binomial Theorem, Pascal's Triangle
  2. Fibonacci Number, Golden Ratio
  3. Multinomial Theorem

Partitions

  1. Surjections: n Distinct Objects k Distinct Boxes, n Distinct Objects any Number of Distinct Boxes
  2. Compositions: n Identical Objects k Distinct Boxes, n Identical Objects any Number of Distinct Boxes
  3. Set Partitions: n Distinct Objects k Identical Boxes (Stirling Number of the Second Kind)
  4. Set Partitions: n Distinct Objects any Number of Identical Boxes (Bell Number)
  5. Integer Partitions, Ferrer Shape, Conjugate Partition, Self-Conjugate
  6. Integer Partitions: n Identical Objects k Identical Boxes, n Identical Objects any Number of Identical Boxes

Generating Functions

  1. Recurrence Relations, Generating Functions
  2. Products of Generating Functions, Compositions of Generating Functions
  3. Exponential Generating Functions
  4. Catalan Number

Applications

  1. Eulerian Walks
  2. Ramsey Theory
  3. Probability