I have a question about the statement of problem (aa) in Stanley's list of problems on Catalan numbers (see here), in which he lists 66 sets whose elements are counted by the $n$th Catalan number $C_n$.
The statement seems to be imprecise, or incomplete. I am copying it here for ease of reference:
[We consider] equivalence classes $B$ of words in the alphabet [$n-1$] such that any three consecutive letters of any word in $B$ are distinct, under the equivalence relation $uijv \sim ujiv$ for any words, $u, v$ and any $i, j \in$ [$n-1$] satisfying $|i-j|\geq 2$. For $n=3$, equivalence classes are {$\varnothing$}, {1}, {2}, {12}, {21}. For $n=4$ a representative of each class is given by $\varnothing$, 1, 2, 3, 12, 21, 13, 23, 32, 123, 132, 213, 321, 2132.
Now, while this is not stated, we are clearly interested in the smallest equivalence relation containing those ordered pairs. Furthermore, it seems that we are only considering words of length at most $n$. Even taking into account this, it is still not clear to me why for $n=4$ we only have one equivalence class for words of length $4$. For instance why, in addition to $[2132]$, do we not also have the four pairwise distinct equivalence classes $[1231], [1321], [3123], [3213]$?
For example, let's consider $[1231]$. Then $1231$ is not equivalent to $1321$, since we are only considering permutations of pairs $ij$ with $|i-j|\geq 2$. In particular, it seems that $1231$ is not equivalent to any other word such that any three consecutive letters are all distinct.
Please note that I am not asking for a solution to the counting problem, but simply trying to understand the statement. Since these problems are quite well-known and used in many combinatorics classes, I am a bit surprised at the fact that the statement appears to be so imprecise.
I think that if any word in the equivalence class is an invalid word, then all words in the equivalence class are invalid. So 1231 is invalid since it's equivalent to 1213, which is invalid. For $n=4$ you cannot have a word of length $5$ or greater. This is not an additional assumption, but follows from the constraint. To see this, note that the middle three letters in a five letter word cannot all be 2s. Any 3 in the interior of the word must either be preceded or succeed by a 1. Likewise any 1 must be preceded or succeeded by a 3. In either casethe surrounding letters are forced to both be 2s, giving either 2132 or 2312 (which are equivalent). Any letter preceding or succeeding this word must be a 1 or 3, but both are impossible.