1
$\begingroup$

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.

$\endgroup$
11
  • 3
    $\begingroup$ Probably you want to avoid being equivalent to an invalid arrangement. i.e., $1231\sim 1213$, $1321 \sim 3121$, $3123\sim 1321$ and $3213\sim 3231$ $\endgroup$ – Phicar Oct 27 '20 at 14:49
  • 1
    $\begingroup$ @n.o.: It’s perfectly clear that the equivalence relation is defined on the set of words over $[n-1]$, but that we are considering only those equivalence classes $B$ such that any three consecutive letters of any word in $B$ are distinct. There is no need to go through contortions to define some other equivalence relation. $\endgroup$ – Brian M. Scott Oct 27 '20 at 22:39
  • 1
    $\begingroup$ It is perfectly grammatical to interpret "words in the alphabet [$n-1$] such that any three consecutive letters of any word in $B$ are distinct" as a noun phrase, in which case we are considering the equivalence relation over a subset of all words in the alphabet [$n-1$]. $\endgroup$ – Adrian Clough Oct 28 '20 at 10:01
  • 1
    $\begingroup$ However, if we isolate the noun phrase "equivalence classes $B$ of words in the alphabet [$n-1$] ", which we then further modify by "such that any three consecutive letters of any word in $B$ are distinct" we obtain the interpretation intended by the Stanley, in which case, as Will points out, the difficulty regarding word length disappears. $\endgroup$ – Adrian Clough Oct 28 '20 at 10:01
  • 1
    $\begingroup$ @BrianM.Scott, as Adrian Clough explains, there are two possible readings of the statement, which are both perfectly valid. Thus, writing "it's perfectly clear" is not only impolite, it is untrue. This is the first time I write a question on Math.SE; I had written this question together with a student to show them how to write questions on SE sites, but it is comments such as yours that are making me think twice before recommending this site to students in the future, since they are misleading, and a student might not have enough experience to understand that. $\endgroup$ – n.o. Oct 28 '20 at 10:41
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks for this answer. As I remark in my comment above, one should have formulated the problem by defining an equivalence relation on the set of all words on the alphabet $[𝑛−1]$, and by additionally defining any word having three consecutive entries with repetitions to be equivalent to the empty word. Then clearly one can't have words with length greater than $5$ for $n=4$. $\endgroup$ – n.o. Oct 27 '20 at 22:11
  • $\begingroup$ My reading of Stanley, which I think agrees with Brian Scott's, is that one first considers all equivalence classes of words under Stanley's equivalence relation and then one forms a set by selecting those equivalence classes in which any three consecutive letters, in any word in the equivalence class, are distinct. I'm not sure it's obvious without checking that one cannot have words of length greater than $4$ when $n=4$, but the checking done in my answer seems to suffice to show this. For $n=5$ note that you can have words of length $6$ (such as 231423 ) but not of length $7$ or more. $\endgroup$ – Will Orrick Oct 28 '20 at 3:58
  • 1
    $\begingroup$ Yes, I didn't mean that it's obvious, but it's clear to me why in that case one does not have words of length greater than $4$. My problem was in the set-up of the problem, which I still believe needs to be addressed. As you correctly write, yours is one reading, mine was another possible reading. In the same way that I should not read a proof of a theorem to understand what the theorem states, I should not rely on examples to understand what a problem asks, especially in a textbook that is so widely used. $\endgroup$ – n.o. Oct 28 '20 at 7:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.