Combinatorial Enumeration

Current announcements

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

• The course is over.

General Information

This course covers basic fundamental counting techniques for combinatorics. The first part of the course deals with ordinary and exponential generating functions and their applications to permutations, partitions, rooted trees, etc. We also focus on multivariate generating functions and computation of moments. Then, we give an introduction to hypergeometric functions and the Wilf-Zeilberger method. The cycle index of the symmetric group is also presented. The rest of the course is centered around asymptotics. We briefly comment on real asymptotics, Lagrange inversion formula and singularity analysis of generating functions. If time allows, we finish with an introduction to a selected topic from one of the following areas: random graphs, random combinatorial structures, hypergeometric functions.

• The general information handout for the course is in text format.
• The tentative lecture schedule per month, as of August 2004 (before classes start) is below.
  The actual material covered in each lecture will be updated below ("Lectures per month").

  Topic	Approx. # of weeks
  Introduction; ordinary generating functions	2.5
  Exponential generating functions	1.5
  Multivariate generating functions	2
  WZ method; cycle index	2.5
  Test	0.5
  Asymptotics; Lagrange inversion; singularity analysis	3
  Hypergeometric functions or random structures	0.5
  Total	12.5

• Prerequisites: A combinatorics course equivalent to MATH 3805, or permission of the School.
• Classes begin: Thursday September 9, 2004.
  Classes end: Thursday December 2, 2004.
  
• Term mark: There will be three assignments. The tentative schedule of assignments is:

  Assignment	Hand-out Date	Due Date	Worth
  1	September 23	October 14	10%
  2	October 14	November 4	10%
  3	November 4	November 25	10%

  In addition to the assignments, there is a midterm test on Thursday October 21, 2004, and a final exam.

  The deadlines for assignments are not firm. Work handed-in some days after the deadline will carry no penalties. However, the student must agree with the lecturer on a new deadline for the work.

• 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 November 5, 2004.
• Students with Disabilities: Students with Disabilities who require academic accommodations please feel free to see me, and contact the Paul Menton Centre to complete the required forms.

Textbooks

We will use Herb Wilf 's Generatingfunctionology (you can download it for free!).

We will also use material from the coming book:

• P. Flajolet and R. Sedgewick, "Analytic Combinatorics", Addison-Wesley, Reading, MA, in preparation.

Some chapters of this book are available as technical reports at Philippe Flajolet's webpage. In particular, we will extensively use the first two issues of the book:

• Counting and Generating Functions
• Complex Asymptotics and Generating Functions

• An Introduction to the Analysis of Algorithms by Robert Sedgewick and Philippe Flajolet.
• Concrete Mathematics by Ron Graham, Don Knuth, and Oren Patashnik.

Lectures per month

• September 2004 (html file)
• October 2004 (html file)
• November 2004 (html file)

Contact Information: