Motivating example: consider the eight formulas (a+b)*c, (a+c)*b, (b+c)*a, (a*b)+c, (a*c)+b, (b*c)+a, (a+b)+c, (a*b)*c. Each can produce a different output, eg. as when a=5, b=7, c=2 which gives, respectively, 24, 49, 45, 37, 17, 19, 14, 70. There are no other formulas involving *, +, exactly three inputs a, b, c used once each, and parentheses--at least none that will ever produce a value not produced by the above eight. For instance, (b+a)*c is not on the list, but it's not fundamentally different from (a+b)*c because + is commutative. Similarly (a*c)*b is essentially captured by (a*b)*c.

The question is, given a fixed number n of inputs a_1, ..., a_n; two commutative, associative, binary operators (call them + and *); and parentheses, how many fundamentally different formulas can you construct, using each input precisely once? Formulas are considered equal if no matter what the inputs and operators are they always evaluate to the same thing. For instance, a+(b*c) and (a+b)*c are considered different formulas even though 0+(1*2) = 2 = (0+1)*2 since for other inputs they produce different values. Note that (a+b)*c and (a+c)*b are considered different even though they have the same structure since they produce different values for some choices of a, b, and c.

I may post my own workings at some point, or maybe this will languish forever. I do not yet know the answer.