| CHAPTER 1 What is Combinatorics? |
- 1.1 Perfect Coverings of Chessboards
- How many perfect coverings are there of chessboards of varying dimensions? See Perfect Coverings Worksheet.
|
| CHAPTER 3 Permutations and Combinations |
- 3.1 Four Basic Counting Principles
- Addition, Subtraction, Multiplication and Division Principles of Counting.
- 3.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. See Permutations Worksheet.
- 3.3 Combinations of Sets
- r-combinations; the number of ways of selecting r objects from a collection of n distinct objects. See Combinations Worksheet.
- 3.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.
- 3.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 Formula
- Pascal's Formula for the binomial coefficients, Pascal's Triangle.
- 5.2 The Binomial Theorem
- Expanding (x+y)n.
- 5.3 Identities
- Identities involving binomial coefficients.
- 5.5 The Multinomial Theorem
- Expanding (x1 + x2 + x3 + ... + xk )n.
|
| 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 Linear Homogeneous Recurrence Relations
- How to compute solutions of linear homogeneous recurrence relations with constant coefficients; Characteristic equation and characteristic roots.
- 7.3 Nonhomogeneous Recurrence Relations
- How to compute solutions of linear nonhomogeneous recurrence relations with constant coefficients.
- 7.4 Generating Functions
- How to use power series to find solutions to combinatorial problems.
- 7.5 Recurrences and Generating Functions
- How to use generating functions to find solutions to recurrence relations.
- 7.7 Exponential Generating Functions
- Using exponential generating functions to count combinatorial objects.
|
| 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 Method of Inclusion-Exclusion
- How to count the cardinality of the union of sets that overlap without restriction.
- Rogers-Ramanujan Identities
- A brief introduction to the world's most famous partition identity.
- The 20-fold Way
- A review of many of the concepts studied this semester by way of arranging books on shelves. See The 20-fold Way Worksheet
|