Mathematics 357 – Combinatorics Course Information Spring 2005

Professor: John Little Office: Swords 335 Office Phone: 793-2274 Office Hours: M-F 10-11, TR 1-3, and by appointment

Course Homepage: http://mathcs.holycross.edu/~little/Combo05/ComboHome.html

Course Description

Combinatorics is a wide-ranging applied and pure mathematical discipline that deals with questions concerning combinations or arrangements of objects, usually from a finite set. For instance, the arrangement might be an ordering of the objects in the finite set, and we might ask whether an ordering with a certain property (for instance, where some specified elements are not adjacent) exists, and if so, how many of them are there? Generalizing this, the basic questions addressed in combinatorics can be broken down into two groups:

1) Existence questions: Do arrangements of a particular type, or with specified properties exist?

2) Enumeration or counting questions: If arrangements of a particular type do exist, how many distinct ones are there?

This course will offer a breadth-first introduction to the subject as a whole. We will investigate a representative sampling of combinatorial problems, and introduce a number of general techniques for solving them. When we make connections with other classes you have taken, we will be drawing primarily on ideas from Algebraic Structures and Linear Algebra, so this course satisfies the Algebra distribution area requirement for the Mathematics major.

The topics we will study this semester are:

1) Counting techniques: permutations and combinations, binomial and multinomial coefficients, recurrence relations, generating functions, counting with symmetry (Polya’s Theorem).

2) Techniques for existence questions: Pigeonhole principle, parity arguments, Hall’s “marriage” theorem.

3) Numerous examples of various types.

Because of the many interconnections between these subjects, we will not be studying them in sequence; rather we will develop the techniques and the examples in tandem, following more or less the ordering of the chapters in our text. A more detailed day-by-day schedule is maintained on the course homepage if you want to see how the semester breaks down that way.

Text

The text for the course is Introductory Combinatorics, 4th ed. by Richard Brualdi, published by Pearson Prentice Hall in 2004. We will study the material from Chapters 1, 2, 3, 4, 5, 6, 7, 9, 11, 14 this term. The remaining chapters can serve as excellent bases for term projects (see below).

Course Format

In order for a student to get as much as possible out of this or any course, regular active participation and engagement with the ideas we discuss are necessary. This is especially true in a subject like combinatorics where the best way to learn the material is to solve lots of problems using the key ideas. Indeed, a major portion of what you should get out of this course is greater confidence and skill in solving problems. To get you more directly involved in the subject matter of this course, regularly throughout the semester, the class will break down into groups of roughly 4 students for one or more days, and each group will work individually on a group discussion exercise. I will be responsible for designing and preparing these exercises, and I will be available for questions and other help during these periods. At the conclusion of each discussion, the class as a whole will reconvene to talk about what has been done, to sum up the results, to hear short oral reports from each group, etc. Each group will keep a written record of the group’s observations, results, questions, etc. which will be handed in. I will make copies of these, and return them with comments. Other meetings of the class will also be structured as lectures when that seems appropriate.

Grading

The assignments for the course will consist of:

1. Two midterm exams together worth 30% of the course grade. Tentative dates: a. Friday, February 25. b. Friday, April 15.

2. Final exam worth 25% of the course grade. The final exam for this course is scheduled for 8:30 a.m. on Thursday, May 12.

3. Individual Problem sets worth 20% of the course grade.

4. Group discussion writeups, worth 10% of the course grade.

5. Group final project, worth 15% of the course grade. More information about the projects will be distributed later in the semester.

If you ever have a question about the grading policy, or about your standing in the course, please feel free to consult with me.