Problem 1923

Solution 1. The answer is $n!^2$.
We use $s_1 \sim s_2$ to denote that strings $s_1$ and $s_2$ are equivalent. If $x_1x_2 \cdots x_k$ is any string in $S$, we can see that
$$x_1x_2\cdots x_kx_1x_2\cdots x_k = (x_1\cdots x_k)(x_1\cdots x_k) \sim x_1\cdots x_k$$
because $xx \in \{x\}$. But also, if $a_1a_2 \cdots a_i, b_1b_2 \cdots b_j$ are strings in $S$ and $x \in S$, then
$$xa_1a_2 \cdots a_ixb_1b_2 \cdots b_jx \sim xa_1a_2 \cdots a_ib_1b_2 \cdots b_jx$$
To prove this, it suffices to show that $xaxbx \sim xabx$. Suppose that for some $\times$, these did not evaluate to the same element of $S$. Then $a \times x = x$, since otherwise $x(a \times x)bx = xabx$. Similarly, $x \times b = x$. This means that
$$xaxbx = x(a \times x)bx = xxbx = x(x \times b)x = xxx = x$$
so by assumption $xabx \neq x$. But if $xabx = a$, then in particular $xa = a$, $ab = a$, and $ax = a$ all must hold, the latter of which is a contradiction. Similarly if $xabx = b$ we reach a contradiction. Thus this equivalence holds.
Given any full string $w = x_1x_2 \cdots x_k$, we claim that it is equivalent to some string consisting of two concatenated permutations of $S$, i.e. $\sigma_1\sigma_2$ where $\sigma_1$ is a permutation of the $n$ variables of $S$ and $\sigma_2$ is also. Note that $w \sim ww = x_1x_2 \cdots x_kx_1x_2 \cdots x_k$. This string may be reduced by our second observation above so that in any case where an element $y$ appears more than two times, all but the outermost instances of $y$ are removed. Because $w$ was full, the new string $\tilde{w} \sim w$ will have each element of $S$ occurring exactly twice. But the first occurrences of each variable all occur in the first instance of $w$, and the last occurrences all occur in the second instance of $w$ (in $ww$), so $\tilde{w}$ consists of two concatenated permutations of $S$, of which there are $n!^2$ possibilities.
It remains to show that two double-permutations $\sigma_1\sigma_2$ and $\sigma'_1\sigma'_2$ are not equivalent. Suppose otherwise. Without loss of generality we may assume that $\sigma_1 \neq \sigma'_1$; otherwise we reverse the order of the operation $\times$ found below. Choose two elements $a, b$ such that $a$ occurs before $b$ in $\sigma_1$ but their order is reversed in $\sigma'_1$. Then choose some operation $\times$ such that for any $x, y \in S$,
$$x \times y = \begin{cases} y & \text{if } x \notin \{a, b\}, y \in \{a, b\}, \\ x & \text{otherwise.} \end{cases}$$
This operation clearly satisfies $x \times y \in \{x, y\}$, and some easy casework on which of $x, y, z$ are in $\{a, b\}$ shows that $(x \times y) \times z = x \times (y \times z)$ for all $x, y, z \in S$. Hence, the operation is simple. Furthermore $\sigma_1\sigma_2$ evaluates to $a$ under this operation, while $\sigma'_1\sigma'_2$ evaluates to $b$. We conclude that the two strings are not equivalent, finishing the solution.

Solution 2 (Based on an idea of Alex Zhai). Given an operation $\times$, construct a complete directed graph $G(\times)$ with $n$ vertices, each vertex corresponding to a variable of $S$. Construct an edge marked $L$ going from $u$ to $v$ if $u \times v = u$, and an edge marked $R$ from $v$ to $u$ if $u \times v = v$. In this way each pair of vertices will have two edges between them, either both going in the same direction or both having the same marking.
Suppose we have an edge from $x$ to $y$ marked $a$ and an edge from $y$ to $z$ marked $b$. Through some simple casework on $a, b$ and use of the associative condition on $\times$, we can verify this implies there is an edge from $x$ to $z$ marked $a$. Call this the *associativity condition* on $G(\times)$.
Now suppose two vertices $u, v$ are such that there are two edges from $u$ to $v$, one $L$ and one $R$. We claim this means there is no path from $v$ to $u$. Suppose that $v, w_1, w_2, \dots, w_k, u$ were such a path. Then the associativity condition on $u, v, w_1$ means that $u$ has two edges marked $L$ and $R$ from $u$ to $w_1$. Through the same methods we can inductively show that the two edges between $u$ to $w_i$ are directed away from $u$ for all $i$. But we need an edge from $w_k$ to $u$, so this is a contradiction.
Consider the strongly connected components of $G(\times)$, meaning components such that a pair of vertices $u, v$ has a path from $u$ to $v$ and a path from $v$ to $u$ if and only if $u, v$ are in the same component. The above paragraph implies that for any $u, v$ in the same component, the two edges between $u, v$ go in opposite directions and have the same marking. The associativity condition implies the markings between all pairs of vertices in the same component are equal, so we can consider each component to be either $L$ as a whole or $R$ as a whole.
Let $C_1$ be the component such that no other component has an edge going into $C_1$, and call this the top component of $G(\times)$. Then by the way we have constructed the graph, any full expression evaluates to a variable corresponding to a vertex in $C_1$ under $\times$. Since all the edges in $C_1$ are either $L$ or $R$, the value of the full expression is either the leftmost variable out of those appearing in $C_1$, or the rightmost variable. In this way, we have completely characterized how a full expression can be evaluated under a simple operation $\times$: take a nonempty subset $T$ of the variables, then $\times$ evaluates the expression to either the leftmost occurrence of a variable in $T$, or the rightmost occurrence of a variable in $T$.
From here the problem is straightforward to finish. Given a full expression $w$, consider only the leftmost occurrence of each variable in $w$. This gives a permutation $\sigma_L$ of the variables of $S$. Similarly construct $\sigma_R$ from the rightmost occurrence of each variable in $w$. By our above characterization $w$ is equivalent to $\sigma_L\sigma_R$, and there are $n!^2$ ways to make a word from appending two permutations. Finally, suppose we have a different appending $\sigma'_L\sigma'_R$ (without loss of generality we may assume that $\sigma_L \neq \sigma'_L$). We have some pair $a, b$ such that $a$ appears to the left of $b$ in $\sigma_L$ but their order is reversed in $\sigma'_L$. Then we can construct $\times$ such that $a, b$ are the only two elements of the top component marked $L$ of $G(\times)$. This operation gives $\sigma_L\sigma_R = a$ and $\sigma'_L\sigma'_R = b$, so the two are not equivalent.