0
$\begingroup$

I'm currently working through Analytic Combinatorics (free online) and i'm stuck at a very interesting example. After introducing some admissible constructions (combinatorial sum, cartesian product, sequence, powerset, multiset) and talking about how to define structures recursively, there's an example I can't really wrap my head around.

Here's the part i don't understand (page 35 in the pdf):

page36 page37

The book uses $\{\epsilon\}$ to denote the neutral class consisting of a single element of size zero. Could someone explain how this fits into the recursive definition? Without the term $\{\epsilon\}$ it would have made sense to me.

Thanks a lot!

1 Answers 1

1

If you had $\mathcal{T}=\mathcal{T}\times\nabla\times\mathcal{T}$, every triangulation would have to contain a triangle. Using the iterative interpretation of the recursive definition discussed on page 32, you’d have $\mathcal{T}^{[0]}=\varnothing$, $\mathcal{T}^{[1]}=\{\nabla\}$, $\mathcal{T}^{[2]}=\{\nabla+\nabla+\nabla\}$, and so on, with no way to get the triangulation of a square. Including the $\{\epsilon\}$ term allows you to get things like $\epsilon+\nabla+\nabla$ in $\mathcal{T}^{[2]}$, which gives you the triangulation of a square. This is what they’re getting at in the parenthetical remark in this sentence:

Then, a triangulation decomposes into its root triangle and two subtriangulations (that may well be “empty”) appearing on the left and right sides of the root triangle; ...

The $\{\epsilon\}$ term allows for those empty subtriangulations.