Basic Combinatorics

(3 Credit Hours) · Undergraduate

Combinatorics is the study of objects that are fundamentally discrete (made up of distinct and separated parts) as opposed to continuous. For example, instead of studying differential equations to see how a system evolves as time passes continuously, we study recurrence relations to see how some quantity changes as time increments unit by unit; in place of the functions on the real line studied in analysis, combinatorics looks at functions on a finite set. Combinatorics has been increasing in importance in recent decades, in part because of the advent of digital computers (which operate and store data discretely), and in part because of the recent ubiquity of large discrete networks (social, biological, ecological, ...). Typical objects studied in combinatorics include graphs (networks consisting of nodes, some pairs of which are joined), permutations (arrangements of distinct objects in various different orders), and finite sets and their subsets. There are many aspects of combinatorics, such as enumerative, structural (e.g., when is it possible to travel around a network, visiting each edge once and only once?), extremal (e.g., if you know which pairs of people in a class don't like each other, what's the smallest number of groups the class can be broken up into, with no two enemies together in a group?), and algorithmic (e.g., if you know the cost of connecting each possible pair of a set of towns, how can you find the most economical network that fully connects up the towns?). In this course, we will explore each of these aspects of combinatorics, and maybe some more as time permits.