Mathematics 357 – Combinatorics Course Information Spring 2017

Professor: John Little Office: Swords 331 Office Phone: 793-2274 Office Hours: M 10-11am, T 9-10am, W 1-2pm, R 2-3pm, F 10-11am, and by appointment Email: jlittle@holycross.edu

Course Homepage: http://mathcs.holycross.edu/~little/Combo17/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). If such an arrangement does exist, 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? For instance, can we color the vertices of a cube using three different colors in such a way that no two vertices joined by an edge have the same color?

2) Enumeration or counting questions: If arrangements of a particular type do exist, how many distinct ones are there? And, under what circumstances do we want to think of arrangements as distinct? For instance, if we were looking at arrangements of beads of three different colors around a circular bracelet, we might want to think of two arrangements as the same if one can be rotated into the other one!

This course will offer an introduction to the subject as a whole. We will focus more or less on the enumeration questions, 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 for the Mathematics majors in the classes of 2017 and 2018.

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, possibly 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 How To Count: An Introduction to Combinatorics and Its Applications by Robert Beeler, published by Springer in 2015. We will study most of the book (but omit Chapter 9 on applications to Probability) this term. Many of you have taken or will take MATH 375 (Probability Theory), so while there might be some overlap with the applications of counting techniques you may have seen there, I want to keep that to a minimum.

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 may 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 also keep a written record of the group’s observations, results, questions, etc. which will be handed in. I will grade theses 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 40% of the course grade. Tentative dates: a. Friday, February 24. b. Friday, April 7. Information about what will be covered, practice problems, etc. will be posted on the course homepage at least one week before each of the exams.

2. Final exam OR final project and presentation worth 30% of the course grade. I hope to offer everyone the option of either taking a standard final exam, or else preparing a final project paper and making an accompanying oral presentation, working as a team with one other student in the class. Subject to approval by Prof. Levandosky (the Math/CS Chair), a project for this course may be used to satisfy the project course requirement for the Mathematics major.

Some groundrules: a. I will only be able to handle the task of supervising about 6-8 of these projects. b. Since some students will already have satisfied the project course requirement in

other ways or would prefer to take a final instead of doing a project, I reserve the right to declare that some of you will need to take the final exam.

c. The final exam for this course will be given at the usual time for MWF 11am

classes (to be determined). d. The date(s) and time(s) for the final project presentations will be determined

later.

3. Individual Problem sets (roughly weekly) worth 20% of the course grade.

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

I will be keeping your course average in numerical form throughout the semester, and only converting to a letter for the final course grade. The course grade will be assigned according to the following conversion table (also see Note below):

A – 94 and above A- – 90 - 93 B+ – 87 - 89 B – 84 - 86 B- – 80 - 83 C+ – 77 - 79 C – 74 - 76 C- – 70 - 73 D+ – 67 – 69 D – 60 - 66 F – 59 and below.

Note: Depending on how the class as a whole is doing, some downward adjustments of the above letter grade boundaries may be made. No upward adjustments will be made, however. (This means, for instance, that an 85 course average would never convert to a letter grade of B- or below, although it might be a B+ in some circumstances.) If you ever have a question about the grading policy or your standing in the course, don’t hesitate to ask me. If you ever have a question about the grading policy, or about your standing in the course, please feel free to consult with me.

Statement on Academic Integrity

All education is a cooperative enterprise between teachers and students. This cooperation works well only when there is trust and mutual respect between everyone involved.

To be become an engaged and advanced learner, you must be able to think and work both independently and in concert with your peers. The College academic honesty policy states: “As an institution devoted to teaching, learning, and intellectual inquiry, Holy Cross expects all members of the College community to abide by the highest standards of academic integrity. Any violation of academic honesty undermines the student-teacher relationship, thereby wounding the whole community. The principal violations of academic honesty are plagiarism, cheating, and collusion.

Plagiarism is the act of taking the words, ideas, data, illustrative material, or statements of someone else, without full and proper acknowledgment, and presenting them as one’s own.

Cheating is the use of improper means or subterfuge to gain credit or advantage. Forms of cheating include the use, attempted use, or improper possession of unauthorized aids in any examination or other academic exercise submitted for evaluation; the fabrication or falsification of data; misrepresentation of academic or extracurricular credentials; and deceitful performance on placement examinations. It is also cheating to submit the same work for credit in more than one course, except as authorized in advance by the course instructors.

Collusion is assisting or attempting to assist another student in an act of academic dishonesty.”

The full statement on Academic Honesty in the College Catalog is available at

       http://www.holycross.edu/catalog/academic-honesty-policy.pdf

While the temptation to engage in an act of academic dishonesty may arise because of time pressure, other events in your life, and so forth, using dishonest means to enhance a single grade is not worth the loss of your personal integrity. If in doubt about what you plan to do or write violates academic honesty, PLEASE ASK!

Specific Guidelines for this Course

In this course, the examinations will be closed-book. No sharing of information with other students in any form will be permitted during exams. On group discussion write-ups, close collaboration with the other members of your group is expected. On the individual problem sets, discussion of the questions with other students in the class and with me during office hours is allowed, even encouraged. However, your final problem solutions should be prepared individually and the wording and organization of your final problem solutions should be entirely your own work. Moreover, if you do take advantage of any of the above options for discussion of problems with others, you will be required to state that fact in a footnote accompanying the problem solution. Failure to follow this rule will be treated as a violation of the College’s Academic Integrity policy. For the project papers (if you decide to do one), if you do consult a source other than the course text, include a full reference in a bibliography section at the end of your paper, and identify any direct quotations using endnotes or footnotes. (I’m not a stickler for the form you use, only for giving proper credit where credit is due.)