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 2009 (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
  Snake oil method; cycle index; introduction to asymptotics	2
  Test	0.5
  Lagrange inversion; complex asymptotics; singularity analysis	3
  Total	12

• Prerequisites: A combinatorics course equivalent to MATH 3805, or permission of the School.
• Classes begin: Tuesday January 5, 2010.
  Classes end: Tuesday April 1, 2010.
  
• Term mark: There will be three assignments. The tentative schedule of assignments is:

  Assignment	Hand-out Date	Due Date	Worth
  1	January 19	February 9	10%
  2	February 9	March 9	10%
  3	March 9	March 30	10%

  In addition to the assignments, there is a midterm test on Thursday March 4, 2010, and a final exam. To pass the PhD comprehensive in Combinatorial Enumeration a student needs at least 70% in the final exam.

• Evaluation:

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

• Withdrawal: The last day for withdrawal from the course is March 12, 2010.
• 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.

  For more general accommodation requests, see: http://www.carleton.ca/equity/accommodation/outlines.htm.

• 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; see http://www2.carleton.ca/graduate-studies/policies-and-guidelines 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 (these classes were given before, one in week 4 and one in week 6);
  two lectures about basic asymptotics: oldasymp1.pdf and oldasymp2.pdf;
  week8_9.pdf, week10.pdf, week11.pdf, week12.pdf.

Lectures per month

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

Contact Information: