Math 375 Combinatorics

Spring 2019


Announcements

Facebook Friends. Note: I recommend reading Steven Strogatz NYTimes article on this phenomenon.

More examples of the Pigeonhole principle. Box Principle from the book "Problem-solving strategies" by Engel.

The proof of the formula 1+2+...+n we did in class can be found here here. The version published in the American Mathematical Monthly is A Short Proof of a Sum of Powers Formula.

The expected value calculation that used Catalan will appear in the College Math Journal. You can see the paper below:
A birthday in St. Petersburg

The problem about the n sided die and rolling it many times, you can see a write up here. This includes the random (0,1) number solved with integrals (we didn't do that in class).
For the version that will appear in the American Mathematical Monthly, look below
Expected Number of Dice Rolls for the Sum to Reach n.

All the homework assignments will appear here:
Homework


Course Description

Enumeration techniques with emphasis on permutations and combinations, generating functions, recurrence relations, inclusion and exclusion, and the pigeonhole principle. Graph theory with emphasis on trees, circuits, cut sets, planar graphs, chromatic numbers, and transportation networks. Additional topics from designs with emphasis on Latin squares, finite projective and affine geometries, block designs, and design of experiments. Prerequisite: Mathematics 230. ( Under the old GEC, this course meets the Natural Science & Mathematics requirement.) Cross-listed as: CSCI 375
Textbook

Applied Combinatorics 2017 Edition by Mitchel T. Keller and William T. Trotter.

The book is free online and it can be accessed here:
Applied Combinatorics

Topics we will cover

We will cover many of the following topics: If time permits, other subjects such as the probabilistic method, might be covered.

Student Learning Outcomes

Main Goals:


Grading

The course grade will be based on:
Homework 20%,
Midterms 45% (15% each),
Final Exam 35%.


Homework

There will be written homework roughly every week. The homework will be posted here. Collaboration in the homework is permitted, however it must be your own.

Each homework problem should appear on its own page of a sheet of paper. This is because I might randomly select a subset of the problems to be graded. By having each problem on its own page, it is easier to grade only what's relevant. As a corollary, you should not staple your homework assignments.


Exams

There will be three midterms and one final exam. On the midterms and the final exam you must work on the problems on your own. No collaboration permitted in the exams.

The midterms will be outside of class so that you have more time to try the problems.

The tentative dates for the exams:

Attendance

Students are expected to come to every lecture and every exam.

If the dates of the exams conflict with Lake Forest approved events, inform me as soon as possible.

Description of instructional time and expectations:

This course meets 3 times per week for 3 hours per week. The course carries 1.0 course credit (equivalent to four semester credit hours). Students are expected to devote a minimum of 12 hours of total work per week (in-class time plus out-of-class work) to this course.

Academic Honesty

Please read the College's information on Academic Honesty. If a student cheats in an exam, quiz or homework assignment, I will proceed with charging the student with the Academic Honesty Judicial Board. The usual (first) penalty is a 0 in the assignment on which the cheating occured plus some ethics lectures the student would take. The second penalty is usually suspension.

Accommodations Statement

If you believe that you need accommodations for a disability, please consult with The Learning and Teaching Center. Since accommodations may require early planning and are not retroactive, please contact the center as soon as possible. For details about the services for students with disabilities and the accomodations process, visit http://www.lakeforest.edu/academics/resources/disability/.

You are also welcome to contact me privately to discuss your academic needs. However, all disability-related accommodations must be arranged through Teryn Robinson at the Learning and Teaching Center.


Last modified on February 14, 2019.