Applied Combinatorics

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

Elementary combinatorial techniques and proof methods used in discrete problem solving.

Prerequisites: 

(MATH 1552 OR MATH 15X2 OR MATH 1X52) AND (MATH 1522 OR MATH 1553 OR MATH 1554 OR MATH 1564 OR MATH 1X53)

CS students should complete CS 2050 before taking MATH 3012.

Course Text: 

At the level of Discrete and Combinatorial Mathematics (5th edition) by Grimaldi

Topic Outline: 
  • Preliminaries: Bijections, the pigeon-hole principle, and induction
  • Fundamental concepts: permutations, combinations, arrangements, selections
  • Basic counting principles: rule of sum, rule of product
  • The Binomial Coefficients Pascal's triangle, the binomial theorem, binomial identities, multinomial theorem 
  • Inclusion Exclusion: The inclusion-exclusion principle, combinations with repetition, and derangements
  • Recurrence Relations and Generating Functions: Fibonacci numbers, ordinary generating functions, exponential generating functions
  • Graph Theory -- 1 Graph isomorphism, connectivity, Euler trails, Hamilton cycles, the traveling salesman
  • Graph Theory -- 2 Graph coloring, planarity
  • Graph Algorithms: Search algorithms, shortest paths and spanning tree algorithms