Combinatorial Enumeration

Current announcements

This space will be used for announcements. Check it regularly.

• The course is over.

General Information

The course focuses on generating functions and their uses in enumeration and related topics.

We introduce ordinary and exponential generating functions and their applications to permutations, partitions, rooted trees, etc. We cover multivariate generating functions and computation of moments. We look at hypergeometric functions, and the cycle index of the symmetric group. We also discuss Lagrange inversion, singularity analysis and asymptotic analysis. Time permitting we may touch on other topics such as random combinatorial structures, and the WZ method.

• The tentative lecture schedule per month, as of December 2011 (before classes start) is below.
  The actual material covered in each lecture will be updated below ("Lectures per month").

  Topic	Approx. # of weeks
  Counting techniques, recursions, ordinary and exponential generating functions	2.5
  Formal power series, enumeration by generating functions, the exponential formula	3
  Compute moments using multivariate generating functions	1.5
  Snake oil method; cycle index; introduction to asymptotics	2
  Lagrange inversion; complex asymptotics; singularity analysis	3
  Test	1
  Total	13

• Prerequisites: A combinatorics course equivalent to MATH 3855, or permission of the School.
• Classes begin: Tuesday January 10, 2012.
  Classes end: Thursday April 5, 2012.
  
• Term mark: There will be two assignments. The tentative schedule of assignments is:

  Assignment	Hand-out Date	Due Date	Worth
  1	February 2	March 1	10%
  2	March 8	April 5	10%

  In addition to the assignments, there are two midterm tests on the weeks of February 13-17 and March 26-30, 2012, and a final exam. Each midterm test is worth 15%. To pass the PhD comprehensive in Combinatorial Enumeration a student needs at least 70% in the final exam.

• Evaluation:

  Workload component	Percentage
  2 Assignments at 10% each	20%
  2 Midterm test at 15% each	30%
  1 Final exam	50%

• Withdrawal: The last day for withdrawal from the course without academic penalties is the last day of classes.
• Textbooks: There is no formal textbook for this course. However, much of what we cover can be found in the following books, both of which are available for free download:
  • Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick, and
  • Generatingfunctionology by Herb Wilf .

  Other texts for consult:

  • An Introduction to the Analysis of Algorithms by Robert Sedgewick and Philippe Flajolet, and
  • Concrete Mathematics by Ron Graham, Don Knuth, and Oren Patashnik.
    
• Students with Disabilities: Students with disabilities requiring academic accommodations in this course must register with the Paul Menton Centre for Students with Disabilities (PMC) for a formal evaluation of disability-related needs. Documented disabilities include but are not limited to mobility/physical impairments, specific Learning Disabilities (LD), psychiatric/psychological disabilities, sensory disabilities, Attention Deficit Hyperactivity Disorder (ADHD), and chronic medical conditions. Registered PMC students are required to contact the PMC every term to have a Letter of Accommodation sent to the Instructor by their Coordinator. In addition, students are expected to confirm their need for accommodation with the Instructor no later than two weeks before the first assignment is due or the first in-class test/midterm. If you require accommodations only for formally scheduled exam(s) in this course, you must request accommodations by the last official day to withdraw from classes in each term.
  
• Pregnancy obligation: write to me with any requests for academic accommodation during the first two weeks of class, or as soon as possible after the need for accommodation is known to exist.
• Religious obligation: write to me with any requests for academic accommodation during the first two weeks of class, or as soon as possible after the need for accommodation is known to exist.
• Academic Integrity Statement: Plagiarism and cheating at the graduate level are viewed as being particularly serious and the sanctions imposed are accordingly severe. Students are expected to familiarize themselves with and follow the Carleton University Student Academic Integrity Policy. The Policy is strictly enforced and is binding on all students. Plagiarism and cheating, presenting another's ideas, arguments, words or images as your own, using unauthorized material, misrepresentation, fabricating or misrepresenting research data, unauthorized co-operation or collaboration or completing work for another student, weaken the quality of the graduate degree. Academic dishonesty in any form will not be tolerated. Students who infringe the Policy may be subject to one of several penalties including: expulsion; suspension from all studies at Carleton; suspension from full-time studies; a refusal of permission to continue or to register in a specific degree program; academic probation; or a grade of Failure in the course.

Lecture notes:

• Week1.pdf, week2.pdf, week3.pdf, week4.pdf, week5.pdf, week6.pdf, week7.pdf.
• Two lectures about basic asymptotics: oldasymp1.pdf and oldasymp2.pdf.
• Week8.pdf, week9.pdf, week10.pdf, week11.pdf, week12.pdf.

Lectures per month

• January 2012 (html file)
• February 2012 (html file)
• March 2012 (html file)

Contact Information: