Math 225, Combinatorics and Graph Theory
The following are some of the types of questions you will encounter in Math 225.
- If you live at the corner of 1st Avenue and 1st Street and you work at the corner of 7th Avenue and 7th Street, in how many different ways can you walk to work without going out of your way?
- How many ways are there to arrange 6 pennies and 6 nickels in a row (where the pennies are identical and so are the nickels)?
- If 25 students are seated in 5 rows of 5 chairs each, is it possible for each student to move to an adjacent seat (where adjacent means directly to the left of, to the right of, in front of, or behind)?
- How many ways are there to make change for $1 using pennies, nickels, dimes, quarters and half dollars?
If you find these problems intriguing then you
will probably enjoy studying combinatorics. Combinatorics is not only
about counting things, but also about discovering relationships between
seemingly different problems. Did you notice that problems 1 and 2
above have the same answer? You can prove it even without computing
that answer. Here's how:
We might as well assume that increasing street numbers mean going north and
increasing avenue numbers mean going east. At each intersection on a walk to
work you must decide whether to go north or east (going south or west will
take you out of your way). Keep a list of what you decide. Eventually you will
need to go 6 blocks north and 6 blocks east, so the problem is equivalent to
making an ordered list of 6 "norths" and 6 "easts" which could serve as directions
for your route. Now if you imagine the norths to correspond to pennies and
the easts to nickels, you can see that each arrangement of 6 pennies and 6
nickels corresponds to a different route to work and conversely, each route
to work corresponds to a different arrangement of 6 pennies and 6 nickels (see
the diagram below for an example).
While problems like these may seem frivolous, in
Math 225 we will study general techniques for solving combinatorial
problems. Results in combinatorics and graph theory have a variety
of applications to fields like computer science and to solving applied
problems such as scheduling problems and telephone network problems.
Math 225 provides a way to meet the "proof-course" prerequisite for Math
302 and Math 305. Math 225 counts toward the mathematics major/minor as an elective.
Prerequisite: Math 116, 120, or the equivalent; or CS 230
together with permission of the instructor.
Distribution: Mathematical Modeling.
Click here to see
when this class is being taught and who will be teaching it.
Created
by: Heather Barrett '08
Maintained
by: Professor Alexia Sontag
Date
Created: June 2005
Last
Modified: August 23, 2007
Expires:
August, 2008