# Bijection between binary strings with an even-length palindromic prefix and binary strings with a bifix

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?

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