0
$\begingroup$

As Danny Rorabaugh's OEIS sequence A262312 suggests, the number of binary words of length $n$ that begin with a even-length palindromic prefix is the same as the number of binary words of length $n$ that have a matching prefix and suffix (sometimes called a "bifix").

I'm interested in finding a bijection $$ \phi_n\colon \big\{s \in \{0,1\}^n : s \text{ has an even-length palindromic prefix}\big\} \rightarrow \big\{s \in \{0,1\}^n : s \text{ has a bifix}\big\} $$ between these sets such that the length of the longest palindromic prefix of $s$ is equal to the total length of the longest bifix of $\phi_n(s)$.

For instance, a map $\underline{1001}1 \mapsto \underline{01}1\underline{01}$ is good, because the palindromic prefix on the left has length four, which is equal to the (total) length of the bifix on the right. However, the map $\underline{00}010 \mapsto \underline{00}1\underline{00}$ is not acceptable, because the palindromic prefix on the left has length two, but the (total) length of the bifix on the right has length four.

Is there a natural way to create a length-preserving bijection like this?

$\endgroup$
3
  • $\begingroup$ Bifix words with prefix & suffix $11...11$ that also have a palindromic infix seem problematic to finding such a bijection. $\endgroup$ Mar 7, 2021 at 4:03
  • $\begingroup$ @CyclotomicField, equivalently with a bifix $00 \cdots 00$ and a palindromic infix, like my second example. $\endgroup$ Mar 7, 2021 at 4:54
  • $\begingroup$ Did you try $uvu \to u\tilde{u}v$? $\endgroup$
    – J.-E. Pin
    Apr 5, 2021 at 6:10

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.