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. 
 A: 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: 


*

*Wilf's generatingfunctionology (freely available online)

*Flajolet and Sedgewick's Analytic Combinatorics (also freely available online)

*Stanley's Enumerative Combinatorics, Vol. II

*Bergeron, Labelle, and Leroux's Combinatorial Species and Tree-like Structures
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. 
