Counting

My own background is (mostly) in combinatorics, especially the enumeration of discrete structures on regular lattices. So, my approach to the topics at hand will be very discrete flavoured.

Given a set of discrete structures, $\mathcal{A}$, such as

• words in two symbols — eg $\{0,1\}$
• Dyck paths
• Binary trees
• self-avoiding walks and polygons
• poker-hands
• permutations
• involutions
• knot diagrams
• knot types

the main question I’d like to be able answer is

How many objects are there in $\mathcal{A}$?

Most of the sets I have described are infinite sets, so the above question is boring. Instead we need to grade the sets by some notion of size. This should be a function $$|\cdot| : \mathcal{A} \to \{0\}\cup \mathbb{N}$$

For most of the objects we’ll talk about, this will end up being something like “the number of crossings”, “the number of edges”, “the number of symbols”. We can then grade our original set $\mathcal{A}$ as $$\begin{align} \mathcal{A}_n &= \{a \in \mathcal{A} \mid |a|=n\} & \mathcal{A} &= \bigcup_{n \geq 0} \mathcal{A}_n \end{align}$$

Then the main question becomes

How many objects are there of size $n$?

where (hopefully) the answer is now finite. Lets call it (for the moment) $a_n$.

What is an acceptable answer? This can be quite hard to decide. For example, the (somewhat literal) answer $$\begin{align*} a_n &= \sum_{\varphi \in \mathcal{A}_n} 1 \end{align*}$$ is completely correct, but obviously not much use. It does, however, somehow set a baseline for what is “useful”. I guess we should call the above a “brute force” solution.

In particular, if we think about actually computing the number — the expression above takes time proportional to $a_n$ to compute $a_n$. This is pretty useless, and so anything that might be faster than the above is arguably “useful”. Of course there are exceptions to this — for example, if we have an expression that is useless for computing the numbers, but can tell us other properties (eg the asymptotics of the numbers), then it might still be “useful” and perhaps even more useful than being able to compute $a_n$ quickly.

Anyway — what we’d really like is an explicit expression for $a_n$ that is quick to compute. For example $$\begin{align*} a_n &= \frac{1}{n+1} \binom{2n}{n} \end{align*}$$ To compute $a_n$ we need to do $O(n)$ operations.

We might also be happy with a more implicit expression like a generating function $$\begin{align*} \sum_{n \geq 0} a_n z^n &= \frac{1-\sqrt{1-4z}}{2z} \end{align*}$$ This can be expanded in polynomial time, and it also contains useful information about the asymptotics of the coefficients $a_n$ - the interested reader should take a look at the topic of “analytic combinatorics” and the wonderful text of Flajolet & Sedgewick.

We might also be happy with a recurrence: $$\begin{align*} (n+2) \cdot a_{n+1} &= (4n+2) \cdot a_n & a_0=1 \end{align*}$$ which we can iterate in polynomial time to find $a_n$. We can also use such linear recurrences (with polynomial coefficients) to extract information about the asymptotic growth of $a_n$.

For some problems finding such expressions is pretty easy

• words in two symbols — $a_n = 2^n$
• Dyck paths — $a_n = \frac{1}{n+1}\binom{2n}{n}$
• Binary trees — $a_n = \frac{1}{n+1}\binom{2n}{n}$
• permutations — $a_n = n!$
• involutions — $a_n = a_{n-1} + (n-1) a_{n-2}$ or $\sum a_n z^n/n! = \exp(z+z^2/2)$

but far too frequently they are just too damn hard and no such nice expression is known — nor any useful implicit expression

• self-avoiding walks and polygons
• knot diagrams
• knot types

And — of course — as “luck” would have it, these are precisely the sort of objects that we are interested in.

So why can’t we just use the brute force solution?