- You are here:
- Home

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:

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)