Classes: Tuesday and Thursday, 11:00 a.m. - 12:15 p.m., Stevenson Center 1310.
Instructor: Mark Ellingham, SC 1514, phone 615 322 6670, email mark.ellingham at vanderbilt.edu.
Web page: http://www.math.vanderbilt.edu/ellingmn/6700.
Office hours: Tuesday and Thursday, 3:10-4:00 p.m., and Wednesday, 1:30-2:30 p.m.
Textbook: I have not been able to find a book that covers all the course material at an appropriate level. Lecture notes covering much of the material will be posted on the class website, but students should expect to rely on their class notes some of the time. Lecture notes will not be posted until after material is covered in class.
Helpful (but not required) background reading: Applied Combinatorics (any edition), Alan Tucker, Wiley.
Assessment: 60% written problems, 25% project, 15% class participation.
Written problems: There are five major topics in the course. Question sheets for each topic will be handed out. You will be required to hand in about half of the questions on each sheet. Questions will be announced on a regular basis during class, and will be due in class on the Thursday of the school week following the week in which they are announced. If you have a good reason for submitting an assignment late, please see me (in advance if at all possible) to make arrangements. Otherwise, late assignments will count as zero.
Solutions to problems should be fully explained, using clear English sentences where necessary. Written problems must be submitted on paper, not in electronic form, unless explicit permission is given due to special circumstances. Solutions should be written neatly on one side only of clean paper with straight (not ragged) edges. Multiple pages should be stapled (not clipped or folded) together. Marks may be deducted for violating these presentation requirements.
Class participation: Most of the problems on the question sheets which are not to be handed in will be presented in class by students. During each class the problems to be presented at the following class will be announced. At the following class students will be chosen by the instructor to present these problems, or students may be assigned in advance to present particular problems.
Project: Students are expected to write a 10 to 20 page paper on some area of combinatorics. A list of topics will be available in early February, and projects should be in progress by Spring break.
Graduate credit: Students registered for Math 6700 are expected to produce a longer and more sophisticated project than students registered for Math 4700.
Honor code: The Vanderbilt Honor Code applies as follows. Work on written problems to be submitted must be done individually; you may not obtain assistance from any source, with the exception of hints given by the instructor. Problems to present in class may be discussed with other students in the class, but you must be able to explain the solution in detail if you expect credit for presenting it. You may discuss your work on the project with others, but the final project must be your own work.
Technology policy: Modern technology is useful but also distracting. Full attention and active participation are expected during class. Therefore, the following are prohibited during class: taking photographs or videos, use of earphones or earbuds, use of cellphones for any purpose. Laptop or tablet use for taking notes or other class-relevant activities that are not distracting to other students may be allowed at the instructor's discretion (let me know if you plan to use one regularly); your laptop or tablet must be silent. Other use of laptops or tablets is prohibited. Students requiring special accommodation should discuss their situation with the instructor.
Good news: No exams, tests or quizzes.
Drop dates: The period to drop or add using YES ends on Monday 14th January. The period to drop or add using a paper form ends on Monday 21st January. The last day to withdraw from the class is Friday 15th March.
This course deals with techniques for counting finite structures. Five main topics will be covered. (Some of these topics are also covered in Math 3700, but we will cover them in a more sophisticated and detailed way.)
1. Permutations and combinations: We enumerate ways of arranging and selecting objects subject to certain conditions. As a simple example, n people may be arranged in a circle in (n-1)! ways.
2. Generating functions: Counting information may be represented and manipulated as formal power series. For example, the number of ways to make change for a dollar in pennies, nickels, dimes, and quarters turns out to be the coefficient of x^100 in the Maclaurin series for 1/((1-x)(1-x^5)(1-x^10)(1-x^25)).
3. Recurrence relations: The number of objects of a given size can often be expressed in terms of the number of objects of smaller sizes. For example, if a_n is the number of objects of size n, many counting problems give rise to the Fibonacci recurrence relation a_n=a_{n-1}+a_{n-2}. We look at how to formulate and solve recurrence relations such as this.
4. Inclusion-exclusion: Often we wish to count objects with a certain combination of properties. For example, to count people with red hair or blue eyes, we add the number with red hair and the number with blue eyes (inclusion), but must then subtract the number with both red hair and blue eyes (exclusion) because they have been counted twice. We develop a general technique for problems of this nature.
5. Polya's Theorem: Sometimes we wish to count only `inequivalent' objects. For example, suppose we colour the sides of a square black or white. There are 16 colourings, but only 6 are inequivalent under the symmetries (rotations and reflections) of a square. Polya's Theorem is a general method for counting problems of this type.