# Combinatorics of term algebras

My question is about the number of terms of size $n$ in term algebras for an arbitrary (finite) signature.

A signature is a map $\Sigma : S \rightarrow \mathbb{N}$ from a set $S$ of symbols. We assume $S$ to be finite, and $\mathbb{N}$ to contain 0. If $\Sigma(f) = n$ we say that $f$ has arity $n$. We call symbols with arity 0 constants.

Here are some examples of signatures.

• $\Sigma_G$, the signature of groups, is based on symbols $+, -$ and $0$ with the following arities. $\Sigma_G(+) = 2$, $\Sigma_G(-) = 1$, and $\Sigma_G(e) = 0$.
• $\Sigma_L$, the signature of bounded lattices, has symbols $\vee$, $\wedge$, $0$ and $1$, with arities $\Sigma_L(\vee) = 2$, $\Sigma_L(\wedge) = 2$, $\Sigma_L(0) = 0$ and $\Sigma_L(1) = 0$.
• $\Sigma_F$, the signature of fields, has symbols $+, -, 0, \cdot, ^{-1}$ and $1$, with arities $\Sigma_F(+) = 2$, $\Sigma_F(\cdot) = 2$, $\Sigma_F(-) = 1$, and $\Sigma_F(-) = 1$, $\Sigma_F(0) = 0$ and $\Sigma_F(1) = 0$.

The term-algebra over a variable set $X$ is denoted $\Sigma(X)$. It is generated inductively by the following rules.

• If $x \in X$, then $x$ is a member of $\Sigma(X)$.
• If $f \in \Sigma(n)$ and $t_1, ..., t_n \in \Sigma(X)$, then also $f(t_1, ..., t_n) \in \Sigma(X)$.

Examples of terms in the term algebra $\Sigma_G(\{x, y, z\})$ of groups include $-(x+(y + z))$ and $-0$. These are also terms of $\Sigma_F(\{x, y, z\})$. The term $0 \wedge (1 \vee 0)$ is in $\Sigma_L(\emptyset)$.

We can define the usual notion of size of terms as follows. $$\mathsf{size}(f(t_1, ..., t_n)) = 1 + \sum_{i=1}^n \mathsf{size}(t_i) \qquad\qquad \mathsf{size}(c) = 1$$ Here $c$ ranges over the constants in $\Sigma$, and $f \in \Sigma(n)$.

With this notion of size, $0 \wedge (1 \vee 0)$ for example has size 5, while $-0$ has size 2.

Now we can ask questions like: how many elements of size $n$ does the term algebra $\Sigma(\emptyset)$ contain?

Consider a signature $\Sigma$ with symbols $\{+, 0\}$ such that $\Sigma(+) = 2$ and $\Sigma(0) = 0$. Let $C'_n$ be the number of terms in $\Sigma(\emptyset)$ of size $n$. The sequence $C'_n$ begins as follows. $$0, 1, 0, 1, 0, 2, 0, 5, 0, 14, 0, 42, 0, 132, 0, 429, 0, 1430, 0, 4862$$ The non-zero subsequence corresponds exactly to the Catalan numbers $C_n$ that are defined by the following recursive equation. $$C_0 = 1 \qquad\qquad C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}$$

The sequence of numbers of terms in $\Sigma_G(\emptyset)$, term algebra of groups with no variables begins with the following numbers. $$0, 1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634$$

It's not too difficult to work out the recursive equation giving the number of terms of size $n$ for arbitrary signatures (it's a generalisation of the recursion for Catalan numbers, using integer partitions).

Question. Surely this counting problem must have been investigated, but my googling has fail to locate anything relevant. I'd be delighted to learn about books or papers that consider this problem. I'm especially interested in closed forms, should they exist and approximations.

-
This question doesn't really seem to involve universal algebra in an essential way, so can you rephrase it in a way that doesn't require that we already know what a signature, term algebra, etc. are? (I just mean, for example, adding definitions of all of these things.) – Qiaochu Yuan Oct 4 '11 at 18:16
Hello Qiaochu, thanks for your suggestion. I've added definitions and examples. I hope the question is more understandable now. – Martin Berger Oct 5 '11 at 11:16
Thanks. I understand the question now, but I don't think your definition of size agrees with your examples. It seems to me that $0 \wedge (1 \vee 0)$ should have size $3$ according to it. – Qiaochu Yuan Oct 5 '11 at 15:24
Sorry, I forgot to add a "1 +" in the recursive definition of size. Now fixed. All size is supposed to measure is the number of symbols from the signature in the term. – Martin Berger Oct 5 '11 at 16:10

