Enumerating totally clean words (Q1109033): Difference between revisions

Let A be a finite alphabet. To every letter \(a\in A\) we assign the weight \(\chi_ a\) and the weight of a word is the product of the weights of its letters. The weight of a set S of words is the sum of the weights of the members of S. For example, weight \(\{1,12,213,2113\}= \chi_ 1+ \chi_ 1\chi_ 2+ \chi_ 1\chi_ 2\chi_ 3+ \chi^ 2_ 1\chi_ 2\chi_ 3.\) For a finite set D of words let W(A,D) be the set of words in \(A^*\), \(w_ 1w_ 2...w_ f\) such that you cannot find any subsequence \(w_{i_ 1}w_{i_ 2}...w_{i_ r}\) \((1\leq i_ 1<i_ 2<...<i_ r\leq f)\) that belongs to D. The author presents a recursive procedure for computing the weight of W(A,D).