1 Introduction
In this note, we work with finite words over a finite alphabet . For reasons that will be clear later, we assume without loss of generality that for some integer .
We index words starting at position , so that is the first symbol of and is the factor beginning at position and ending at position .
We let denote the reverse of a word; thus, for example, . A word is a palindrome if ; an example in English is radar. A palindrome is even if it is of even length, and odd otherwise. If a palindrome is of length , then its order is defined to be . A palindrome is trivial if it is of length .
A word has an even palindromic prefix (resp., odd palindromic prefix) if there is some nonempty prefix (possibly equal to ) that is a palindrome of even (resp., odd) length. Thus, for example, the English word diffident has the even palindromic prefix diffid of order , and the English word selfless has an odd palindromic prefix selfles of order .
A border of a word is a word that is both a prefix and suffix of . If the only borders of are the trivial ones ( and itself), we say it is unbordered. Otherwise it is bordered. For more about bordered words, see, for example, [10, 3].
Call a border of a word long if and short otherwise. If a word has a long border , then by considering the overlap of the two occurrences of , one as prefix and one as suffix, we see that also has a short border. Given a word , its set of short border lengths is .
By explicit counting for small , one quickly arrives at the conjecture that , the number of length words over that are unbordered, equals , the number of length words over having no even palindromic prefix. This seems to be true, despite the fact that the individual words being counted differ in the two cases. As an example consider , which has an even palindromic prefix but is unbordered. Similarly, if denotes the number of length words over having no odd palindromic prefix, it is natural to conjecture that for odd, and for even. The first few terms of the sequences and are given in the following table.
1  2  3  4  5  6  7  8  9  10  11  12  

2  4  4  8  12  24  40  80  148  296  568  1136  
2  2  4  6  12  20  40  74  148  284  568  1116 
The sequence is sequence A308528 in the OnLine Encyclopedia of Integer Sequences (OEIS) [7], and the sequence is sequence A003000.
In fact, even more seems to be true: if is any set of positive integers, then the number of length words for which gives the lengths of all the short borders of is exactly the same as the number of length words having even palindromic prefixes with orders given by . A similar claim (but slightly different) seems to hold for the odd palindromic prefixes. How can we explain this?
The obvious attempts at a bijection (e.g., map to ) don’t work, because (for example) and both map to . Nevertheless, there is a bijection, as we will see below, and this bijection provides even more information.
2 A bijection on
The perfect shuffle of two words of length , written , is defined as follows: if and , then
Thus, for example, = calliope.
Clearly , a fact we use below.
Lemma 1.
A word is an even palindrome iff there is a word such that .
Proof.
Suppose is an even palindrome. Then it is of the form for some word .
By “unshuffling”, write as , for words and , where is either empty or a single letter, depending on whether is even or odd. Then
Letting , we see that .
Similarly, suppose . Write , where are words of equal length, and is either empty or a single letter, depending on whether is even or odd. Then
Letting , we see that . ∎
For a related result, see [8].
We now define a certain map from to , as follows:
if with and empty or a single letter (depending on whether is even or odd). Thus, for example, and . Clearly this map is a bijection.
Theorem 2.
Let be a word and let . Then has a border of length iff has an even palindromic prefix of order .
Roughly speaking, this theorem says that “maps borders to orders”.
Proof.
Suppose has a border of length . Then , where . Write , where and is either empty, or a single letter, depending on whether is even or odd. Then
which by Lemma 1 has a palindromic prefix of length and order .
Suppose has an even palindromic prefix of order . Write , so that . Write and such that . Now
It follows that is a palindrome and hence . Hence has a length border, namely . ∎
Corollary 3.
Let . Then the number of length words whose short borders are exactly those in equals the number of length words whose even palindromic prefixes are of orders exactly those in .
Let denote the number of length words over a letter alphabet having even palindrome prefixes of order for each , and no other orders.
Proposition 4.
We have for even.
Proof.
Let be even. Let be a word over a letter alphabet with even palindrome prefix lengths given by , and let be a single letter. Then clearly has exactly the same palindromic prefixes as . Since is arbitrary, the result follows. ∎
3 Odd palindrome prefixes
Let be any subset of . Let denote the number of length words over a letter alphabet having odd palindrome prefixes of order for each , and no others.
Proposition 5.
We have for odd.
Proof.
Exactly like the proof of Proposition 4. ∎
Theorem 6.
We have

for odd; and

