### Combinatorics

• MAT21300T, Summer

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