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

Prerequisites: Grade of C or better in either MA225 or CSC226
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.