# 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.

• These expressions might look slightly simpler if we choose to use infix notation. For example, we could write $x+y = f(x,y)$, and $x\# y = g(x,y)$. Then for instance $f(g(x_3, x_2), x_1)$ becomes $(x_3\# x_2) + x_1$. If we remember that $+$ and $\#$ are commutative and associative, then it's easy to see that $(x_3 \# x_2) + x_1 = x_1 + (x_2 \# x_3)$, which is the second equivalence you mentioned. So this notation could help to improve readability, at least for some people. (Granted, it'll be harder to make this work for the more general question with $k$ binary operations.) – mathmandan Jan 31 '15 at 17:48
• @mathmandan even simpler would be to combine all function applications of the same function and order the arguments by the lowest index appearing in it, e.g. $f(x_1,x_2,x_3)$ or $f(x_1,g(x_2,x_4),x_3)$ - note: a binary, associative function can be extended to a function with more arguments in a natural way. And by ordering the arguments we take care of commutativity, thus having a simple normalized represenation for the expressions. – coproc Jan 31 '15 at 19:18

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$.
• don't we need $p_{m_i}^d_i$ in the numerator of the sum term? – coproc Jan 31 '15 at 20:39
• I guess the prediction for $e_5$ has to be updated also ... (up to $e_4$ the missing exponent does not matter, I think) – coproc Feb 1 '15 at 10:30
• The result $e_5=472$ seems to be correct. And indeed: the first time the exponents $d_i$ make a difference is with $p_{m_1} > 1$ and $d_i > 1$, hende $m_1=3, d_1=2$ and therefore $n = 2*3 = 6$. – coproc Feb 1 '15 at 12:34