COURSE NUMBER AND TITLE: MATH 3710 Combinatorics
CREDIT HOURS: 3
CATALOG DESCRIPTION: A first course in enumeration. Topics include permutations and combinations of finite sets and multisets, properties of the binomial coefficients, the inclusion-exclusion formula, recurrences, generating functions, the Fibonacci sequence, and properties of the difference operator. The idea of the combinatorial proof is emphasized throughout the course.
PREREQUISITE(S): MATH 2012 or permission of instructor.
Proofs that Really Count: The Art of Combinatorial Proof by Benjamin and Quinn
Introductory Combinatorics by John Brualdi
Applied Combinatorics by Alan Tucker
- Counting Techniques
- The addition and multiplication principles
- Permuations and combinations of a set
- The binomial coefficients
- Binomial coefficient identities as an introduction to combinatorial proof
- The binomial theorem
- Multisets, the multinomial coefficients, and the multinomial theorem.
- Advanced counting techniques
- Recurrences and the Fibonacci sequence
- Combinatorial interpretations of Fibonacci numbers
- Difference equations
- Techniques for solving difference equations
- Derangements of a set
- Generating functions (ordinary and exponential)
- Other topics (as time permits)
- The difference operator and "discrete differentiation"
- Reconstruction of a function via its difference table
- Stirling numbers
- Catalan numbers
- Polynomial analogues of counting sequences