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.