AcademicsCombinatorics
Academics >> Mathematics >> Courses
Instructor: Matt Ollis
NSC 503
TuTh 11:20 - 12:50 Sci 217 Intermediate
Office: Sci 218
Email: matt@marlboro.edu
Combinatorics is the study of arranging objects to satisfy given rules. That is, we try to solve puzzles such as:
a) Take a chessboard and remove a pair of diagonally opposite corner squares. Suppose we have some dominos, each of which exactly covers two adjacent squares of the chessboard. Is it possible to exactly cover this chessboard using the dominos?
b) Kirkman's Schoolgirl Problem (1850): A schoolmistress takes her class of 15 girls on a daily walk. The girls are arranged in 5 rows, with 3 girls in each row, so that each girl has 2 companions. Is it possible to plan a walk for 7 consecutive days so that no girl will walk in a triplet with any of her classmates more than once?
c) Suppose a region of land is to be divided into countries. How many colors do we need so that, however the region is divided, we can produce a map of the region in which no two neighboring countries are the same color?
If we can show that a certain arrangement exists, then we are interested in how many possible arrangements there are. In the course we study some essential techniques of combinatorics and then look at some problems from various areas of the field. We also consider how combinatorial techniques and results apply to other fields, such as experimental design and computer science.
Course Structure: The course text is "Introductory Combinatorics" (3rd edition) by Richard Brualdi (available in bookstore and on reserve in the library). An approximate outline for the course is chapters 1-3, 5, 6, 9-12 of the text. There will be two types of homework assignment. The first type will consist of problems which reinforce and build on the skills we are developing in class; the second type will be a single challenging problem. They will be set on alternate Thursdays. The first type are due by 4pm the following Wednesday. For the second type there is nothing to hand in, but you should come to class the following Thursday ready to discuss progress you have made and approaches you have attempted.
Grading: Your grade will be based on 3 equally weighted components; the first type of homework, a final exam and class participation. The class participation component will rely heavily on your engagement with the problems in the second type of homework.
Prerequisite: None
Homework Assignments:
Homework 3
Challenge Problem 4
Other material:
