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 used in discrete problem solving: counting methods, solving linear recurrences, graph and network models, related algorithms, and combinatorial designs.

Prerequisites: 

MATH 1502 OR MATH 1512 OR MATH 1555 OR MATH 1504 ((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 and Newton's binomial theorem
  • Inclusion Exclusion: The inclusion-exclusion principle, combinations with repetition, and derangements
  • Recurrence Relations and Generating Functions Fibonacci numbers, linear homogeneous recurrences, nonhomogeneous recurrences
  • Generating functions, exponential generating functions
  • Graph Theory -- 1 Graph isomorphism, connectivity, Euler trails, Hamilton cycles, the traveling salesman
  • Graph Theory -- 2 Graph coloring, planarity, matchings, system of distinct representatives
  • Graph Algorithms: Search algorithms, shortest paths and spanning tree algorithms
  • Elementary number theory: Divisors, primes, factorization into primes, modular arithmetic, Fermat's little theorem and the Euclidean algorithm (optional)