Department:
MATH
Course Number:
3012
Hours - Lecture:
3
Hours - Lab:
0
Hours - Recitation:
0
Hours - Total Credit:
3
Typical Scheduling:
Every semester Description:
Elementary combinatorial techniques used in discrete problem solving: counting methods, solving linear recurrences, graph and network models, related algorithms, and combinatorial designs.
Prerequisites:
Course Text:
Discrete and Combinatorial Mathematics (5th edition) by Grimaldi
Topic Outline:
- Preliminaries Bijections, the pigeon-hole principle, and induction
- Permutations and Combinations Counting sequences, counting subsets of a fixed size, distribution of identical objects, combinatorial probability (events and probability, independent repetition of an experiment)
- 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, (example recurrences from divide and conquer algorithms), 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)
- Combinatorial Designs Difference sets, block designs, and Steiner triple systems