How many answers can be created using the elementary arithmetic operators?

Question

If I gave you an amount of $n$ numbers, how many anwswer will you be able to create using the elementary arithmetic operators ($+, -, \times, /$)?

These are the rules:

• All numbers $\in\mathbb{Q}_{0>}$.
• All numbers are different ($a\neq b \neq c \neq \cdots$).
• All numbers in the answer must be used and can only be used once.
• An operator can be used several times or zero times.
• Use of parentheses is allowed.

Lets's have a look at some examples:

We have 2 numbers called $a$ and $b$;

1. $a + b$ or $b+a$
2. $a-b$
3. $b-a$
4. $b\times a$ or $a\times b$
5. $b/a$
6. $a/b$

Not allowed:

• $a\times a+b$

We have 3 numbers called $a, b$ and $c$;

1. $a+b+c$ or ...
2. $a\times b\times c$ or ...
3. $a-b-c$
4. $(a+b)\times c$
5. $(a/b)/c$
6. etc..

Please edit if necessary!

Answer 1

If we ignore all "coincidences", including associativity and commutativity where it applies, we can enumerate all valid exprsssions by

• arranging the $n$ numbers in one of $n!$ orders
• insertingof parentheses among them in $C(n-1)$$=\frac{(2n-2)!}{(n-1)!n!}$ ways
• inserting operators among the subexpressions in $4^{n-1}$ ways

That gives us a total of $$\tag1\frac{4^{n-1}(2n-2)!}{(n-1)!} $$ expressions.

If one wants to regard commutativity, each occurance of $+$ or $\times$ leads to double-counting, that is: For each $k$, $0\le k\le n-1$, the number $\frac{2^{n-1}(2n-2)!}{(n-1)!}{n-1\choose k}$ expressions with $k$ commutative operators should be divided by $2^k$. This give us $$\tag2\begin{align}\sum_{k=0}^{n-1} 2^{-k}\frac{2^{n-1}(2n-2)!}{(n-1)!}{n-1\choose k}&=\frac{2^{n-1}(2n-2)!}{(n-1)!}\left(1+\frac12\right)^{n-1}\\&=\frac{3^{n-1}(2n-2)!}{(n-1)!}.\end{align}$$ The next goal would be to fully regard associativity. However it doesn't lend itself to simple investigations; one should leave the realm of binary trees and instead consider trees of arbitrary degree with twocoloured edges and I have no idea how to count these efficiently.