Introduction

An Invitation to Enumeration #

Figure: Image from Essay d’analyse sur les jeux de hazard (Analysis of games of chance) by P. R. de Montmort (1708)

This website contains the notes An Invitation to Enumeration by Stephen Melczer, written for enumeration courses at the University of Waterloo.

These notes provide an introduction to enumerative combinatorics. They are suitable for undergraduate students in combinatorics, mathematics, and computer science – ideally (but not strictly necessarily) those who have already taken a first course in combinatorics.

If you read these notes on a phone or other small screen, I highly recommend tilting your device sideways so the math formulas don’t run off the page and require horizontal scrolling.

Computer Algebra Software #

Effective computation forms an integral part of modern combinatorics. These notes mainly use the open-source Sage computer algebra system, which is available for download on its website or through the online browser-based CoCalc service. Knowledge of Sage is not required to follow these notes, but being able to play around with the code snippets provided can greatly increase understanding.

An introduction to Sage for beginners can be viewed as a static HTML file here or downloaded as a Jupyter notebook here. See also the Sage Tutorial and the excellent textbook Computational Mathematics with SageMath by Zimmermann and 15 coauthors.

Occasionally, these notes might reference software packages for other computer algebra systems, like Maple, MAGMA, and Mathematica. These computer algebra systems are not open source, but many educational institutions provide free access to some or all of them.

Licenses and Citation #

This website was created with Hugo, using a modification of the Hugo Book theme (license) with Bootstrap (license) and math rendering through KaTeX (license).

Please use the citation An Invitation to Enumeration (enumeration.ca) by Stephen Melczer, 2024 to refer to these notes.

Notation #

These notes use notation commonly found in other mathematics books, including

  • $\mathbb{N}$ for the natural numbers $0,1,2,\dots$ including zero.

  • $\mathbb{Z}$ for the integers.

  • $\mathbb{Q}$ for the rational numbers.

  • $\mathbb{C}$ for the complex numbers.

  • The notation $x \in S$ to say $x$ is an element of the set $S.$

  • The factorial $n! = n(n-1)\cdots(3)(2)(1)$ for $n\in\mathbb{N}.$

  • The binomial coefficient $$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$ when $n,k \in \mathbb{N}$ and $n \geq k.$ As explained in the text, we extend this to all $n \in \mathbb{C}$ and $k \in \mathbb{N}$ by defining $$\binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k!}.$$

  • The set notation $[n] = \{1,2,\dots,n\}$.

Other References #

Our treatment of LIFT, $q$-analogues, partitions, and some of the exercises in Parts 1 and 2 of these notes are based on David G. Wagner’s CO 330 Course Notes and past offerings of CO 330 by instructors at Waterloo (including David Wagner, Karen Yeats, Kevin Purbhoo, and Ian Goulden). Our treatment of the symbolic method and combinatorial constructions follows Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick. Other sources covering the topics we discuss include

Nothing delays more the advancement of the Sciences, and puts a greater obstacle to the discovery of hidden truths, than the mistrust in which we have of our strengths. The greater part of those things which may appear impossible are only so for lack of allowing the human intellect all the extent that it can achieve.

— Pierre Remond de Montmort

Click here for the next chapter