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