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.

SUGGESTED TEXT(S):
Proofs that Really Count: The Art of Combinatorial Proof by Benjamin and Quinn
Introductory Combinatorics by John Brualdi
Applied Combinatorics by Alan Tucker

COURSE OUTLINE:

1. 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.
   • Inclusion-exclusion
2. 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)
3. 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