Question 8
A word is a sequence of zero or more letters taken from the set $\{A,B,C,D,E,F,G,H,I\}$. Two words are said to be related if one can be obtained from the other by a sequence of the following operations:
(a) swapping two adjacent letters,
(b) deleting two adjacent letters which are the same,
(c) inserting two adjacent letters which are the same.
Thus, for instance, BACA and BCAA are related by swapping adjacent letters A and C, and BCAA is related to BC by deleting or inserting two adjacent letter As. Note that the empty word with zero letters is related to any word consisting of just two adjacent letters.
What is the maximum number of words in a set in which no word is related to any other?
Numerical answer only; a non-negative integer less than 1000.
(a) swapping two adjacent letters,
(b) deleting two adjacent letters which are the same,
(c) inserting two adjacent letters which are the same.
Thus, for instance, BACA and BCAA are related by swapping adjacent letters A and C, and BCAA is related to BC by deleting or inserting two adjacent letter As. Note that the empty word with zero letters is related to any word consisting of just two adjacent letters.
What is the maximum number of words in a set in which no word is related to any other?
Numerical answer only; a non-negative integer less than 1000.