Math 28: Introduction to Combinatorics

Winter 2016

Syllabus



Course Description

Math 28 is a course in combinatorial mathematics. In this course we will concentrate on enumerative combinatorics, this area of combinatorics is concerned with "counting" the objects in a set. Some of the techniques we will learn include:

  • Basic counting principles: Sum principle and product principle
  • Bijective principle
  • Counting in two ways
  • Pigeonhole principle
  • Induction and recursions
  • Ordinary generating functions
  • Inclusion-Exclusion principle
    Along the way we will learn how to count many mathematical objects, the number of subsets of a set, number of lattice paths, Dyck paths (or Catalan paths), functions, one-to-one functions, onto functions, distributions, multisets, set partitions, compositions, classes of partitions, etc. We will learn the basics of graph theory and proof writing.

    The philosophy of this course is that you learn by "doing", therefore most of our class time will be devoted to you solving problems and discussing problems. This means that the primary text for the course is a book of problems. It is available at the Wheelock Books in the form of course notes. Students are encouraged to work in groups on the problems. Students are expected to work as many of the problems as they can and submit them. Certain problems will be designated each week in advance as "mandatory" problems. These problems will be graded and returned to the student.

    As mentioned above, class time will be devoted largely to a discussion of the problems and the broad themes in combinatorial mathematics that the problems illustrate. This discussion will be split between whole class discussion, including possible student presentations of their ideas, and small group discussions.

    The objectives of the course are:

  • Students will be able to solve problems in enumerative combinatorics.
  • Students will improve their oral communication skills by explaining solutions to problems.
  • Students will improve their proof-writing skills.
  • Students will be well-prepared for Computer Science courses and Mathematics courses that use combinatorics.
    • "Mathematics is not for spectators; in order to gain in understanding, confidence, and enthusiasm one has to participate." M.A. Armstrong
    Exams
    DateTime & Location
    Midterm #1 Friday, January 29 4:00 - 6:00 PM - KH 007
    Midterm #2 Friday, February 19 4:00 - 6:00 PM - KH 007
    Final Exam Sunday, March 13 8:00 - 11:00 AM KH 105

    Grades
    The course grade will be computed as follows:

    Percent of Final Grade
    Midterms 30 (15 each)
    Homework 25
    Participation 15
    Final Exam 30

    Students will be graded on class participation. Unfortunately, coming late to class may disrupt small group discussions, and so this will have to be reflected in the class participation grades of students who habitually come late to class. Of course it is difficult to participate if one does not come to class at all, and so habitual absence will also be reflected in the class participation grade.
    Homework Policy
    • Buy a binder instead of a notebook for this class. It will be easier to add remove assignments this way.
    • Written homework will be assigned daily and will be collected once a week at the beginning of class.
    • The mandatory homework will be graded on a 10/9/7/5/0 rule. Perfect problems (correct and well written) will be assigned a 10. Problems that are correct, but have small issues with the way they were written will receive a 9, problems that are mostly correct or have problems with explanations will be assigned an 7, problems where the student has made some progress towards a correct solution but it is not completely correct or it is poorly written will be assigned a 5, and if the solution is incorrect a 0.
    • If a student receives an 7, 5 or 0 on a problem, he or she will be allowed to hand-in the problem a second time within a week from the time the homework is returned to the student. Students can only "rewrite" a problem, it is not allowed to hand in problems for regrade if the student did not attempt the problem by the time it was originally due.
    • All homework assignments will be posted on the course assignment's webpage.
    • Unexcused late and missing papers count zero.
    • Homework is to be written neatly using both sides of 8 1/2 x 11 inch paper. Do not use paper from a spiral notebook unless you can tear off the ragged edge. All papers are to be stapled.
    • Use English. If you can't read your solutions aloud as fluently as if you were reading a textbook, try using nouns and verbs in your write ups!
    If you do not follow this guidelines, your homework will be returned to you ungraded.
    Textbook
    Combinatorics Through Guided Discovery (November 6, 2004 edition) by Kenneth Bogart.
    Available online: here.
    Honor Principle
    Students are encouraged to work together to do homework problems. What is important is a student's eventual understanding of homework problems, and not how that is achieved. However, when the student writes the solution to the homework, he/she should write her own understanding of the problem. It is not allowed to read someone else's solution to write yours.

    The honor principle on homework: What a student turns in as a homework solution is to be his or her own understanding of how to do the problem. Students must state what sources they have consulted, with whom they have collaborated, and from whom they have received help. It is a violation of the honor code to copy solutions from problems posted on the web or book or any other source. The solutions you submit must be written by you alone. Any copying (electronic or otherwise) of another person's solutions, in whole or in part, is a violation of the Honor Code. For example, it is a breach of the honor code to read the solutions of someone else in order to write your solution.

    The honor principle on exams: Students may not give or receive assistance of any kind on an exam from any person except for the professor or someone explicitly designated by the professor to answer questions about the exam.

    If you have any questions as to whether some action would be acceptable under the Academic Honor Code, please speak to me I will be glad to help clarify things. It is always easier to ask beforehand than to have trouble later!
    Disabilities and Religious Observances
    Students with disabilities enrolled in this course and who may need disability-related classroom accommodations are encouraged to make an appointment to see your instructor before the end of the second week of the term. All discussions will remain confidential, although the Student Accessibility Services office may be consulted to discuss appropriate implementation of any accommodation requested.

    Some students may wish to take part in religious observances that occur during this academic term. If you have a religious observance that conflicts with your participation in the course, please meet with your instructor before the end of the second week of the term to discuss appropriate accommodations.

    Page created and maintained by R. Orellana