Math 447/547 Spring 2009

Title: Combinatorial Mathematics
Class: MWF 2:00 to 2:50 pm, PSYCH 305
Problem sessions: Friday 3:00 to 4:00 pm PSYCH 206
Instructor: Ji Li
Office: Math 319
Phone: (520) 621-6870
Email: jli at email.arizona.edu
Office Hours: MWF 1:00 to 1:50pm, and by appointments.

Syllabus (pdf)

Weekly Notice

• Week 15: May 4 thru May 8: contains information about the last week.
• Week 14: Apr 27 thru May 1: Lessons on old and new problems are covered in class. Optional take-home final exam is due on May 3.
  • Solutions to take-home final exam.
• Week 13: Apr 20 thru Apr 24: Lessons on Graphs are covered in class. Homework 11 is due on Apr 27.
  • Solutions to Homework 11
• Week 12: Apr 13 thru Apr 17: Lessons on Permutation Groups and Labeled Trees are covered in class. Homework 10 is due on Apr 20.
  • Solutions to Homework 10
• Week 11: Apr 6 thru Apr 10: including Homework 9 (Sections 9.1 and 9.2) due on Apr 13.
  • Solutions to Homework 9
• Week 10: Mar 30 thru Apr 3: the next homework assignment will be due on Monday, Apr 13.
• Week 9: Mar 23 thru Mar 27: including Homework 8 (Section 8.3) due on Mar 30.
  • Solutions to Homework 8
• Week 8: Mar 9 thru Mar 12: including Homework 7 (Sections 8.1 and 8.2) due on Mar 23.
  • Solutions to Homework 7
• Week 7: Mar 2 thru Mar 6: including Homework 6 (Sections 7.1, 7.3, and 7.5) due on Mar 9.
  • Solutions to Homework 6
• Week 6: Feb 23 thru Feb 27: including Homework 5 (Section 7.1) due on Mar 2.
  • Solutions to Homework 5
• Weeks 4 & 5: Feb 9 thru Feb 20: including Homework 3 (Sections 6.1 and 6.2) due on Feb 16, and Homework 4 (Section 6.4) due on Feb 23.
  • Homework 4 Extra problem
  • Solutions to Homework 3
  • Solutions to Homework 4
• Week 3: Feb 2 thru Feb 6: Exam 1 information, Review session scheduling.
• Week 2: Jan 26 thru Jan 30: including Homework 2 (Sections 5.3, 5.4 and 5.5) due on Feb 2.
  • Solutions to Homework 2
• Week 1: Jan 14 thru Jan 23: including Homework 1 (Sections 5.1 and 5.2) due on Jan 26.
  • Solutions to Homework 1

Lessons

• End-of-semester Lecturs
  • Lesson36, May 4: Trees and Degree Sequences.
  • Lesson35, May 1: Miscellaneous Problems: Part III.
  • Lesson34, Apr 29: Miscellaneous Problems: Part II.
  • Lesson33, Apr 27: Miscellaneous Problems: Part I.
• Chapter 9
  • Lesson32, Apr 20, 22, 24: Enumeration of Graphs.
  • Lesson31, Apr 17: Labeled Trees, Part II.
  • Lesson30, Apr 15: Labeled Trees, Part I.
  • Lesson29, Apr 10, 13, 15: Cycle Index of Group Actions and Permutation Groups.
  • Lesson28, Apr 8: Polya's Cycle Index: Examples (Part of Homework due on Monday, April 20).
  • Lesson27, Apr 6: Weighted Version of Cauchy-Frobenius Theorem Part II, and Power Sum Symmetric Functions.
  • Lesson26, Mar 30: Weighted Version of Cauchy-Frobenius Theorem Part I.
  • Lesson25, Mar 27: Cauchy-Frobenius Theorem.
  • Lesson24, Mar 27: Group of Symmetries.
  • Lesson23, Mar 25: Group Actions.
• Chapter 8
  • Lesson22, Mar 25: Rook Polynomials and Problem Manage.
  • Lesson21, Mar 23: Restricted Permutations and Rook Polynomials.
  • Lesson20, Mar 11: Derangements and Notations.
  • Lesson19, Mar 9: Inclusion-Exclusion and Derangements.
  • Lesson18, Mar 6: Venn Diagram and Inclusion-Exclusion.
  • Lesson17, Mar 4: Venn Diagram.
• Chapter 7
  • Lesson16, Mar 2: Recurrence Relations: Part III.
  • Lesson15, Feb 27: Recurrence Relations: Part II.
  • Lesson14, Feb 25: Recurrence Relations: Part I.
• Chapter 6
  • Lesson13, Feb 20: Composition of Exponential Generating Functions
  • Lesson12, Feb 18: Exponential and Ordinary Generating Functions
  • Lesson11, Feb 16: Exponential Generating Functions
  • Generalized Pigionhole Principle
  • Lesson10, Feb 10: from section 6.1 to 6.2: Generating Functions
  • Lesson9, Feb 9: starting section 6.1: Introducing (Ordinary) Generating Functions
• Chapter 5
  • Lesson8, Feb 1: finishing section 5.5
  • Lesson7, Jan 30: starting section 5.5
  • Lesson6, Jan 28: finishing section 5.4
  • Lesson5, Jan 26: from section 5.3 to section 5.4

Exams

• Final Exam and solutions.
  • Review Sheet for Final Exam.
• Exam 2 and solutions.
  • Review Sheet for Exam 2.
• Exam 1 and solutions.

Puzzles and Some of the Solutions

• Puzzle 8: problem on derangements.
• Puzzle 7: problem on recurrence relations: solved by Anantha Krishnan, and Michael O'Connell.Solution
• Puzzle 6: Problem 10 on page xiv: solved by James Pohl.
• Puzzle 5: problem: solved by Anantha Krishnan.
• Puzzle 4: problem: solved by Anantha Krishnan. Solution
• Puzzle 3: Problem: solved by Dzung Nguyen.
• Puzzle 2: Problem: solved independently by James Pohl and Marcus Schmidt.
• Puzzle 1: Problem 2 on page xiii, solved by Ben Robbins. Solution.

Supplementary Handouts

• Chapter 5
  • For Chapter 5: Numerical Problems: containing different counting problems for different levels.
  • From Section 5.1: Arranging Books: a different approach to Example 3, and a basic idea of Inclusion-Exclusion.

Quotes

No matter what it is, there is nothing that cannot be done. If one manifests the determination, he can move heaven and earth as he pleases. But because man is pluckless, he cannot set his mind to it. Moving heaven and earth without putting forth effort is simply a matter of concentration.
Yamamoto Tsunetomo in "Shadow of the Leaves".