TSTST 2012 Problem 9

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 $x y z \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 $x x x, x x$, and $x$ are equivalent, but these are only full if $n=1$. Suppose $T$ is a set of full strings such that any full string is equivalent to exactly one element of $T$. Determine the number of elements of $T$.