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: 116 or the equivalent.
Distribution: Mathematical Modeling.

• Megan Kerr mkerr@wellesley.edu
• Department of Mathematics
• Date Created: October 26, 1995
• Last Modified: June 27, 2005
• Expires: June 30, 2006