Question 96
Given a set $S$ of $n$ variables, a binary operation $\times$ on $S$ is called *simple* if it satisfies $(x \times y) \times z = x \times (y \times z)$ for all $x, y, z \in S$ and $x \times y \in \{x, y\}$ for all $x, y \in S$. Given a simple operation $\times$ on $S$, any string of elements in $S$ can be reduced to a single element, such as $xyz \rightarrow x \times (y \times z)$. A string of variables in $S$ is called *full* if it contains each variable in $S$ at least once, and two strings are *equivalent* if they evaluate to the same variable regardless of which simple $\times$ is chosen. For example, $xxx$, $xx$, and $x$ are equivalent, but these are only full if $n = 1$. Suppose $T$ is a set of strings such that any full string is equivalent to exactly one element of $T$. Determine the number of elements of $T$.
(This problem was suggested by John Berman.)
(This problem was suggested by John Berman.)