Math 447/557, Combinatorial Mathematics, Spring 2019

Information Type Data
Meeting Time MWF, 2:00—2:50
Meeting Room PAS 414
Instructor Professor Marek Rychlik
Office Mathematics 605
Email rychlik@email.arizona.edu
Telephone 1-520-621-6865
Homepage http://alamos.math.arizona.edu/~rychlik/math447
Homepage (Mirror) http://marekrychlik.com/math447

Office Hours

Personnel Day(s) of the Week Hour Room Comment
Marek Rychlik M 3:00pm—3:50pm Mathematics 220 Upper Division Tutoring Room
Marek Rychlik W 3:00pm—3:50pm Mathematics 605 Regular Office Hours in my office
Marek Rychlik F 12:20pm—1:10pm Mathematics 605 Regular Office Hours in my office

Required Texts

Applied Combinatorics, Sixth Edition, Alan Tucker, John Wiley & Sons, required.

Textbook Errata

They can be found at this link: Corrections to Applied Combinatorics 6th Edition.

Required Examinations

Two 1-hour Midterms, worth 20% of the course grade each, and a 2-hour Final Exam worth 30%.

Homework

Homework is assigned weekly and graded, and it counts for 30% of course grade. The grade for each assignment shall be based on a representative sample of the assigned problems. Homework shall be submitted as a typed paper, with the exception of these graphs and figures which cannot be easily drawn with software. Recommended tools for preparing the homework paper are LaTeX and Graphviz or TikZ for drawing graphs. They will be briefly discussed in class. Proofs should be complete, concise and clear in terms of reasoning and presentation.

Extra Credit Assignments

Mastermind Extra Credit

In the first month of the course, there will be weekly Mastermind puzzles posted on this webpage each Monday at 10:00 pm. Mastermind is explained in the Prelude at the front of the textbook. The first five students to submit the correct solution (with an explanation of their reasoning if required) will get 3 extra points on the first test; the next five students to submit the correct sequence will get 2 extra points on the first test and the next 5 students will get one extra point on the first test.

Overall Course Objectives and Expected Learning Outcome

  1. Strengthen logical reasoning skills to solve combinatorial problems using:

  2. Learn to find multiple (equally valid) ways to solve a combinatorics problem:

  3. Learn basic graph theory results and apply them in problem-solving:

  4. Use formulas for counting basic combinatorial outcomes to construct solutions to more complex combinatorial enumeration problems:

  5. Apply counting strategies to solve discrete probability problems.
  6. Use specialized techniques to solve combinatorial enumeration problems:

Course Outline

Week Dates Topics Sections Covered
1—2 Jan 9—Jan 18 Graph Theory Basics, Isomorphism 1.1, 1.2, 1.3
3 Jan 21—Jan 25 Planar Graphs, Euler Cycles 1.4, 2.1
4 Jan 28—Feb 1 Planar Graphs, Euler Cycles and Trails 1.4, 2.1
5 Feb 4—Feb 8 Hamilton Circuits, Graph Coloring 2.2, 2.3, 2.4
6 Feb 11—Feb 15 Graph Coloring, Trees and Searching 2.4, 3.1, 3.2
7 Feb 18—Feb 22 Graph Coloring, Trees and Searching, Traveling Salesperson Problem 2.4, 3.1, 3.2, 3.3
8 Feb 25 Review for Midterm 1
8 Feb 27 Midterm 1
8 Mar 1 Basic Permutations and Combinations 5.1, 5.2
Mar 2—Mar 10 Spring Recess
9 Mar 11—Mar 15 Counting Problems with Repetition 5.3, 5.4
10 Mar 18—Mar 22 Counting Problems with Repetition, Generating Function Models 5.3, 5.4, 6.1
11 Mar 25—Mar 29 Generating Function Models, Evaluating Generating Function Coefficients 6.1, 6.2
12 Apr 1 Review for Midterm 2
12 Apr 3 Midterm 2
12 Apr 1 Evaluating Generating Function Coefficients, Recurrence Relations 6.2, 7.1
13 Apr 8—Apr 12 Recurrence Relations 7.1, 7.3
14 Apr 15—Apr 19 Inclusion-Exclusion Principle 8.1, 8.2
15 Apr 22—Apr 26 Chromatic Polynomials, Rook Polynomials, Review and/or Optional Topics 8.3
16 Apr 28—May 1 Review and/or Optional Topics
Finals Week May 3 Final Exam, 1:00 pm - 3:00 pm (regular room)

Course Policies

Attendance Policy

Students are expected to attend every scheduled class and to be familiar with the University Class Attendance policy as it appears in the General Catalog. It is the student's responsibility to keep informed of any announcements, syllabus adjustments or policy changes made during scheduled classes.

Expected Classroom Behavior

Students are expected to behave in accordance with the Student Code of Conductand the Code of Academic Integrity. The guiding principle of academic integrity is that a student's submitted work must be the student's own. University policies can be found at http://policy.arizona.edu/academic.

Threatening Behavior

See http://policy.web.arizona.edu/threatening-behavior-students. No prohibited behavior will be tolerated.

Administrative Drop

Students who miss the first two class meetings will be administratively dropped unless they have made other arrangements with the instructor.

Missed Exams

Students are expected to be present for all exams. If a verifiable emergency arises which prevents you from taking an in-class exam at the regularly scheduled time, the instructor must be notified as soon as possible, and in any case, prior to the next regularly scheduled class. Make-up exams and quizzes will be administered only at the discretion of the instructor and only under extreme circumstances. If a student is allowed to make up a missed exam, (s)he must take it at a mutually arranged time. No further opportunities will be extended. Failure to contact your instructor as stated above or inability to produce sufficient evidence of a real emergency will result in a grade of zero on the exam. Other remedies, such as adjusting credit for other exams, may be considered.

Accessibility and Accommodations

Disabled students must register with Disability Resources and be identified to the course instructor through the University's online process in order to use reasonable accommodations.

It is the University's goal that learning experiences be as accessible as possible. If you anticipate or experience physical or academic barriers based on disability, please let me know immediately so that we can discuss options. You are also welcome to contact Disability Resources 520-621-3268 to establish reasonable accommodations.

Please be aware that the accessible table and chairs in this room should remain available for students who find that standard classroom seating is not usable.

Policy on the grade of "I" (incomplete)

The grade of "I" will be awarded if all of the following conditions are met:

Disclaimers

Changes to the Syllabus

The information contained in the course syllabus, other than the grade and absence policies, is subject to change with reasonable advance notice, as deemed appropriate by the instructor.