| CHAPTER 2 Permutations and Combinations |
- 2.1 Four Basic Counting Principles
- Addition, Subtraction, Multiplication and Division Principles of Counting.
- 2.2 Permutations of Sets
- Permutations, r-permutations and circular r-permtuations; the number of ways of seating people in a row of chairs or at a circular table.
- 2.3 Combinations of Sets
- r-combinations; the number of ways of selecting r objects from a collection of n distinct objects.
- 2.4 Permutations of Multisets
- the number of permutations of a multiset, the number of r-permutations of a multiset where each distinct object is repeated a minimum of r times.
- 2.5 Combinations of Multisets
- the number of r-combinations of a multiset with k distinct objects, the number of nonnegative integer solutions to x1 + x2 + ... + xk= r, the number of ways to distribute r identical objects to k people.
|
| CHAPTER 5 The Binomial Coefficients |
- 5.1 Pascal's Triangle
- Pascal's Formula for the binomial coefficients, Pascal's Triangle.
- 5.2 The Binomial Theorem
- Expanding (x+y)n, identities involving binomial coefficients.
- 5.4 The Multinomial Theorem
- Expanding (x1 + x2 + x3 + ... + xk )n.
|
| CHAPTER 6 The Inclusion-Exclusion Principle and Applications |
- 6.1 The Inclusion-Exclusion Principle
- How to count the cardinality of the union of sets that overlap without restriction.
- 6.2 Combinations with Repetition
- A general formula for the number of combinations of a multiset.
- 6.3 Derangements
- A formula for the number of permutations with no fixed points.
|
| CHAPTER 7 Recurrence Relations and Generating Functions |
- 7.1 Some Number Sequences
- Arithmetic and Geometric sequences, Fibonacci sequence, explicit function definition of a sequence, recursive definition of a sequence.
- 7.2 Generating Functions
- How to use power series to find solutions to combinatorial problems.
- 7.4 Solving Linear Homogeneous Recurrence Relations
- How to compute solutions of linear homogeneous recurrence relations with constant coefficients; Characteristic equation and characteristic roots. How to use generating functions to find solutions to recurrence relations.
- 7.5 Nonhomogeneous Recurrence Relations
- How to compute solutions of linear nonhomogeneous recurrence relations with constant coefficients.
|
| CHAPTER 8 Special Counting Sequences |
- 8.1 Catalan Numbers
- A variety of combinatorial interpretations of the Catalan sequence; Recursive formula for the nth Catalan number
- 8.2 Stirling Numbers
- s(n,k), the number of ways to seat n people at k identical circular tables with at least one person at each table (a.k.a Stirling numbers of the first kind); S(n,k), the number of partitions of an n-element set into exactly k nonempty subsets (a.k.a Stirling numbers of the second kind); Bell Numbers
- 8.3 Partition Numbers
- Counting the number of ways to write n as a unordered sum of integers.
|
| Additional Topics, time permitting |
- The Transfer-matrix Method
- Using matrices to count pattern avoiding permutations and sequences.
- Bijective Proofs of Partition Identities
- Euler's Identity, Pentagonal Number Theorem, Jacobi Triple Product
- More Generating Functions for Partitions
- q-binomial coefficients and q-analogs of binomial identities
- Rogers-Ramanujan Identities
- A brief introduction to the world's most famous partition identity.
|