Parity Index of Binary Words and Powers of Prime Words

  • Aleksandar Ilić
  • Sandi Klavžar
  • Yoomi Rho
Keywords: binary words, combinatorics on words, words avoiding a pattern, parity index, generalized Fibonacci cubes


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$.

Author Biographies

Aleksandar Ilić, University of Niš, Serbia
Faculty of Sciences and Mathematics
Sandi Klavžar, University of Ljubljana, Slovenia \\ and \\ University of Maribor, Slovenia

Faculty of Mathematics and Physics \\
University of Ljubljana, Slovenia \\
and \\
Faculty of Natural Sciences and Mathematics\\ University of Maribor, Slovenia



Yoomi Rho, University of incheon
Dept of Mathematics
Article Number