Parity index of binary words and powers of prime words (Q456389)

Summary: Let \(f\) be a binary word and let \({\mathcal F}_d(f)\) be the set of words of length \(d\) which do not contain \(f\) as a factor (alias words that avoid the pattern \(f\)). A word is called even/odd if it contains an even/odd number of 1s. The parity index of \(f\) (of dimension \(d)\) is introduced as the difference between the number of even words and the number of odd words in \({\mathcal F}_d(f)\). A word \(f\) is called prime if every nontrivial suffix of \(f\) is different from the prefix of \(f\) of the same length. It is proved that if \(f\) is a power of a prime word, then the absolute value of the parity index of \(f\) is at most 1. We conjecture that no other word has this property and prove the conjecture for words \(0^r1^s0^t\), \(r,s,t \geq 1\). The conjecture has also been verified by computer for all words \(f\) of length at most 10 and all \(d\leq 31\).