for even.
Proof.
We begin by proving for odd. We do this by creating a to map from the length words with odd palindrome prefix orders given by to the length words with even palindrome prefix orders given by .
Here is the map. Let be a word of odd length, and define , where the addition is performed modulo . We claim that this is a to map, and furthermore, it maps words with odd palindrome prefix orders given by to words with even palindrome prefix orders also given by .
To see the first claim, observe that if both and are given, then we can uniquely reconstruct . Since is arbitrary, this gives a to map.
To see the second claim, suppose has an odd palindrome prefix of order . Then for . Hence, applying the map to gives
which is clearly an even palindrome of order .
And for even we get
∎
Remark 7.
It is seductive, but wrong, to think that the map also maps evenlength palindrome prefixes in a to manner to oddlength palindrome prefixes, but this is not true (consider what happens to the center letter).
4 Applications
As an application of our results we can (for example) determine the asymptotic fraction of length words having no nontrivial even palindrome prefix (resp., having no nontrivial odd palindrome prefix).
Corollary 8.
For all there is a constant such that the number of length words having no nontrivial even palindrome prefix (resp., having no nontrivial odd palindrome prefix) is asymptotically equal to .
5 Interlude: the permutation defined by
The map defined in Section 2 can be considered as a permutation on . In this case, we write it as . For example, if , the resulting permutation is
This is an interesting permutation that has been wellstudied in the context of cardshuffling, where it is called the milk shuffle. A classic result about the milk shuffle is the following [5]:
Theorem 9.
The order of the permutation is the least such that (mod ).
This is sequence A003558 in the OEIS.
6 No palindrome prefix
In this section we consider the words having no nontrivial palindrome prefix. (Recall that a palindrome is trivial if it is of length .) This is only of interest for alphabet size , for if , the only such words are of the form and .
Let denote the number of such words over a letter alphabet. We use the technique of [1, 4] to show that for a constant and large .
Proposition 10.
For we have
(1)  
(2) 
Proof.
Consider the words of length having no nontrivial palindrome prefix. By appending a new letter, we get words. However, some of these words will be palindromes of length . But since no proper prefix is a palindrome, the first half of these palindromes will be counted by . This gives (1). A similar argument works to prove (2). ∎
For the corresponding sequence is given below and is sequence A252696 in the OEIS:
1  2  3  4  5  6  7  8  9  10  11  12  
3  6  12  30  78  222  636  1878  5556  16590  49548  148422 
Now define by . From (1) and (2) we get
It now follows that
(3) 
By telescoping cancellation applied to (3), we now get
or
If we now set , we get
Note that is the limiting frequency of words having no nontrivial palindrome prefix.
By iterating this functional equation, and using the fact that for small real , we get an expression for :
This is very rapidly converging; for only terms are enough to get 60 decimal places of :
7 Square prefixes
It is natural to conjecture that our bijections connecting words with no border and no even palindrome prefix might also apply to words having no square prefix. However, this is not the case. Let denote the number of length words over having no square prefix. When , for example, the two sequences and differ for the first time at , as the following table indicates.
1  2  3  4  5  6  7  8  9  10  11  12  

2  2  4  6  12  20  40  74  148  284  568  1116  
2  2  4  6  12  20  40  74  148  286  572  1124 
The sequence is sequence A122536 in the OEIS.
Chaffin, Linderman, Sloane, and Wilks [2, §3.7] conjectured that for a constant . In this section we prove this conjecture in more generality.
Theorem 11.
The limit exists and equals a constant with .
Proof.
Let be the number of length words over having a nonempty square prefix, and let be the number of squares of length over having no nonempty proper square prefix. Hence and .
The first few values of and are given in the following table.
1  2  3  4  5  6  7  8  9  10  11  12  

2  2  4  6  10  20  36  72  142  280  560  1114  
0  2  4  10  20  44  88  182  364  738  1476  2972 
Let be a word of length . Either its shortest square prefix is of length 2 (and there are such words), or of length 4 (and there are such words), or …
So , the number of words of length having a nonempty square prefix, is exactly . Hence . Thus exists iff the infinite sum converges. But, since , this sum converges to some constant , by comparison with the sum . It follows that . Letting , the result follows. ∎
To estimate the value of
(and hence ) we use the inequalitiesTaking, for example, , we get and hence . This can be compared to the analogous constant for even palindromes.
References
 [1] G. Blom. Overlapping binary sequences (problem 9420). SIAM Review 37 (1995), 619–620.

[2]
B. Chaffin, J. P. Linderman, N. J. A. Sloane, and A. R. Wilks.
On curling numbers of integer sequences.
J. Integer Sequences 16 (2013), 13.4.3 (electronic),
https://cs.uwaterloo.ca/journals/JIS/VOL16/Sloane/sloane3.html
 [3] A. Ehrenfeucht and D. M. Silberger. Periodicity and unbordered segments of words. Discrete Math. 26 (1979), 101–109.
 [4] Š. Holub and J. Shallit. Periods and borders of random words. In N. Ollinger and H. Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), Vol. 47 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 44:1–44:10. Schloss Dagstuhl–LeibnizZentrum für Informatik, Dagstuhl, Germany, 2016. Available at http://drops.dagstuhl.de/opus/volltexte/2016/5745.
 [5] P. Lévy. Sur quelques classes de permutations. Compositio Math. 8 (1951), 1–48.
 [6] P. Tolstrup Nielsen. A note on bifixfree sequences. IEEE Trans. Inform. Theory IT19 (1973), 704–706.
 [7] N. J. A. Sloane et al. The online encyclopedia of integer sequences. Available at https://oeis.org, 2018.
 [8] N. Rampersad, J. Shallit, and M.w. Wang. Inverse star, borders, and palstars. Inform. Process. Lett. 111 (2011), 420–422.

[9]
L. B. Richmond and J. Shallit.
Counting the palstars.
Electronic J. Combinatorics 21 (2014), P3.25
(electronic),
https://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p25
 [10] D. M. Silberger. Borders and roots of a word. Portugal. Math. 30 (1971), 191–199.
Comments
There are no comments yet.