Combinatorial Analysis

Department: 
MATH
Course Number: 
4032
Hours - Lecture: 
3
Hours - Lab: 
0
Hours - Recitation: 
0
Hours - Total Credit: 
3
Typical Scheduling: 
Every spring semester

Combinatorial problem-solving techniques including the use of generating functions, recurrence relations, Polya theory, combinatorial designs, Ramsey theory, matroids, and asymptotic analysis.

Prerequisites: 

MATH 3012 or equivalent

Course Text: 

At the level of Cameron, Combinatorics: Topics, Techniques, Algorithms, Peter Cameron, Cambridge Univ. Press

Topic Outline: 
  • Basic Counting Techniques Permutations, combinations, sampling with replacement, combinatorial identities
  • Generating Functions Ordinary and exponential generating functions and applications
  • Recurrence Relations Methods of characteristic roots and generating functions, divide/conquer relations
  • The Pigeonhole Principle and Generalizations Applications of the pigeonhole principle, Ramsey theory
  • Enumeration in Graphs Chromatic and matching polynomials, graphic sequences
  • Polya Theory Permutation groups, Burnside's lemma, the cycle index, Polya's theorem
  • Designs and Codes Latin squares, balanced incomplete block designs, Hadamard matrices, applications to the design of error-correcting codes
  • Matroids Equivalent definitions, binary, unimodular, and simplicial matroids
  • Asymptotic Analysis Asymptotic estimates, sums of positive terms, the use of generating functions and recurrences