How many expressions can be formed with two commutative and associative functions? 
EDIT: I have posted a generalization of this question to MathOverflow here.

Suppose we have two binary functions $f,g$ which are commutative and associative, i.e., satisfying
$$ f(a,b) = f(b,a) \qquad g(a,b) = g(b,a)$$
$$ f(a,f(b,c)) = f(f(a,b),c) \qquad g(a,g(b,c)) = g(g(a,b),c)$$
for all $a,b,c$. If we have $n$ indeterminates $x_1, x_2, \ldots, x_n$, what is the number $a_n$ of distinct expressions can we produce using $f,g$ and one of each indeterminate?
For example, in the case $n=3$, the expressions $f(x_1, f(x_2, x_3))$ and $f(x_1, g(x_2, x_3))$ are clearly distinct. However, $f(f(x_2, x_1), x_3)$ is equivalent to the first, and $f(g(x_3, x_2), x_1)$ is equivalent to the second.
Using a simple brute force search, the first few terms of the sequence $(a_n)$  are
$$1, 2, 8, 52, \ldots$$
which correspond to several sequences in OEIS.
 A: Here's a recurrence relation for your problem, for what it's worth. As mentioned in the comments, I visualize these expressions as in-fix combinations of two operations, say summation and multiplication. So, each expression is either a sum of products of sums of products (etc.) or a product of sums of products of sums (etc.). To quantify this, let $e_n$ be the number of expressions in $n$ variables that can be made from summation and multiplication and one of each variable; $s_n$ is the portion of the $e_n$ that are sums (i.e., $p_1+\dots+p_k$ for some $k$ where each $p_i$ is a product) and $p_n$ is the portion of the $e_n$ that are products (i.e., $s_1\times\dots\times s_k$ for some $k$ where each $s_i$ is a sum). Then, $e_1=s_1=p_1=1$, and $e_n=s_n+p_n$ for each $n>1$, and by symmetry $s_n=p_n$. Now imagine a sum of $k$ products, where the $i^{\text{th}}$ product has $n_i$ variables. Then, since each variable is used only once $n_1+\dots+n_k=n$. The variables in these products can be arranged in $\binom n{n_1,\dots,n_k}$ ways. By commutativity and associativity we can arrange the products in increasing order of variables, so that $n_1\le \dots\le n_k$. Also because of commutativity, products with the same number of variables can be rearranged with any permutation. So, let $m_1<\dots< m_\ell$ be the strictly increasing sequence of the distinct $n_i$'s, and let $d_i$ be the multiplicity that each $m_i$ appears in $n_1,\dots, n_k$. So, $d_1 m_1+\dots+d_\ell m_\ell=n$. This gives the recurrence relation
$$s_n=\sum_{k\ge 2}\sum\binom n{n_1\dots n_k}\frac{(p_{m_1})^{d_1}\cdots (p_{m_l})^{d_\ell}}{d_1!\cdots d_\ell!},$$
where the inner sum ranges over the $n_i,\ m_i,\ d_i$ variables as just described.
This recurrence relation agrees with the values $1,2,8,52$ which you obtained by "brute force". (In fact, maybe you did the exact same thing to obtain these values.) It also predicts 472 for $e_5$.
The obvious next question is if it's possible to get an explicit solution for the recurrence relation. At this point, I honestly don't know. However, it seems like the setting where the exponential formula should come into play.
