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.