C&O 330 Combinatorial Enumeration

Fall 2009

Who?

Instructor

David G. Wagner
office: MC 5040, phone: x32487
dgwagner@math.uwaterloo.ca
OFFICE HOURS: Mon & Weds 4:00-5:00 or by appointment.

Teaching Assistant

Jon Dietrich
office: MC 5164, phone: x36673
jedietrich@uwaterloo.ca
OFFICE HOURS: Weds 3:00-4:00 or by appointment.


Where and When?

Lectures: MWF 10:30-11:20 in MC 4042.
Tutorials: none.
Office Hours: see above
Midterm Exam: Monday Nov.2 / 4:30-6:00 / MC 4058.
Final Exam: Saturday Dec.19 / 4:00-6:30 / PAC 9.
EXAM SCHEDULE OFFICE HOURS: DGW: 14th and 16th, 1:00-3:00 / JD: 17th and 18th, 1:00-3:00.

What?

Homework: 15%

Midterm Exam: 30%

Final Exam: 55%


Homework assignments and solutions, midterm exam solutions, and supplemental notes will be posted here.

Homework assignments will be due every second Friday (or so) at the beginning of class.

The textbook will be course notes on sale (for cost) at Campus Copy (MC 2018).
The enumeration section of the MATH 239 course notes is worth keeping handy for reference and review. Moreover, here are some supplemental notes to start with: this is an introduction at a very elementary level, written for CO 220.

  • Basic Principles of Enumeration and Examples and Applications [PDF file]


    • Main Topics of the Course
  • Finite Sets and Bijections
  • The q-Binomial Theorem
  • Recursive Structure
  • The Lagrange Implicit Function Theorem
  • Algebra of Formal Power Series
  • Integer Partitions
  • Exponential Generating Functions

    • Secondary Topics
  • Ordinary Generating Functions
  • Lattice Paths
  • Polynomial Identities
  • Catalan Numbers
  • Inclusion/Exclusion


  • READ: Section 1 up to Example 1.9, Section 2, Section 3.


  • HOMEWORK ASSIGNMENT #1: due Friday, Oct. 2nd.
    Exercises: 1.1, 1.5, 2.1, 2.3, 3.6, 3.8, 3.10, 3.11.
    (A little bit long since it covers three weeks.)
    Solutions: [PDF file]


  • READ: Sections 4 and 5, start Section 6.


  • HOMEWORK ASSIGNMENT #2: due Friday, Oct. 16th.
    Exercises: 5.2, 5.4, 5.5, 5.6, 5.7 [Typo: prove Theorem 5.8], 6.1, 6.7.
    Solutions: [PDF file]


  • READ: Sections 6 and 7, start Section 8.


  • HOMEWORK ASSIGNMENT #3: due Friday, Oct. 30th.
    Exercises: 6.9, 7.3, 7.6, 7.8(a), 7.11, 7.12(a,b,c), 8.1.
    TYPO in 7.6: the recurrence should be f_{k+1}(x) = f_k(x) + x^k*f_{k-1}(x) for all k>=1. Oops sorry, my bad. ;-(
    Solutions: [PDF file]


  • READ: Sections 8 and 9.


  • HOMEWORK ASSIGNMENT #4: due Friday, Nov. 13th.
    Exercises: 8.2, 8.5, 9.1, 9.3, 9.5, 9.6.
    Solutions: [PDF file]


  • MIDTERM EXAM SOLUTIONS.


  • READ: Section 10 (EPNT and JTPF), start 11.


  • HOMEWORK ASSIGNMENT #5: due Friday, Nov. 27th.
    Exercises: 9.9, 10.3, 10.4, 10.8, 11.3, 11.5, 11.6.
    Solutions: [PDF file]
    Amusing Factoids: [text file]


  • READ: Section 11.


  • HOMEWORK (1/2)ASSIGNMENT #6: due Friday, Dec. 4th.
    Exercises: 11.7, 11.8, 11.9, 11.12.
    Solutions: [PDF file]


    • Why?

    Because it is interesting! Besides which, you can use this stuff in probability theory, theoretical computer science, physics, and a bunch of other ways.

    NOTICES ON ACADEMIC INTEGRITY

    The University requires me to include this. You should know it already!