$S$-words (also called $S$-sequences) are of importance in the theory of $n$-ary structures. In this paper it is proved that the number of different $S$-words of the length $n$ is the $(n-1)$-th Catalan number. A simple way of generating all the different $S$-words of the length $n$ is given. Also an algorithm is given for the recognition of $S$-words. The complexity of this algorithm is $O(n)$, where $n$ is the length of the word.