CSC 416 - Introduction to Combinatorics
Catalog Description:Basic principles of counting: addition and multiplication principles, generating functions, recursive methods, inclusion-exclusion, pigeonhole principle; basic concepts of graph theory: graphs, digraphs, connectedness, trees; additional topics from:Polya theory of counting, Ramsey theory; combinatorial optimization - matching and covering, minimum spanning trees, minimum distance, maximum flow; sieves; mobius inversion; partitions; Gaussian numbers and q-analogues; bijections and involutions; partially ordered sets.
Contact Hours:
- Lecture: 3 hours
Co-requisites: None
Restrictions: None
Coordinator:
Textbook: Combinatorics
Course Outcomes:
Students will learn...
- enumerative combinatorics
- graph theory
- combinatorial optimization
- combinatorial objects and techniques
Topics:
- Addition and multiplication principles, generating functions, recursive methods, inclusion-exclusion, pigeonhole principle.
- Graphs, digraphs, connectedness, trees; additional topics (Polya theory of counting, Ramsey theory)
- Matching and covering, minimum spanning trees, minimum distance, maximum flow
- Mobius inversion; partitions; Gaussian numbers and q-analogs; bijections and involutions; partially ordered sets.
See Course Listings