Department of Mathematics

Van Vleck Hall, 480 Lincoln Drive, Madison, WI

Math 475: Introduction to Combinatorics

 
Student Body: 

Math, statistic and comp science majors

Background and Goals: 

As the title Introduction to Combinatorics suggests, Math 475 is a first course with emphasis on the basics of combinatorial counting techniques, number sequences, and patterns, with some graph theory thrown in. It is not however a course on what is traditionally called discrete mathematics. We will discuss algorithms for some of the combinatorial problems considered.

Alternatives: 

N/A

Subsequent Courses: 

N/A

Course Content: 
  • Pigeon-hole principle and applications
  • Permutations and combinations
  • Generating permutations and combinations
  • Properties of binomial coefficients (combination numbers)
  • Partial orders, equivalence relations, and Dilworth's theorem
  • Inclusion-exclusion principle
  • Recurrence relations and generating functions
  • Difference sequences, Catalan numbers, Stirling numbers, partition numbers, and other counting sequences
  • Marriage Theorem and Stable Marriages
  • Graph theory (paths, cycles, trees, graph coloring, etc.)
  • Polya counting (counting in the presence of symmetries)

Some topics are omitted according to instructor.

credits: 
3. (N-A)
semester: 
FallSpring
prereqs: 
Math 320 or 340, or consent of instructor.

UW-Madison Department of Mathematics
Van Vleck Hall
480 Lincoln Drive
Madison, Wi  53706

(608) 263-3054

Contact Us

Got a question about
accessibility, content
or structure of this website?
webmaster@math.wisc.edu