Math 454 - Combinatorial Theory
Description
Math 454 provides an introduction to common methods in combinatorics, which are applicable to problems such as enumerating the number of states in which some designated pattern is satisfied (tiling boards, placing non-attacking rooks, etc.).
There can be some overlap between Math 428 and Math 454, both of which are courses in discrete mathematics; some iterations of 454 include coverage on some topics in graph theory.
Topics covered
Topics covered in Math 454 include:
- Basic counting
- Permutations and combinations
- Pigeonhole principle
- Binomial coefficients in more detail
- Pascal’s triangle and the binomial theorem
- Various identities involving binomial coefficients
- Combinatorial/counting proofs
- Inclusion-exclusion principle with applications
- Recurrence relations
- Generating functions, ordinary and exponential types
Note that the exact list of topics may vary by instructor and semester. Additional topics may include some graph theory.
Comments on prerequisites
Unofficial/suggested additional prerequisites: Math 300.
Many iterations of Math 454 include writing proofs at some level, so background in proof-based mathematics from Math 300 may be helpful. However, 454 should cover the proof techniques needed in the course, as 300 is not an official prerequisite.
Resources
Textbook
The usual textbook for this class is Introductory Combinatorics by Richard Brualdi.