Intro
Let there be a game in which participants are presented with a set of $n$ numbers $x = [x_1, x_2, \dots, x_n]$, a set $O$ containing $k$ arithmetic operators, and a target number $T$. The goal of the game is to find the arithmetic expression that has $T$ as its outcome using all numbers in $X$ once, and only operators in $O$. The well known 24-game items are a subset of items in this game in which the dimensions of all items are fixed to $n = 4$, $O = \{+,-,\times,\div \}$ and $T = 24$.
I use $x$ with character subscript to denote index non-specific numbers and the $\sim$ symbol to denote non-specific operations, such that for $X = [1,2]$ and $O = \{+,-\}$, $(x_a \sim x_b) \in \{(1 + 2), (1 - 2), (2 + 1), (2 - 1)\}$. Whereas there only is a single pattern for $n=2$, for $n = 3$ we see that there exist two base patterns namely, $((x_a \sim x_b) \sim x_c)$ and $(x_c \sim (x_a \sim x_b))$, in which $(x_a \sim x_b)$ denotes an operation on two numbers from the original set, for which the outcome is then used in the operation together with the remaining initial number $x_c$.
The total number of (textually) unique patterns is then given by:
$$n! \times k^{n-1} \times \frac{1}{n} \, \binom{2 \, (n-1)}{(n-1)}$$
So for $n = 3$ and $O = \{+,-,\times,\div \}$ there are for example 192 different patterns.
Clearly, there are however patterns that are different, but will lead to the same outcome, as they are algebraically equivalent. The simplest of these are those in which uses only $+$ or $\times$, e.g.:
$$((x_a + x_b) + x_c) = (x_c + (x_a + x_b)) = ((x_a + x_c) + x_b) = \dots $$
Another equivalency is of course:
$$((x_a \sim x_b) + x_c) = (x_c + (x_a \sim x_b))$$
It gets a bit more complex when we consider:
$$((x_a - x_b) - x_c) = ((x_a - x_c) - x_b) = (x_a - (x_b + x_c))$$
Question
a. Does an expression exists that given $n$ and the set $O$ tells me how many unique expressions exists, i.e., the potential number of unique outcomes? I write potential as the actual number is of course based on the exact contents of $X$, for example, when $X$ contains duplicate numbers, ones, or zeros, the number of unique outcomes will be less compared to when $X$ contains only unique irrational numbers.
For $n = 2$ we would find, for example, that there are eight different patterns, of which 2 pairs have the same outcome, i.e., 6 potentially unique outcomes:
- $(a-b)$
- $(a \div b)$
- $(b-a)$
- $(b \div a)$
- $(a + b) = (b + a)$
- $(a \times b) = (b \times a)$
(for $n = 3$ there is 192 patterns and 68 outcomes, and for $n = 4$ there are 7680 patterns and somewhere around 1170 unique outcomes (numerical approximation))
b. Is there also an expression that tells me the number of algebraically unique expressions, but where the actual numbers used are irrelevant. For example, while $$((x_b - x_a) - x_c) \neq ((x_a - x_b) - x_c)$$ the general pattern of their equivalency relations is the same. $$((x_a - x_b) - x_c) = ((x_a - x_c) - x_b) = (x_a - (x_b + x_c))$$ and $$((x_b - x_a) - x_c) = ((x_b - x_c) - x_a) = (x_b - (x_a + x_c))$$ So although they can lead to different outcomes, and hence would both be counted as +1 for question a, for question b I would want them to only count for one in total.
In the case for $n=2$ we would count 4 patterns for question b:
- $(a-b)$
- $(a \div b)$
- $(a + b) = (b + a)$
- $(a \times b) = (b \times a)$
And in the case of $n=3$ we would count 18 patterns:
$(c \div (a-b))$
$((a-b) \div c)$
$(c-(a \div b))$
$((a \div b)-c) \\$
$((a+b) \div c) = ((b+a) \div c)$
$((a-b) \times c) = (c \times (a-b))$
$((a \times b)-c) = ((b \times a)-c)$
$((a \div b)+c) = (c+(a \div b))$
$(c \div (a+b)) = (c \div (b+a))$
$(c-(a \times b)) = (c-(b \times a)) \\$
$((a+b) \times c) = ((b+a) \times c) = (c \times (a+b)) = (c \times (b+a))$
$((a-b)-c) = ((a-c)-b) = (a-(b+c)) = (a-(c+b))$
$((a \times b)+c) = ((b \times a)+c) = (c+(a \times b)) = (c+(b \times a))$
$((a \div b) \div c) = ((a \div c) \div b) = (a \div (b \times c)) = (a \div (c \times b)) \\$
$((a-b)+c) = ((a+c)-b) = ((c-b)+a) = (a-(b-c)) = \dots $
$((a \times b) \div c) = ((a \div c) \times b) = (a \times (b \div c)) = (a \div (c \div b)) = \dots \\$
$((a+b)+c) = ((a+c)+b) = ((b+a)+c) = \dots$
$((a \times b) \times c) = ((a \times c) \times b) = ((b \times a) \times c) = \dots \\$
Thanks very much for your help.