Let $f$ be a binary word and let ${\cal 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 ${\cal 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\le 31$.
@article{10_37236_2178,
author = {Aleksandar Ili\'c and Sandi Klav\v{z}ar and Yoomi Rho},
title = {Parity index of binary words and powers of prime words},
journal = {The electronic journal of combinatorics},
year = {2012},
volume = {19},
number = {3},
doi = {10.37236/2178},
zbl = {1253.68274},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2178/}
}
TY - JOUR
AU - Aleksandar Ilić
AU - Sandi Klavžar
AU - Yoomi Rho
TI - Parity index of binary words and powers of prime words
JO - The electronic journal of combinatorics
PY - 2012
VL - 19
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/2178/
DO - 10.37236/2178
ID - 10_37236_2178
ER -
%0 Journal Article
%A Aleksandar Ilić
%A Sandi Klavžar
%A Yoomi Rho
%T Parity index of binary words and powers of prime words
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/2178/
%R 10.37236/2178
%F 10_37236_2178
Aleksandar Ilić; Sandi Klavžar; Yoomi Rho. Parity index of binary words and powers of prime words. The electronic journal of combinatorics, Tome 19 (2012) no. 3. doi: 10.37236/2178