Let me describe a reformulation of the problem in language more familiar to me. The question is to count the number of (rooted, planar) trees with $n$ nodes (this agrees with your examples about size but not with your definition) with the following properties:

• Each node is labeled by an element of $S$.
• If a node is labeled by $s \in S$, then it has $\Sigma(s)$ children.

Let $t_n$ denote the number of such trees. The key to understanding this question is to use generating functions, and instead of just studying the sequence $t_n$ we study the function $$T(z) = \sum_{n \ge 0} t_n z^n.$$

The recursive definition of terms leads to a relation satisfied by $T$. More precisely, let $s_i$ be the number of symbols with arity $i$. Then I claim that $$T = z \sum_{i \ge 0} s_i T^i.$$

This relation can be understood combinatorially as follows: we split up the set of trees based on the arity of their roots. If the arity is $i$, then the tree consists of one of $s_i$ possible roots together with $i$ other trees of the same form. Expanding out the above gives a recursion for $t_n$, but it's cleaner to work directly with the above instead.

In your example we have $s_0 = s_2 = 1$ and all other terms equal to zero, giving $$T = z (1 + T^2) \Rightarrow T = \frac{1 - \sqrt{1 - 4z^2}}{2z}$$

which is one of the generating functions of the Catalan numbers. In general, by Lagrange inversion we have $$t_n = \frac{1}{n} [w^n] \left( \sum s_i w^i \right)^n$$

where $[w^n]$ denotes the coefficient of $w^n$.

N.B.: It is not necessary for $S$ to be finite; the only condition for this problem to have an answer is that there are only finitely many symbols of a given arity and at least one symbol of arity $0$. For example, consider the case in which $s_i = 1$ for all $i$. This gives $$T = z(1 + T + T^2 + ...) = \frac{z}{1 - T} \Rightarrow T - T^2 = z \Rightarrow T = \frac{1 - \sqrt{1 - 4z}}{2}$$

which is another generating function for the Catalan numbers.

Some suggestions for further reading, roughly in order of difficulty:

One last comment. It may not be obvious how to prove rigorously that the coefficients of $T$ are uniquely determined by a relation of the form $T = z \sum s_i T^i$. One can do this by induction, but the cleanest way I know how to do this is to appeal to the Banach fixed point theorem. $T$ is a fixed point of the map $$f \mapsto z \sum s_i f^i$$

acting on the space of formal power series $\mathbb{R}[[z]]$. This space is equipped with a norm $$|f| = 2^{-n}$$

where $f = a_n x^n + \text{higher terms}$ and $a_n \neq 0$, and in fact it is complete relative to the induced metric (exercise). The map $f \mapsto z \sum s_i f^i$ is a contraction, so it has a unique fixed point. In fact this proof is completely constructive: starting with any initial $T_0$, we can consider the sequence $$T_n = z \sum s_i T_{n-1}^i$$

and this sequence of power series will converge to $T$ in the sense that the coefficients will stabilize to the coefficients of $T$. Starting with $T_0 = 0$ this corresponds to counting trees of the above form, but of bounded depth.

-
Thanks for the explanation. I agree that looking at term algebras as labelled trees is possible, with one slight caveat: you'll need to look at edge-ordered labelled trees because, e.g. 2+3 is in general different from 3+2, and so you'd want to count them as two rather than as one. – Martin Berger Oct 6 '11 at 10:32
@Martin: yes, that's what "planar" means (the trees are drawn on a plane, so the leaves of each node have an order to them). – Qiaochu Yuan Oct 6 '11 at 13:06
Shouldn't that second dot point be: "then it has $\Sigma(s)$ children"? – goblin Oct 12 '15 at 0:16
@goblin: yeah, sure, I guess that's a better term. – Qiaochu Yuan Oct 12 '15 at 0:30