Properties of palindromes in finite words

Mira Anisiu
(original), paper

Abstract

We present a method which displays all palindromes of a given length from De Bruijn words of a certain order, and also a recursive one which constructs all palindromes of length \(n+1\) from the set of palindromes of length \(n\). We show that the palindrome complexity function, which counts the number of palindromes of each length contained in a given word, has a different shape compared with the usual (subword) complexity function. We give upper bounds for the average number of palindromes contained in all words of length n, and obtain exact formulae for the number of palindromes of length 1 and 2 contained in all words of length \(n\).

Authors

Mira-Cristiana Anisiu
Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy, Cluj-Napoca

Valeriu Anisiu
Department of Mathematics Faculty of Mathematics and Computer Science Babeş-Bolyai University of Cluj-Napoca

Zoltán Kása
Department of Computer Science Faculty of Mathematics and Computer Science Babeş-Bolyai University of Cluj-Napoca

Keywords

?

Paper coordinates

M.-C. Anisiu, V. Anisiu, Z. Kása, Properties of palindromes in finite words, Pure Math. Appl., 17 (2006) nos. 3-5, pp. 183-195.

PDF

https://ictp.acad.ro/anisiu/papers/2006-Anisiu-A-K-Properties.pdf

http://www.bke.hu/puma/17_3/AnisiuAnisiuKasa.pdf

About this paper

Journal

Pure Mathematics and Applications

Publisher Name

Romanian Academy

DOI
Print ISSN
Online ISSN

1788-800X

google scholar link

[1] J.-P. Allouche, M. Baake, J. Cassaigne and D. Damanik, Palindrome complexity, Theoret. Comput. Sci., 292 (2003), 9–31.
[2] M.-C. Anisiu and J. Cassaigne, Properties of the complexity function for finite words, Rev. Anal. Num. Théor. Approx., 33 (2004), 123–139.
[3] J.-P. Borel and C. Reutenauer, Palindromic factors of billiard words, Theoret. Comput. Sci., 340 (2005), 334–348.
[4] N.G. De Bruijn, A combinatorial problem, Nederl. Akad. Wetensch. Proc., 49 (1946), 758–764 = Indag. Math., 8 (1946), 461–467.
[5] A. Ehrenfeucht, K.P. Lee and G. Rozenberg, Subword complexities of various classes of deterministic developmental languages without interactions, Theoret. Comput. Sci., 1 (1975), 59–75.
[6] C. Flye Sainte-Marie, Solution to question nr. 48, l’Intermédiaire des Mathématiciens, 1 (1894), 107–110
[7] H. Fredricksen, A survey of full length nonlinear shift register cycle algorithms, SIAM Review, 24 (1982), 195–221.
[8] R.A. Games, A generalized recursive construction for De Bruijn sequences, IEEE Trans. Inform. Theory, 29 (1983), 843–850.
[9] M. Giel-Pietraszuk, M. Hoffmann, S. Dolecka, J. Rychlewski and J. Barciszewski, Palindromes in proteins, J. Protein Chem., 22 (2003), 109–113.
[10] I.J. Good, Normal recurring decimals, J. London Math. Soc., 21 (1946),
167–169.
[11] R.L. Graham, D.E. Knuth and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd edition (Reading, Massachusetts: Addison-Wesley), 1994.
[12] M. Heinz, Zur Teilwortkomplexität für Wörter und Folgen über einem endlichen Alphabet, EIK, 13 (1977), 27–38.
[13] A. de Luca, On the combinatorics of finite words, Theoret. Comput. Sci., 218 (1999), 13–39.
[14] A. de Luca and Al. de Luca, Combinatorial properties of Sturmian palindromes, Int. J. Found. Comput. Sci., 17 (2006), 557–573.
[15] F. Levé and P. Séébold, Proof of a conjecture on word complexity, Bull. Belg. Math. Soc. Simon Stevin, 8 (2001), 277–291.
[16] M.H. Martin, A problem in arrangements, Bull. American Math. Soc., 40 (1934), 859–864.
[17] M. Morse and G.A. Hedlund, Symbolic dynamics, Amer. J. Math., 60 (1938), 815–866.
[18] A. Ralston, A new memoryless algorithm for De Bruijn sequences, J. Algorithms, 2 (1981), 50–62

2006-Anisiu-A-K-Properties

Properties of palindromes in finite words

Mira-Cristiana AnisiuTiberiu Popoviciu Institute of Numerical AnalysisRomanian Academy, Cluj-Napocae-mail: mira@math.ubbcluj.roandValeriu AnisiuDepartment of MathematicsFaculty of Mathematics and Computer ScienceBabeş-Bolyai University of Cluj-Napocae-mail: anisiu@math.ubbcluj.roandZoltán KÁsaDepartment of Computer ScienceFaculty of Mathematics and Computer ScienceBabeş-Bolyai University of Cluj-Napocae-mail: kasa@cs.ubbcluj.ro

(Received: July 12-15, 2006)

Abstract

We present a method which displays all palindromes of a given length from De Bruijn words of a certain order, and also a recursive one which constructs all palindromes of length n + 1 n + 1 n+1n+1n+1 from the set of palindromes of length n n nnn. We show that the palindrome complexity function, which counts the number of palindromes of each length contained in a given word, has a different shape compared with the usual (subword) complexity function. We give upper bounds for the average number of palindromes contained in all words of length n n nnn, and obtain exact formulae for the number of palindromes of length 1 and 2 contained in all words of length n n nnn.

Mathematics Subject Classifications (2000). 68R15

1 Introduction

The palindrome complexity of infinite words has been studied by several authors (see [1], [3], [14] and the references therein). Similar problems related to the number of palindromes are important for finite words too. One of the reasons is that palindromes occur in DNA sequences (over 4 letters) as well as in protein description (over 20 letters), and their role is under research ([9]).
Let an alphabet A A AAA with card ( A ) = q ≥ 1 card ( A ) = q ≥ 1 card(A)=q >= 1\operatorname{card}(A)=q \geq 1card(A)=q≥1 be given. The set of the words of length n n nnn over A A AAA will be denoted by A n A n A^(n)A^{n}An.
Given a word w = w 1 w 2 … w n w = w 1 w 2 … w n w=w_(1)w_(2)dotsw_(n)w=w_{1} w_{2} \ldots w_{n}w=w1w2…wn, the reversed of w w www is w ~ = w n … w 2 w 1 w ~ = w n … w 2 w 1 widetilde(w)=w_(n)dotsw_(2)w_(1)\widetilde{w}=w_{n} \ldots w_{2} w_{1}w~=wn…w2w1. Denoting by ε ε epsi\varepsilonε the empty word, we put by convention ε ~ = ε ε ~ = ε widetilde(epsi)=epsi\widetilde{\varepsilon}=\varepsilonε~=ε. The word w w www is a palindrome if w ~ = w w ~ = w widetilde(w)=w\widetilde{w}=ww~=w. We denote by a k a k a^(k)a^{k}ak the word a … a ⏟ k times a … a ⏟ k  times  ubrace(a dots aubrace)_(k" times ")\underbrace{a \ldots a}_{k \text { times }}a…a⏟k times . The set of the subwords of a word w w www which are nonempty palindromes will be denoted by PAL ( w w www ). The (infinite) set of all palindromes over the alphabet A A AAA is denoted by PAL ( A ) PAL ( A ) PAL(A)\mathrm{PAL}(A)PAL(A), while PAL n ( A ) = PAL ( A ) ∩ A n PAL n ( A ) = PAL ( A ) ∩ A n PAL_(n)(A)=PAL(A)nnA^(n)\operatorname{PAL}_{n}(A)=\operatorname{PAL}(A) \cap A^{n}PALn(A)=PAL(A)∩An.

2 Storing and generating palindromes

An old problem asks if, given an alphabet A A AAA with card ( A ) = q card ( A ) = q card(A)=q\operatorname{card}(A)=qcard(A)=q, there exists a shortest word of length q k + k − 1 q k + k − 1 q^(k)+k-1q^{k}+k-1qk+k−1 containing all the q k q k q^(k)q^{k}qk words of length k k kkk. The answer is affirmative and was given in [6], [10], [4]. For each k ∈ N k ∈ N k inNk \in \mathbb{N}k∈N, these words are called De Bruijn words of order k k kkk. This property can be proved by means of the Eulerian cycles in the De Bruijn graph B k − 1 B k − 1 B_(k-1)B_{k-1}Bk−1. If a window of length k k kkk is moved along a De Bruijn word, at each step a different word is seen, all the q k q k q^(k)q^{k}qk words being displayed.
We ask if it is possible to arrange all palindromes of length k k kkk in a similar way. The answer is in general no, excepting the case of the two palindromes a b a … a a b a … a aba dots aa b a \ldots aaba…a and b a b … b b a b … b bab dots bb a b \ldots bbab…b of odd length.
Proposition 1 Given a word w ∈ A n w ∈ A n w inA^(n)w \in A^{n}w∈An and k ≥ 2 k ≥ 2 k >= 2k \geq 2k≥2, the following statements are equivalent:
(1) all the subwords of length k k kkk are palindromes;
(2) n n nnn is even, k = n − 1 k = n − 1 k=n-1k=n-1k=n−1 and there exists a , b ∈ A , a ≠ b a , b ∈ A , a ≠ b a,b in A,a!=ba, b \in A, a \neq ba,b∈A,a≠b so that w = ( a b ) n / 2 w = ( a b ) n / 2 w=(ab)^(n//2)w=(a b)^{n / 2}w=(ab)n/2.
Furthermore, in this case the only palindromes of w w www are ( a b ) n / 2 − 2 a ( a b ) n / 2 − 2 a (ab)^(n//2-2)a(a b)^{n / 2-2} a(ab)n/2−2a and ( b a ) n / 2 − 2 b ( b a ) n / 2 − 2 b (ba)^(n//2-2)b(b a)^{n / 2-2} b(ba)n/2−2b.
Proof. Let us consider the first two palindromes a 1 a 2 … a k a 1 a 2 … a k a_(1)a_(2)dotsa_(k)a_{1} a_{2} \ldots a_{k}a1a2…ak and b 1 b 2 … b k b 1 b 2 … b k b_(1)b_(2)dotsb_(k)b_{1} b_{2} \ldots b_{k}b1b2…bk such that a 2 a 2 … a k = b 1 b 2 … b k − 1 a 2 a 2 … a k = b 1 b 2 … b k − 1 a_(2)a_(2)dotsa_(k)=b_(1)b_(2)dotsb_(k-1)a_{2} a_{2} \ldots a_{k}=b_{1} b_{2} \ldots b_{k-1}a2a2…ak=b1b2…bk−1, hence
a k − i + 1 = a i = b i − 1 = b k − i + 2 , i = 2 , … , k a k − i + 1 = a i = b i − 1 = b k − i + 2 , i = 2 , … , k a_(k-i+1)=a_(i)=b_(i-1)=b_(k-i+2),quad i=2,dots,ka_{k-i+1}=a_{i}=b_{i-1}=b_{k-i+2}, \quad i=2, \ldots, kak−i+1=ai=bi−1=bk−i+2,i=2,…,k
It follows
i = 2 a k − 1 = a 2 = b 1 = b k i = 3 a k − 2 = a 3 = b 2 = b k − 1 i = 4 a k − 3 = a 4 = b 3 = b k − 2 ⋯ i = k − 1 a 2 = a k − 1 = b k − 2 = b 3 i = k a 1 = a k = b k − 1 = b 2 i = 2      a k − 1 = a 2 = b 1 = b k i = 3      a k − 2 = a 3 = b 2 = b k − 1 i = 4      a k − 3 = a 4 = b 3 = b k − 2      ⋯ i = k − 1      a 2 = a k − 1 = b k − 2 = b 3 i = k      a 1 = a k = b k − 1 = b 2 {:[i=2,a_(k-1)=a_(2)=b_(1)=b_(k)],[i=3,a_(k-2)=a_(3)=b_(2)=b_(k-1)],[i=4,a_(k-3)=a_(4)=b_(3)=b_(k-2)],[,cdots],[i=k-1,a_(2)=a_(k-1)=b_(k-2)=b_(3)],[i=k,a_(1)=a_(k)=b_(k-1)=b_(2)]:}\begin{array}{ll} i=2 & a_{k-1}=a_{2}=b_{1}=b_{k} \\ i=3 & a_{k-2}=a_{3}=b_{2}=b_{k-1} \\ i=4 & a_{k-3}=a_{4}=b_{3}=b_{k-2} \\ & \cdots \\ i=k-1 & a_{2}=a_{k-1}=b_{k-2}=b_{3} \\ i=k & a_{1}=a_{k}=b_{k-1}=b_{2} \end{array}i=2ak−1=a2=b1=bki=3ak−2=a3=b2=bk−1i=4ak−3=a4=b3=bk−2⋯i=k−1a2=ak−1=bk−2=b3i=ka1=ak=bk−1=b2
If k = 2 l , ( l ≥ 1 ) k = 2 l , ( l ≥ 1 ) k=2l,(l >= 1)k=2 l,(l \geq 1)k=2l,(l≥1) we have b 2 = a 1 = a 3 = … = a k − 1 b 2 = a 1 = a 3 = … = a k − 1 b_(2)=a_(1)=a_(3)=dots=a_(k-1)b_{2}=a_{1}=a_{3}=\ldots=a_{k-1}b2=a1=a3=…=ak−1 and b 3 = a 2 = … = a k b 3 = a 2 = … = a k b_(3)=a_(2)=dots=a_(k)b_{3}=a_{2}=\ldots=a_{k}b3=a2=…=ak and a 1 a 2 … a k a 1 a 2 … a k a_(1)a_(2)dotsa_(k)a_{1} a_{2} \ldots a_{k}a1a2…ak is a palindrome if and only if a 1 = a 2 = … = a k a 1 = a 2 = … = a k a_(1)=a_(2)=dots=a_(k)a_{1}=a_{2}=\ldots=a_{k}a1=a2=…=ak, hence a 1 a 2 … a k = a k a 1 a 2 … a k = a k a_(1)a_(2)dotsa_(k)=a^(k)a_{1} a_{2} \ldots a_{k}=a^{k}a1a2…ak=ak; it follows that b 1 b 2 … b k = a k b 1 b 2 … b k = a k b_(1)b_(2)dotsb_(k)=a^(k)b_{1} b_{2} \ldots b_{k}=a^{k}b1b2…bk=ak too, and the two palindromes are equal.
If k = 2 l + 1 k = 2 l + 1 k=2l+1k=2 l+1k=2l+1, we have b 2 = a 1 = a 3 = … = a k b 2 = a 1 = a 3 = … = a k b_(2)=a_(1)=a_(3)=dots=a_(k)b_{2}=a_{1}=a_{3}=\ldots=a_{k}b2=a1=a3=…=ak and b 3 = a 2 = … = a k − 1 b 3 = a 2 = … = a k − 1 b_(3)=a_(2)=dots=a_(k-1)b_{3}=a_{2}=\ldots=a_{k-1}b3=a2=…=ak−1, hence a 1 a 2 … a k = a b a b … a ( a ≠ b ) a 1 a 2 … a k = a b a b … a ( a ≠ b ) a_(1)a_(2)dotsa_(k)=abab dots a(a!=b)a_{1} a_{2} \ldots a_{k}=a b a b \ldots a(a \neq b)a1a2…ak=abab…a(a≠b) and b 1 b 2 … b k = b a b … b b 1 b 2 … b k = b a b … b b_(1)b_(2)dotsb_(k)=bab dots bb_{1} b_{2} \ldots b_{k}=b a b \ldots bb1b2…bk=bab…b. If another palindrome will follow, it must be again ( a b ) n / 2 ( a b ) n / 2 (ab)^(n//2)(a b)^{n / 2}(ab)n/2 (equal with the first one).
Remark 1 For k = 1 k = 1 k=1k=1k=1, the maximum length of a word containing all distinct palindromes of length 1 (i.e. letters) exactly once is n = q n = q n=qn=qn=q.
It is obvious that for k ≥ 2 k ≥ 2 k >= 2k \geq 2k≥2 it is not possible to arrange all palindromes of length k k kkk in the most compact way. But each palindrome is determined by the
parity of its length and its first ⌈ k / 2 ⌉ ⌈ k / 2 ⌉ |~k//2~|\lceil k / 2\rceil⌈k/2⌉ letters, where ⌈ ⋅ ⌉ ⌈ ⋅ ⌉ |~*~|\lceil\cdot\rceil⌈⋅⌉ denotes the ceil function (which returns the smallest integer that is greater than or equal to a specified number).
Proposition 2 All palindromes of length k k kkk can be obtained from a De Bruijn word of length q ⌈ k / 2 ⌉ + ⌈ k / 2 ⌉ − 1 q ⌈ k / 2 ⌉ + ⌈ k / 2 ⌉ − 1 q^(|~k//2~|)+|~k//2~|-1q^{\lceil k / 2\rceil}+\lceil k / 2\rceil-1q⌈k/2⌉+⌈k/2⌉−1.
Proof. The De Bruijn word contains all different words of length ⌈ k / 2 ⌉ ⌈ k / 2 ⌉ |~k//2~|\lceil k / 2\rceil⌈k/2⌉. Each such word a 1 … a ⌈ k / 2 ⌉ a 1 … a ⌈ k / 2 ⌉ a_(1)dotsa_(|~k//2~|)a_{1} \ldots a_{\lceil k / 2\rceil}a1…a⌈k/2⌉ can be extended to a palindrome by symmetry, for k k kkk even, and by taking a ⌈ k / 2 ⌉ + 1 = a ⌈ k / 2 ⌉ − 1 , … , a k = a 1 a ⌈ k / 2 ⌉ + 1 = a ⌈ k / 2 ⌉ − 1 , … , a k = a 1 a_(|~k//2~|+1)=a_(|~k//2~|-1),dots,a_(k)=a_(1)a_{\lceil k / 2\rceil+1}=a_{\lceil k / 2\rceil-1}, \ldots, a_{k}=a_{1}a⌈k/2⌉+1=a⌈k/2⌉−1,…,ak=a1, for k k kkk odd.
Example 1 Let k = 3 , q = 3 k = 3 , q = 3 k=3,q=3k=3, q=3k=3,q=3 and the De Bruijn word of order ⌈ k / 2 ⌉ = 2 w 1 = 0221201100 ⌈ k / 2 ⌉ = 2 w 1 = 0221201100 |~k//2~|=2w_(1)=0221201100\lceil k / 2\rceil=2 w_{1}=0221201100⌈k/2⌉=2w1=0221201100. From each word of length 2 which appears in the given De Bruijn word, we obtain the corresponding palindrome of length k = 3 k = 3 k=3k=3k=3 :
02 → 020 22 → 222 21 → 212 12 → 121 20 → 202 01 → 010 11 → 111 10 → 101 00 → 000 . 02 → 020 22 → 222 21 → 212 12 → 121 20 → 202 01 → 010 11 → 111 10 → 101 00 → 000 .  {:[02 rarr020],[22 rarr222],[21 rarr212],[12 rarr121],[20 rarr202],[01 rarr010],[11 rarr111],[10 rarr101],[00 rarr000". "]:}\begin{aligned} & 02 \rightarrow 020 \\ & 22 \rightarrow 222 \\ & 21 \rightarrow 212 \\ & 12 \rightarrow 121 \\ & 20 \rightarrow 202 \\ & 01 \rightarrow 010 \\ & 11 \rightarrow 111 \\ & 10 \rightarrow 101 \\ & 00 \rightarrow 000 \text {. } \end{aligned}02→02022→22221→21212→12120→20201→01011→11110→10100→000. 
Let k = 4 , q = 2 k = 4 , q = 2 k=4,q=2k=4, q=2k=4,q=2 and the De Bruijn word of order ⌈ k / 2 ⌉ = 2 w 2 = 01100 ⌈ k / 2 ⌉ = 2 w 2 = 01100 |~k//2~|=2w_(2)=01100\lceil k / 2\rceil=2 w_{2}=01100⌈k/2⌉=2w2=01100. From each word of length 2 contained in 01100 we obtain by symmetry the corresponding palindrome of length k = 4 k = 4 k=4k=4k=4 :
01 → 0110 11 → 1111 10 → 1001 00 → 0000 . 01 → 0110 11 → 1111 10 → 1001 00 → 0000 . {:[01 rarr0110],[11 rarr1111],[10 rarr1001],[00 rarr0000.]:}\begin{aligned} & 01 \rightarrow 0110 \\ & 11 \rightarrow 1111 \\ & 10 \rightarrow 1001 \\ & 00 \rightarrow 0000 . \end{aligned}01→011011→111110→100100→0000.
There are several algorithms which construct De Bruijn words, for example, in [16], [18], [7] and [8].
We can generate recursively all palindromes of length n , n ∈ N n , n ∈ N n,n inNn, n \in \mathbb{N}n,n∈N, using the difference representation. This is based on the following proposition.
Proposition 3 If w 1 , w 2 , … , w p w 1 , w 2 , … , w p w_(1),w_(2),dots,w_(p)w_{1}, w_{2}, \ldots, w_{p}w1,w2,…,wp are all binary ( A = { 0 , 1 } A = { 0 , 1 } A={0,1}A=\{0,1\}A={0,1} ) palindromes of length n n nnn, where p = 2 ⌈ n 2 ⌉ , n ≥ 1 p = 2 n 2 , n ≥ 1 p=2^(|~(n)/(2)~|),n >= 1p=2^{\left\lceil\frac{n}{2}\right\rceil}, n \geq 1p=2⌈n2⌉,n≥1, then
2 w 1 , 2 w 2 , … , 2 w p , 2 n + 1 + 1 + 2 w 1 , 2 n + 1 + 1 + 2 w 2 , … , 2 n + 1 + 1 + 2 w p 2 w 1 , 2 w 2 , … , 2 w p , 2 n + 1 + 1 + 2 w 1 , 2 n + 1 + 1 + 2 w 2 , … , 2 n + 1 + 1 + 2 w p 2w_(1),2w_(2),dots,2w_(p),2^(n+1)+1+2w_(1),2^(n+1)+1+2w_(2),dots,2^(n+1)+1+2w_(p)2 w_{1}, 2 w_{2}, \ldots, 2 w_{p}, 2^{n+1}+1+2 w_{1}, 2^{n+1}+1+2 w_{2}, \ldots, 2^{n+1}+1+2 w_{p}2w1,2w2,…,2wp,2n+1+1+2w1,2n+1+1+2w2,…,2n+1+1+2wp
are all palindromes of length n + 2 n + 2 n+2n+2n+2.
Proof. If w w www is a binary palindrome of length n n nnn, then 0 w 0 0 w 0 0w00 w 00w0 and 1 w 1 1 w 1 1w11 w 11w1 will be palindromes too, and the only palindromes of length n + 2 n + 2 n+2n+2n+2 which contains w w www as a subword, which proves the proposition.
In order to generate all binary palindromes of a given length let us begin with an example considering all binary palindromes of length 3 and 4 and their decimal representation:
000 0 0000 0
010 2 0110 6
101 5 1001 9
111 7 1111 15
000 0 0000 0 010 2 0110 6 101 5 1001 9 111 7 1111 15| 000 | 0 | 0000 | 0 | | ---: | ---: | ---: | ---: | | 010 | 2 | 0110 | 6 | | 101 | 5 | 1001 | 9 | | 111 | 7 | 1111 | 15 |
The sequence of palindromes in increasing order based on their decimal value for a given length can be represented by their differences. The difference representation of the sequence 0 , 2 , 5 , 7 0 , 2 , 5 , 7 0,2,5,70,2,5,70,2,5,7 is 2 , 3 , 2 ( 2 − 0 = 2 , 5 − 2 = 3 , 7 − 5 = 2 ) 2 , 3 , 2 ( 2 − 0 = 2 , 5 − 2 = 3 , 7 − 5 = 2 ) 2,3,2(2-0=2,5-2=3,7-5=2)2,3,2(2-0=2,5-2=3,7-5=2)2,3,2(2−0=2,5−2=3,7−5=2), and the difference representation of the sequence 0 , 6 , 9 , 15 0 , 6 , 9 , 15 0,6,9,150,6,9,150,6,9,15 is 6 , 3 , 6 6 , 3 , 6 6,3,66,3,66,3,6. A difference representation is always a symmetric sequence and the corresponding sequence of palindromes in decimal can be obtained by successive addition beginning with 0 : 0 + 6 = 6 , 6 + 3 = 9 , 9 + 6 = 1 5 0 : 0 + 6 = 6 , 6 + 3 = 9 , 9 + 6 = 1 5 0:0+6=6,6+3=9,9+6=150: \mathbf{0}+6=\mathbf{6}, \mathbf{6}+3=\mathbf{9}, \mathbf{9}+6=\mathbf{1 5}0:0+6=6,6+3=9,9+6=15. By direct computation we obtain the following difference representation of palindromes for length n ≤ 8 n ≤ 8 n <= 8n \leq 8n≤8.
n n nnn
11
23
3 2 3 2
4 6 3 6
5 4 6 4 3 4 6 4
6 12 6 12 3 12 6 12
7 8 12 8 6 8 12 8 3 8 12 8 6 8 12 8
8 24 12 24 6 24 12 24 3 24 12 24 6 24 12 24
n 11 23 3 2 3 2 4 6 3 6 5 4 6 4 3 4 6 4 6 12 6 12 3 12 6 12 7 8 12 8 6 8 12 8 3 8 12 8 6 8 12 8 8 24 12 24 6 24 12 24 3 24 12 24 6 24 12 24| $n$ | | | | | | | | | | | | | | | | | | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | | | 11 | | | | | | | | | | | | | | | | | | 23 | | | | | | | | | | | | | | | | | 3 | | 2 | 3 | 2 | | | | | | | | | | | | | | 4 | | 6 | 3 | 6 | | | | | | | | | | | | | | 5 | | 4 | 6 | 4 | 3 | 4 | 6 | 4 | | | | | | | | | | 6 | | 12 | 6 | 12 | 3 | 12 | 6 | 12 | | | | | | | | | | 7 | | 8 | 12 | 8 | 6 | 8 | 12 | 8 | 3 | 8 | 12 | 8 | 6 | 8 | 12 | 8 | | 8 | | 24 | 12 | 24 | 6 | 24 | 12 | 24 | 3 | 24 | 12 | 24 | 6 | 24 | 12 | 24 |
We easily can generalize and prove by induction that the difference representations can be obtained as follows.
For n = 2 k n = 2 k n=2kn=2 kn=2k we have the difference representation:
a 1 , a 2 , … , a 2 k − 1 , a 1 , a 2 , … , a 2 k − 1 , a_(1),a_(2),dots,a_(2^(k)-1),a_{1}, a_{2}, \ldots, a_{2^{k}-1},a1,a2,…,a2k−1,
from which the difference representation for 2 k + 1 2 k + 1 2k+12 k+12k+1 is:
2 k , a 1 , 2 k , a 2 , 2 k , … , 2 k , a 2 k − 1 , 2 k . 2 k , a 1 , 2 k , a 2 , 2 k , … , 2 k , a 2 k − 1 , 2 k . 2^(k),a_(1),2^(k),a_(2),2^(k),dots,2^(k),a_(2^(k)-1),2^(k).2^{k}, a_{1}, 2^{k}, a_{2}, 2^{k}, \ldots, 2^{k}, a_{2^{k}-1}, 2^{k} .2k,a1,2k,a2,2k,…,2k,a2k−1,2k.
For n = 2 k + 1 n = 2 k + 1 n=2k+1n=2 k+1n=2k+1 we have the difference representation:
2 k , a 1 , 2 k , a 2 , 2 k , … , 2 k , a 2 k − 1 , 2 k , 2 k , a 1 , 2 k , a 2 , 2 k , … , 2 k , a 2 k − 1 , 2 k , 2^(k),a_(1),2^(k),a_(2),2^(k),dots,2^(k),a_(2^(k)-1),2^(k),2^{k}, a_{1}, 2^{k}, a_{2}, 2^{k}, \ldots, 2^{k}, a_{2^{k}-1}, 2^{k},2k,a1,2k,a2,2k,…,2k,a2k−1,2k,
from which the difference representation for 2 k + 2 2 k + 2 2k+22 k+22k+2 is:
3 ⋅ 2 k , a 1 , 3 ⋅ 2 k , a 2 , 3 ⋅ 2 k , … , 3 ⋅ 2 k , a 2 k − 1 , 3 ⋅ 2 k . 3 ⋅ 2 k , a 1 , 3 ⋅ 2 k , a 2 , 3 ⋅ 2 k , … , 3 ⋅ 2 k , a 2 k − 1 , 3 ⋅ 2 k . 3*2^(k),a_(1),3*2^(k),a_(2),3*2^(k),dots,3*2^(k),a_(2^(k)-1),3*2^(k).3 \cdot 2^{k}, a_{1}, 3 \cdot 2^{k}, a_{2}, 3 \cdot 2^{k}, \ldots, 3 \cdot 2^{k}, a_{2^{k}-1}, 3 \cdot 2^{k} .3⋅2k,a1,3⋅2k,a2,3⋅2k,…,3⋅2k,a2k−1,3⋅2k.
This representation can be generalized for q ≥ 2 q ≥ 2 q >= 2q \geq 2q≥2. The number of palindromes in this case is q ⌈ n 2 ⌉ q n 2 q^(|~(n)/(2)~|)q^{\left\lceil\frac{n}{2}\right\rceil}q⌈n2⌉.
For n = 2 k n = 2 k n=2kn=2 kn=2k we have the difference representation:
a 1 , a 2 , … , a q k − 1 a 1 , a 2 , … , a q k − 1 a_(1),a_(2),dots,a_(q^(k)-1)a_{1}, a_{2}, \ldots, a_{q^{k}-1}a1,a2,…,aqk−1
from which the difference representation for 2 k + 1 2 k + 1 2k+12 k+12k+1 is:
q k , … , q k ⏟ q − 1 times , a 1 , q k , … , q k ⏟ q − 1 times , a 2 , q k , … , q k ⏟ q − 1 times , … , q k , … , q k ⏟ q − 1 times , a q k − 1 , q k , … , q k ⏟ q − 1 times . q k , … , q k ⏟ q − 1  times  , a 1 , q k , … , q k ⏟ q − 1  times  , a 2 , q k , … , q k ⏟ q − 1  times  , … , q k , … , q k ⏟ q − 1  times  , a q k − 1 , q k , … , q k ⏟ q − 1  times  . ubrace(q^(k),dots,q^(k)ubrace)_(q-1" times "),a_(1),ubrace(q^(k),dots,q^(k)ubrace)_(q-1" times "),a_(2),ubrace(q^(k),dots,q^(k)ubrace)_(q-1" times "),dots,ubrace(q^(k),dots,q^(k)ubrace)_(q-1" times "),a_(q^(k)-1),ubrace(q^(k),dots,q^(k)ubrace)_(q-1" times ").\underbrace{q^{k}, \ldots, q^{k}}_{q-1 \text { times }}, a_{1}, \underbrace{q^{k}, \ldots, q^{k}}_{q-1 \text { times }}, a_{2}, \underbrace{q^{k}, \ldots, q^{k}}_{q-1 \text { times }}, \ldots, \underbrace{q^{k}, \ldots, q^{k}}_{q-1 \text { times }}, a_{q^{k}-1}, \underbrace{q^{k}, \ldots, q^{k}}_{q-1 \text { times }} .qk,…,qk⏟q−1 times ,a1,qk,…,qk⏟q−1 times ,a2,qk,…,qk⏟q−1 times ,…,qk,…,qk⏟q−1 times ,aqk−1,qk,…,qk⏟q−1 times .
For n = 2 k + 1 n = 2 k + 1 n=2k+1n=2 k+1n=2k+1 we have the difference representation:
q k , … , q k ⏟ q − 1 times , a 1 , q k , … , q k ⏟ q − 1 times , a 2 , … , a q k − 1 , q k , … , q k ⏟ q − 1 times , q k , … , q k ⏟ q − 1  times  , a 1 , q k , … , q k ⏟ q − 1  times  , a 2 , … , a q k − 1 , q k , … , q k ⏟ q − 1  times  , ubrace(q^(k),dots,q^(k)ubrace)_(q-1" times "),a_(1),ubrace(q^(k),dots,q^(k)ubrace)_(q-1" times "),a_(2),dots,a_(q^(k)-1),ubrace(q^(k),dots,q^(k)ubrace)_(q-1" times "),\underbrace{q^{k}, \ldots, q^{k}}_{q-1 \text { times }}, a_{1}, \underbrace{q^{k}, \ldots, q^{k}}_{q-1 \text { times }}, a_{2}, \ldots, a_{q^{k}-1}, \underbrace{q^{k}, \ldots, q^{k}}_{q-1 \text { times }},qk,…,qk⏟q−1 times ,a1,qk,…,qk⏟q−1 times ,a2,…,aqk−1,qk,…,qk⏟q−1 times ,
from which the difference representation for 2 k + 2 2 k + 2 2k+22 k+22k+2 is:
( q + 1 ) q k , … , ( q + 1 ) q k ⏟ q − 1 times , a 1 , ( q + 1 ) q k , … , ( q + 1 ) q k ⏟ q − 1 times , a 2 , … , ( q + 1 ) q k , … , ( q + 1 ) q k ⏟ q − 1 times , a q k − 1 , ( q + 1 ) q k , … , ( q + 1 ) q k ⏟ q − 1 times . ( q + 1 ) q k , … , ( q + 1 ) q k ⏟ q − 1  times  , a 1 , ( q + 1 ) q k , … , ( q + 1 ) q k ⏟ q − 1  times  , a 2 , … , ( q + 1 ) q k , … , ( q + 1 ) q k ⏟ q − 1  times  , a q k − 1 , ( q + 1 ) q k , … , ( q + 1 ) q k ⏟ q − 1  times  . {:[ubrace((q+1)q^(k),dots,(q+1)q^(k)ubrace)_(q-1" times ")","a_(1)","ubrace((q+1)q^(k),dots,(q+1)q^(k)ubrace)_(q-1" times ")","a_(2)","],[ dots","ubrace((q+1)q^(k),dots,(q+1)q^(k)ubrace)_(q-1" times ")","a_(q^(k)-1)","ubrace((q+1)q^(k),dots,(q+1)q^(k)ubrace)_(q-1" times ").]:}\begin{aligned} & \underbrace{(q+1) q^{k}, \ldots,(q+1) q^{k}}_{q-1 \text { times }}, a_{1}, \underbrace{(q+1) q^{k}, \ldots,(q+1) q^{k}}_{q-1 \text { times }}, a_{2}, \\ & \ldots, \underbrace{(q+1) q^{k}, \ldots,(q+1) q^{k}}_{q-1 \text { times }}, a_{q^{k}-1}, \underbrace{(q+1) q^{k}, \ldots,(q+1) q^{k}}_{q-1 \text { times }} . \end{aligned}(q+1)qk,…,(q+1)qk⏟q−1 times ,a1,(q+1)qk,…,(q+1)qk⏟q−1 times ,a2,…,(q+1)qk,…,(q+1)qk⏟q−1 times ,aqk−1,(q+1)qk,…,(q+1)qk⏟q−1 times .

3 The shape of the palindrome complexity functions

For an infinite sequence U U UUU, the (subword) complexity function p U : N ⟶ N p U : N ⟶ N p_(U):NlongrightarrowNp_{U}: \mathbb{N} \longrightarrow \mathbb{N}pU:N⟶N (defined in [17] as the block growth, then named subword complexity in [5]) is given by p U ( n ) = card ( F ( U ) ∩ A n ) p U ( n ) = card F ( U ) ∩ A n p_(U)(n)=card(F(U)nnA^(n))p_{U}(n)=\operatorname{card}\left(F(U) \cap A^{n}\right)pU(n)=card(F(U)∩An) for n ∈ N n ∈ N n inNn \in \mathbb{N}n∈N, where F ( U ) F ( U ) F(U)F(U)F(U) is the set of all finite subwords (factors) of U U UUU. Therefore the complexity function maps each nonnegative number n n nnn to the number of subwords of length n n nnn of U U UUU; it verifies the iterative equation
(1) p U ( n + 1 ) = p U ( n ) + ∑ j = 2 q ( j − 1 ) s ( j , n ) (1) p U ( n + 1 ) = p U ( n ) + ∑ j = 2 q   ( j − 1 ) s ( j , n ) {:(1)p_(U)(n+1)=p_(U)(n)+sum_(j=2)^(q)(j-1)s(j","n):}\begin{equation*} p_{U}(n+1)=p_{U}(n)+\sum_{j=2}^{q}(j-1) s(j, n) \tag{1} \end{equation*}(1)pU(n+1)=pU(n)+∑j=2q(j−1)s(j,n)
s ( j , n ) s ( j , n ) s(j,n)s(j, n)s(j,n) being the cardinal of the set of the subwords in U U UUU having the length n n nnn and the right valence j j jjj. A subword u ∈ U u ∈ U u in Uu \in Uu∈U has the right valence j j jjj if there are j j jjj and only j j jjj distinct letters x i x i x_(i)x_{i}xi such that u x i ∈ F ( U ) , 1 ≤ i ≤ j u x i ∈ F ( U ) , 1 ≤ i ≤ j ux_(i)in F(U),1 <= i <= ju x_{i} \in F(U), 1 \leq i \leq juxi∈F(U),1≤i≤j.
For a finite word w w www of length n n nnn, the complexity function p w : N ⟶ N p w : N ⟶ N p_(w):NlongrightarrowNp_{w}: \mathbb{N} \longrightarrow \mathbb{N}pw:N⟶N given by p w ( k ) = card ( F ( w ) ∩ A k ) , k ∈ N p w ( k ) = card F ( w ) ∩ A k , k ∈ N p_(w)(k)=card(F(w)nnA^(k)),k inNp_{w}(k)=\operatorname{card}\left(F(w) \cap A^{k}\right), k \in \mathbb{N}pw(k)=card(F(w)∩Ak),k∈N, has the property that p w ( k ) = 0 p w ( k ) = 0 p_(w)(k)=0p_{w}(k)=0pw(k)=0 for k > n k > n k > nk>nk>n. The corresponding iterative equation is
(2) p w ( k + 1 ) = p w ( k ) + ∑ j = 2 q ( j − 1 ) s ( j , k ) − s 0 ( k ) , (2) p w ( k + 1 ) = p w ( k ) + ∑ j = 2 q   ( j − 1 ) s ( j , k ) − s 0 ( k ) , {:(2)p_(w)(k+1)=p_(w)(k)+sum_(j=2)^(q)(j-1)s(j","k)-s_(0)(k)",":}\begin{equation*} p_{w}(k+1)=p_{w}(k)+\sum_{j=2}^{q}(j-1) s(j, k)-s_{0}(k), \tag{2} \end{equation*}(2)pw(k+1)=pw(k)+∑j=2q(j−1)s(j,k)−s0(k),
where s 0 ( k ) = s ( 0 , k ) ∈ { 0 , 1 } s 0 ( k ) = s ( 0 , k ) ∈ { 0 , 1 } s_(0)(k)=s(0,k)in{0,1}s_{0}(k)=s(0, k) \in\{0,1\}s0(k)=s(0,k)∈{0,1} stands for the cardinal of the set of subwords v v vvv (suffixes of w w www of length k k kkk ) which cannot be continued as v x ∈ F ( w ) , x ∈ A v x ∈ F ( w ) , x ∈ A vx in F(w),x in Av x \in F(w), x \in Avx∈F(w),x∈A. We can write (2) in a condensed form
(3) p w ( k + 1 ) = p w ( k ) + ∑ j = 0 q ( j − 1 ) s ( j , k ) . (3) p w ( k + 1 ) = p w ( k ) + ∑ j = 0 q   ( j − 1 ) s ( j , k ) . {:(3)p_(w)(k+1)=p_(w)(k)+sum_(j=0)^(q)(j-1)s(j","k).:}\begin{equation*} p_{w}(k+1)=p_{w}(k)+\sum_{j=0}^{q}(j-1) s(j, k) . \tag{3} \end{equation*}(3)pw(k+1)=pw(k)+∑j=0q(j−1)s(j,k).
The above relations have their correspondents in terms of left extensions of the subwords.
For an infinite sequence U U UUU, the complexity function p U p U p_(U)p_{U}pU is nondecreasing; more than that, if there exists m ∈ N m ∈ N m inNm \in \mathbb{N}m∈N such that p U ( m + 1 ) = p U ( m ) p U ( m + 1 ) = p U ( m ) p_(U)(m+1)=p_(U)(m)p_{U}(m+1)=p_{U}(m)pU(m+1)=pU(m), then p U p U p_(U)p_{U}pU is constant for n ≥ m n ≥ m n >= mn \geq mn≥m.
The complexity function for a finite word w w www of length n n nnn has a different behaviour, because of p w ( n ) = 1 p w ( n ) = 1 p_(w)(n)=1p_{w}(n)=1pw(n)=1 (there is a unique subword of length n n nnn, namely w ) w ) w)w)w). It was proved ([12], [13], [15], [2]) that the shape of the complexity function is trapezoidal:
Theorem 1 Given a finite word w w www of length n n nnn, there are three intervals of monotonicity for p w : [ 0 , J ] , [ J , M ] p w : [ 0 , J ] , [ J , M ] p_(w):[0,J],[J,M]p_{w}:[0, J],[J, M]pw:[0,J],[J,M] and [ M , n ] [ M , n ] [M,n][M, n][M,n]; the function increases at first, is constant and then decreases with the slope -1 .
The palindrome complexity function of a finite or infinite word w w www is given by pal w : N ⟶ N , pal w ( k ) = card ( PAL ( w ) ∩ A k ) , k ∈ N pal w : N ⟶ N , pal w ( k ) = card PAL ( w ) ∩ A k , k ∈ N pal_(w):NlongrightarrowN,pal_(w)(k)=card(PAL(w)nnA^(k)),k inN\operatorname{pal}_{w}: \mathbb{N} \longrightarrow \mathbb{N}, \operatorname{pal}_{w}(k)=\operatorname{card}\left(\operatorname{PAL}(w) \cap A^{k}\right), k \in \mathbb{N}palw:N⟶N,palw(k)=card(PAL(w)∩Ak),k∈N. Obviously,
(4) pal w ( k ) ≤ p w ( k ) , k ∈ N (4) pal w ( k ) ≤ p w ( k ) , k ∈ N {:(4)pal_(w)(k) <= p_(w)(k)","k inN:}\begin{equation*} \operatorname{pal}_{w}(k) \leq p_{w}(k), k \in \mathbb{N} \tag{4} \end{equation*}(4)palw(k)≤pw(k),k∈N
and for finite words of length | w | = n | w | = n |w|=n|w|=n|w|=n,
(5) pal w ( k ) ≤ min { q ⌈ k / 2 ⌉ , n − k + 1 } , k ∈ { 0 , … , n } (5) pal w ( k ) ≤ min q ⌈ k / 2 ⌉ , n − k + 1 , k ∈ { 0 , … , n } {:(5)pal_(w)(k) <= min{q^(|~k//2~|),n-k+1}","k in{0","dots","n}:}\begin{equation*} \operatorname{pal}_{w}(k) \leq \min \left\{q^{\lceil k / 2\rceil}, n-k+1\right\}, k \in\{0, \ldots, n\} \tag{5} \end{equation*}(5)palw(k)≤min{q⌈k/2⌉,n−k+1},k∈{0,…,n}
The palindrome u ∈ PAL ( w ) u ∈ PAL ( w ) u inPAL(w)u \in \mathrm{PAL}(w)u∈PAL(w) has the palindrome valence j j jjj if there are j j jjj and only j j jjj distinct letters x i x i x_(i)x_{i}xi such that x i u x i ∈ PAL ( w ) , 1 ≤ i ≤ j x i u x i ∈ PAL ( w ) , 1 ≤ i ≤ j x_(i)ux_(i)inPAL(w),1 <= i <= jx_{i} u x_{i} \in \mathrm{PAL}(w), 1 \leq i \leq jxiuxi∈PAL(w),1≤i≤j. We denote by
(6) s p ( j , k ) = card { u ∈ ( PAL ( w ) ∩ A k ) : u has the palindrome valence j } , (6) s p ( j , k ) = card u ∈ PAL ( w ) ∩ A k : u  has the palindrome valence  j , {:(6)s_(p)(j","k)=card{u in(PAL(w)nnA^(k)):u" has the palindrome valence "j}",":}\begin{equation*} s_{p}(j, k)=\operatorname{card}\left\{u \in\left(\operatorname{PAL}(w) \cap A^{k}\right): u \text { has the palindrome valence } j\right\}, \tag{6} \end{equation*}(6)sp(j,k)=card{u∈(PAL(w)∩Ak):u has the palindrome valence j},
and by s p ( 0 , k ) s p ( 0 , k ) s_(p)(0,k)s_{p}(0, k)sp(0,k) the cardinal of the set of subwords v ∈ PAL ( w ) ∩ A k v ∈ PAL ( w ) ∩ A k v inPAL(w)nnA^(k)v \in \mathrm{PAL}(w) \cap A^{k}v∈PAL(w)∩Ak (not necessarily suffixes or prefixes of w w www ) which cannot be continued as x v x ∈ PAL ( w ) x v x ∈ PAL ( w ) xvx in PAL(w)x v x \in \operatorname{PAL}(w)xvx∈PAL(w), x ∈ A x ∈ A x in Ax \in Ax∈A.
The palindrome complexity function of finite or infinite words satisfies the iterative equation
(7) pal w ( k + 2 ) = pal w ( k ) + ∑ j = 0 q ( j − 1 ) s p ( j , k ) (7) pal w ( k + 2 ) = pal w ( k ) + ∑ j = 0 q   ( j − 1 ) s p ( j , k ) {:(7)pal_(w)(k+2)=pal_(w)(k)+sum_(j=0)^(q)(j-1)s_(p)(j","k):}\begin{equation*} \operatorname{pal}_{w}(k+2)=\operatorname{pal}_{w}(k)+\sum_{j=0}^{q}(j-1) s_{p}(j, k) \tag{7} \end{equation*}(7)palw(k+2)=palw(k)+∑j=0q(j−1)sp(j,k)
Due to the fact that the number of even palindromes is not directly related to that of odd ones, we do not expect that pal w pal w pal_(w)\mathrm{pal}_{w}palw is of trapezoidal shape, as it was the case for the subword complexity function p w p w p_(w)p_{w}pw.
Figure 1: Odd and even palindrome complexity function
For this reason we define the odd, respectively even palindrome complexity function as the restrictions of pal w pal w pal_(w)\mathrm{pal}_{w}palw to odd, respectively even integers: pal w o pal w o pal_(w)^(o)\mathrm{pal}_{w}^{o}palwo : 2 N + 1 → N , pal w o ( k ) = pal w ( k ) ; pal w e : 2 N → N , pal w e ( k ) = pal w ( k ) 2 N + 1 → N , pal w o ( k ) = pal w ( k ) ; pal w e : 2 N → N , pal w e ( k ) = pal w ( k ) 2N+1rarrN,pal_(w)^(o)(k)=pal_(w)(k);pal_(w)^(e):2NrarrN,pal_(w)^(e)(k)=pal_(w)(k)2 \mathbb{N}+1 \rightarrow \mathbb{N}, \operatorname{pal}_{w}^{o}(k)=\operatorname{pal}_{w}(k) ; \operatorname{pal}_{w}^{e}: 2 \mathbb{N} \rightarrow \mathbb{N}, \operatorname{pal}_{w}^{e}(k)=\operatorname{pal}_{w}(k)2N+1→N,palwo(k)=palw(k);palwe:2N→N,palwe(k)=palw(k).
These functions have a trapezoidal form for short words; nevertheless, this is not true in general, as the following examples show.
Example 2 The word w 1 = 1010 5 1 2 0 7 10 w 1 = 1010 5 1 2 0 7 10 w_(1)=1010^(5)1^(2)0^(7)10w_{1}=1010^{5} 1^{2} 0^{7} 10w1=10105120710 with | w 1 | = 19 w 1 = 19 |w_(1)|=19\left|w_{1}\right|=19|w1|=19 has pal w 1 o ( 1 ) = 2 pal w 1 o ( 1 ) = 2 pal_(w_(1))^(o)(1)=2\operatorname{pal}_{w_{1}}^{o}(1)=2palw1o(1)=2, pal w 1 O ( 3 ) = 3 , pal w 1 O ( 5 ) = 1 , pal w 1 O ( 7 ) = 2 , pal w 1 O ( 9 ) = 1 . pal w 1 O ( 3 ) = 3 , pal w 1 O ( 5 ) = 1 , pal w 1 O ( 7 ) = 2 , pal w 1 O ( 9 ) = 1 . pal_(w_(1))^(O)(3)=3,pal_(w_(1))^(O)(5)=1,pal_(w_(1))^(O)(7)=2,pal_(w_(1))^(O)(9)=1.quad\operatorname{pal}_{w_{1}}^{O}(3)=3, \operatorname{pal}_{w_{1}}^{O}(5)=1, \operatorname{pal}_{w_{1}}^{O}(7)=2, \operatorname{pal}_{w_{1}}^{O}(9)=1 . \quadpalw1O(3)=3,palw1O(5)=1,palw1O(7)=2,palw1O(9)=1. (see Fig. 1.)
Example 3 The word w 2 = 1 4 0 6 10 8 1 2 0 w 2 = 1 4 0 6 10 8 1 2 0 w_(2)=1^(4)0^(6)10^(8)1^(2)0w_{2}=1^{4} 0^{6} 10^{8} 1^{2} 0w2=1406108120 with | w 2 | = 22 w 2 = 22 |w_(2)|=22\left|w_{2}\right|=22|w2|=22 has pal w 2 e ( 2 ) = 2 pal w 2 e ( 2 ) = 2 pal_(w_(2))^(e)(2)=2\mathrm{pal}_{w_{2}}^{e}(2)=2palw2e(2)=2, pal w 2 e ( 4 ) = 3 , pal w 2 e ( 6 ) = 1 , pal w 2 e ( 8 ) = 2 , pal w 2 e ( 10 ) = 1 . pal w 2 e ( 4 ) = 3 , pal w 2 e ( 6 ) = 1 , pal w 2 e ( 8 ) = 2 , pal w 2 e ( 10 ) = 1 . pal_(w_(2))^(e)(4)=3,pal_(w_(2))^(e)(6)=1,pal_(w_(2))^(e)(8)=2,pal_(w_(2))^(e)(10)=1.quad\operatorname{pal}_{w_{2}}^{e}(4)=3, \operatorname{pal}_{w_{2}}^{e}(6)=1, \operatorname{pal}_{w_{2}}^{e}(8)=2, \operatorname{pal}_{w_{2}}^{e}(10)=1 . \quadpalw2e(4)=3,palw2e(6)=1,palw2e(8)=2,palw2e(10)=1. (see Fig. 1.)
REMARK 2 The palindrome complexity for infinite words is not nondecreasing, as the usual complexity function is. Indeed, we can continue the word in Example 2 with 11001100 … 11001100 … 11001100 dots11001100 \ldots11001100…, and its odd palindrome complexity function will be as that for w 1 w 1 w_(1)w_{1}w1, and then equal to 0 for k ≥ 11 k ≥ 11 k >= 11k \geq 11k≥11. Similarly, we can continue w 2 w 2 w_(2)w_{2}w2 in Example 3 with 1010 … 1010 … 1010 dots1010 \ldots1010… to obtain an infinite word with the even palindrome complexity of w 2 w 2 w_(2)w_{2}w2 till k = 10 k = 10 k=10k=10k=10 and equal to 0 for k ≥ 12 k ≥ 12 k >= 12k \geq 12k≥12.

4 Average number of palindromes

We consider an alphabet A A AAA with q ≥ 2 q ≥ 2 q >= 2q \geq 2q≥2 letters.
Definition 1 We define the total palindrome complexity P P PPP by
(8) P ( w ) = ∑ n = 1 | w | pal w ( n ) (8) P ( w ) = ∑ n = 1 | w |   pal w ( n ) {:(8)P(w)=sum_(n=1)^(|w|)pal_(w)(n):}\begin{equation*} P(w)=\sum_{n=1}^{|w|} \operatorname{pal}_{w}(n) \tag{8} \end{equation*}(8)P(w)=∑n=1|w|palw(n)
where w w www is a word of length | w | | w | |w||w||w|, and pal w ( n ) pal w ( n ) pal_(w)(n)\operatorname{pal}_{w}(n)palw(n) denotes the number of distinct palindromes of length n n nnn which are nonempty subwords of w w www.
Because the set of the nonempty palindromes in w w www is denoted by PAL ( w w www ), we can write also P ( w ) = card ( PAL ( w ) ) P ( w ) = card ( PAL ( w ) ) P(w)=card(PAL(w))P(w)=\operatorname{card}(\operatorname{PAL}(w))P(w)=card(PAL(w)).
Definition 2 The average number of palindromes M q ( n ) M q ( n ) M_(q)(n)M_{q}(n)Mq(n) contained in all words of length n n nnn is defined by
(9) M q ( n ) = ∑ w ∈ A n P ( w ) q n . (9) M q ( n ) = ∑ w ∈ A n   P ( w ) q n . {:(9)M_(q)(n)=(sum_(w inA^(n))P(w))/(q^(n)).:}\begin{equation*} M_{q}(n)=\frac{\sum_{w \in A^{n}} P(w)}{q^{n}} . \tag{9} \end{equation*}(9)Mq(n)=∑w∈AnP(w)qn.
We can give the following upper estimate for M q ( n ) M q ( n ) M_(q)(n)M_{q}(n)Mq(n).
Theorem 2 For n ∈ N n ∈ N n inNn \in \mathbb{N}n∈N, the average number of palindromes contained in the words of length n n nnn satisfies the inequalities
M q ( n ) ≤ q − ( n − 1 ) / 2 ( q + 3 ) + 2 n ( q − 1 ) + q 3 − 2 q 2 − 2 q − 1 ( q − 1 ) 2 , for n odd , (10) M q ( n ) ≤ q − n / 2 ( 3 q + 1 ) + 2 n ( q − 1 ) + q 3 − 2 q 2 − 2 q − 1 ( q − 1 ) 2 , for n even . M q ( n ) ≤ q − ( n − 1 ) / 2 ( q + 3 ) + 2 n ( q − 1 ) + q 3 − 2 q 2 − 2 q − 1 ( q − 1 ) 2 ,  for  n  odd  , (10) M q ( n ) ≤ q − n / 2 ( 3 q + 1 ) + 2 n ( q − 1 ) + q 3 − 2 q 2 − 2 q − 1 ( q − 1 ) 2 ,  for  n  even  . {:[M_(q)(n) <= (q^(-(n-1)//2)(q+3)+2n(q-1)+q^(3)-2q^(2)-2q-1)/((q-1)^(2))","" for "n" odd "","],[(10)M_(q)(n) <= (q^(-n//2)(3q+1)+2n(q-1)+q^(3)-2q^(2)-2q-1)/((q-1)^(2))","" for "n" even ".]:}\begin{align*} & M_{q}(n) \leq \frac{q^{-(n-1) / 2}(q+3)+2 n(q-1)+q^{3}-2 q^{2}-2 q-1}{(q-1)^{2}}, \text { for } n \text { odd }, \\ & M_{q}(n) \leq \frac{q^{-n / 2}(3 q+1)+2 n(q-1)+q^{3}-2 q^{2}-2 q-1}{(q-1)^{2}}, \text { for } n \text { even } . \tag{10} \end{align*}Mq(n)≤q−(n−1)/2(q+3)+2n(q−1)+q3−2q2−2q−1(q−1)2, for n odd ,(10)Mq(n)≤q−n/2(3q+1)+2n(q−1)+q3−2q2−2q−1(q−1)2, for n even .
Proof. We have
∑ w ∈ A n P ( w ) = ∑ w ∈ A n ∑ π ∈ PAL ( w ) 1 = ∑ w ∈ A n ∑ k = 1 n ∑ π ∈ PAL ( w ) ∩ A k 1 = ∑ w ∈ A n ∑ π ∈ PAL ( w ) ∩ A 1 1 + ∑ k = 2 n ∑ π ∈ PAL k ( A ) ∑ w ∈ A n π ∈ PAL ( w ) ∩ A k 1 , ∑ w ∈ A n   P ( w ) = ∑ w ∈ A n   ∑ π ∈ PAL ( w )   1 = ∑ w ∈ A n   ∑ k = 1 n   ∑ π ∈ PAL ( w ) ∩ A k   1 = ∑ w ∈ A n   ∑ π ∈ PAL ( w ) ∩ A 1   1 + ∑ k = 2 n   ∑ π ∈ PAL k ( A )   ∑ w ∈ A n π ∈ PAL ( w ) ∩ A k   1 , {:[sum_(w inA^(n))P(w)=sum_(w inA^(n))sum_(pi in PAL(w))1=sum_(w inA^(n))sum_(k=1)^(n)sum_(pi in PAL(w)nnA^(k))1],[=sum_(w inA^(n))sum_(pi in PAL(w)nnA^(1))1+sum_(k=2)^(n)sum_(pi inPAL_(k)(A))sum_({:[w inA^(n)],[pi in PAL(w)nnA^(k)]:})1","]:}\begin{aligned} \sum_{w \in A^{n}} P(w) & =\sum_{w \in A^{n}} \sum_{\pi \in \operatorname{PAL}(w)} 1=\sum_{w \in A^{n}} \sum_{k=1}^{n} \sum_{\pi \in \operatorname{PAL}(w) \cap A^{k}} 1 \\ & =\sum_{w \in A^{n}} \sum_{\pi \in \operatorname{PAL}(w) \cap A^{1}} 1+\sum_{k=2}^{n} \sum_{\pi \in \operatorname{PAL}_{k}(A)} \sum_{\substack{w \in A^{n} \\ \pi \in \operatorname{PAL}(w) \cap A^{k}}} 1, \end{aligned}∑w∈AnP(w)=∑w∈An∑π∈PAL(w)1=∑w∈An∑k=1n∑π∈PAL(w)∩Ak1=∑w∈An∑π∈PAL(w)∩A11+∑k=2n∑π∈PALk(A)∑w∈Anπ∈PAL(w)∩Ak1,
and
(11) ∑ w ∈ A n ∑ π ∈ PAL ( w ) ∩ A 1 1 ≤ q q n = q n + 1 (11) ∑ w ∈ A n   ∑ π ∈ PAL ( w ) ∩ A 1   1 ≤ q q n = q n + 1 {:(11)sum_(w inA^(n))sum_(pi in PAL(w)nnA^(1))1 <= qq^(n)=q^(n+1):}\begin{equation*} \sum_{w \in A^{n}} \sum_{\pi \in \operatorname{PAL}(w) \cap A^{1}} 1 \leq q q^{n}=q^{n+1} \tag{11} \end{equation*}(11)∑w∈An∑π∈PAL(w)∩A11≤qqn=qn+1
For a fixed palindrome π π pi\piπ, with | π | = k | π | = k |pi|=k|\pi|=k|π|=k, the number of the words of length n n nnn in which it appears as a subword at position i ( 1 ≤ i ≤ n − k + 1 ) i ( 1 ≤ i ≤ n − k + 1 ) i(1 <= i <= n-k+1)i(1 \leq i \leq n-k+1)i(1≤i≤n−k+1) is q n − k q n − k q^(n-k)q^{n-k}qn−k. But the position i i iii is arbitrary, so that there are at most ( n − k + 1 ) q n − k ( n − k + 1 ) q n − k (n-k+1)q^(n-k)(n-k+1) q^{n-k}(n−k+1)qn−k words in which π π pi\piπ is a subword, these words being not necessarily distinct. It follows that
∑ w ∈ A n P ( w ) ≤ q n + 1 + ∑ k = 2 n ∑ π ∈ PAL k ( A ) ( n − k + 1 ) q n − k ∑ w ∈ A n   P ( w ) ≤ q n + 1 + ∑ k = 2 n   ∑ π ∈ PAL k ( A )   ( n − k + 1 ) q n − k sum_(w inA^(n))P(w) <= q^(n+1)+sum_(k=2)^(n)sum_(pi inPAL_(k)(A))(n-k+1)q^(n-k)\sum_{w \in A^{n}} P(w) \leq q^{n+1}+\sum_{k=2}^{n} \sum_{\pi \in \mathrm{PAL}_{k}(A)}(n-k+1) q^{n-k}∑w∈AnP(w)≤qn+1+∑k=2n∑π∈PALk(A)(n−k+1)qn−k
The number of the palindromes of length k k kkk is q ⌈ k / 2 ⌉ q ⌈ k / 2 ⌉ q^(|~k//2~|)q^{\lceil k / 2\rceil}q⌈k/2⌉, therefore
∑ w ∈ A n P ( w ) ≤ q n + 1 + ∑ k = 2 n ( n − k + 1 ) q n − k + ⌈ k / 2 ⌉ ∑ w ∈ A n   P ( w ) ≤ q n + 1 + ∑ k = 2 n   ( n − k + 1 ) q n − k + ⌈ k / 2 ⌉ sum_(w inA^(n))P(w) <= q^(n+1)+sum_(k=2)^(n)(n-k+1)q^(n-k+|~k//2~|)\sum_{w \in A^{n}} P(w) \leq q^{n+1}+\sum_{k=2}^{n}(n-k+1) q^{n-k+\lceil k / 2\rceil}∑w∈AnP(w)≤qn+1+∑k=2n(n−k+1)qn−k+⌈k/2⌉
and M q ( n ) ≤ q + ∑ k = 2 n ( n − k + 1 ) q − k + ⌈ k / 2 ⌉ M q ( n ) ≤ q + ∑ k = 2 n   ( n − k + 1 ) q − k + ⌈ k / 2 ⌉ M_(q)(n) <= q+sum_(k=2)^(n)(n-k+1)q^(-k+|~k//2~|)M_{q}(n) \leq q+\sum_{k=2}^{n}(n-k+1) q^{-k+\lceil k / 2\rceil}Mq(n)≤q+∑k=2n(n−k+1)q−k+⌈k/2⌉.
We split the sum according to k = 2 j , j = 1 , … , ⌊ n / 2 ⌋ k = 2 j , j = 1 , … , ⌊ n / 2 ⌋ k=2j,j=1,dots,|__ n//2__|k=2 j, j=1, \ldots,\lfloor n / 2\rfloork=2j,j=1,…,⌊n/2⌋, respectively k = 2 j + 1 k = 2 j + 1 k=2j+1k=2 j+1k=2j+1, j = 1 , … , ⌊ ( n − 1 ) / 2 ⌋ j = 1 , … , ⌊ ( n − 1 ) / 2 ⌋ j=1,dots,|__(n-1)//2__|j=1, \ldots,\lfloor(n-1) / 2\rfloorj=1,…,⌊(n−1)/2⌋, and obtain
M q ( n ) ≤ q + ∑ j = 1 ⌊ n / 2 ⌋ ( n − 2 j + 1 ) q − j + ∑ j = 1 ⌊ ( n − 1 ) / 2 ⌋ ( n − 2 j ) q − j . M q ( n ) ≤ q + ∑ j = 1 ⌊ n / 2 ⌋   ( n − 2 j + 1 ) q − j + ∑ j = 1 ⌊ ( n − 1 ) / 2 ⌋   ( n − 2 j ) q − j . M_(q)(n) <= q+sum_(j=1)^(|__ n//2__|)(n-2j+1)q^(-j)+sum_(j=1)^(|__(n-1)//2__|)(n-2j)q^(-j).M_{q}(n) \leq q+\sum_{j=1}^{\lfloor n / 2\rfloor}(n-2 j+1) q^{-j}+\sum_{j=1}^{\lfloor(n-1) / 2\rfloor}(n-2 j) q^{-j} .Mq(n)≤q+∑j=1⌊n/2⌋(n−2j+1)q−j+∑j=1⌊(n−1)/2⌋(n−2j)q−j.
Making use of ∑ j = 1 s q − j = ( 1 − q − s ) / ( q − 1 ) ∑ j = 1 s   q − j = 1 − q − s / ( q − 1 ) sum_(j=1)^(s)q^(-j)=(1-q^(-s))//(q-1)\sum_{j=1}^{s} q^{-j}=\left(1-q^{-s}\right) /(q-1)∑j=1sq−j=(1−q−s)/(q−1) and ∑ j = 1 s j q − j = ( q − q 1 − s ( s + 1 ) + s q − s ) / ( q − 1 ) 2 ∑ j = 1 s   j q − j = q − q 1 − s ( s + 1 ) + s q − s / ( q − 1 ) 2 sum_(j=1)^(s)jq^(-j)=(q-q^(1-s)(s+1)+:}{:sq^(-s))//(q-1)^(2)\sum_{j=1}^{s} j q^{-j}=\left(q-q^{1-s}(s+1)+\right. \left.s q^{-s}\right) /(q-1)^{2}∑j=1sjq−j=(q−q1−s(s+1)+sq−s)/(q−1)2, it follows that M q ( n ) M q ( n ) M_(q)(n)M_{q}(n)Mq(n) satisfies the inequalities in (10).
Corollary 1 The following inequality holds
(12) lim sup n → ∞ M q ( n ) n ≤ 2 q − 1 . (12) lim sup n → ∞   M q ( n ) n ≤ 2 q − 1 . {:(12)l i m   s u p_(n rarr oo)(M_(q)(n))/(n) <= (2)/(q-1).:}\begin{equation*} \limsup _{n \rightarrow \infty} \frac{M_{q}(n)}{n} \leq \frac{2}{q-1} . \tag{12} \end{equation*}(12)lim supn→∞Mq(n)n≤2q−1.
Proof.
lim sup n → ∞ M q ( n ) n = max { lim sup n → ∞ M q ( 2 n + 1 ) 2 n + 1 , lim sup n → ∞ M q ( 2 n ) 2 n } ≤ max { lim n → ∞ ( q − n ( q + 3 ) + 2 ( 2 n + 1 ) ( q − 1 ) + q 3 − 2 q 2 − 2 q − 1 ( q − 1 ) 2 ) 1 2 n + 1 lim n → ∞ ( q − n ( 3 q + 1 ) + 4 n ( q − 1 ) + q 3 − 2 q 2 − 2 q − 1 ( q − 1 ) 2 ) 1 2 n } = 2 q − 1 lim sup n → ∞   M q ( n ) n = max lim sup n → ∞   M q ( 2 n + 1 ) 2 n + 1 , lim sup n → ∞   M q ( 2 n ) 2 n ≤ max lim n → ∞   q − n ( q + 3 ) + 2 ( 2 n + 1 ) ( q − 1 ) + q 3 − 2 q 2 − 2 q − 1 ( q − 1 ) 2 1 2 n + 1 lim n → ∞   q − n ( 3 q + 1 ) + 4 n ( q − 1 ) + q 3 − 2 q 2 − 2 q − 1 ( q − 1 ) 2 1 2 n = 2 q − 1 {:[l i m   s u p_(n rarr oo)(M_(q)(n))/(n)=max{l i m   s u p_(n rarr oo)(M_(q)(2n+1))/(2n+1),l i m   s u p_(n rarr oo)(M_(q)(2n))/(2n)}],[ <= max{lim_(n rarr oo)((q^(-n)(q+3)+2(2n+1)(q-1)+q^(3)-2q^(2)-2q-1)/((q-1)^(2)))(1)/(2n+1):}],[{:lim_(n rarr oo)((q^(-n)(3q+1)+4n(q-1)+q^(3)-2q^(2)-2q-1)/((q-1)^(2)))(1)/(2n)}=(2)/(q-1)]:}\begin{aligned} \limsup _{n \rightarrow \infty} & \frac{M_{q}(n)}{n}=\max \left\{\limsup _{n \rightarrow \infty} \frac{M_{q}(2 n+1)}{2 n+1}, \limsup _{n \rightarrow \infty} \frac{M_{q}(2 n)}{2 n}\right\} \\ \leq & \max \left\{\lim _{n \rightarrow \infty}\left(\frac{q^{-n}(q+3)+2(2 n+1)(q-1)+q^{3}-2 q^{2}-2 q-1}{(q-1)^{2}}\right) \frac{1}{2 n+1}\right. \\ & \left.\lim _{n \rightarrow \infty}\left(\frac{q^{-n}(3 q+1)+4 n(q-1)+q^{3}-2 q^{2}-2 q-1}{(q-1)^{2}}\right) \frac{1}{2 n}\right\}=\frac{2}{q-1} \end{aligned}lim supn→∞Mq(n)n=max{lim supn→∞Mq(2n+1)2n+1,lim supn→∞Mq(2n)2n}≤max{limn→∞(q−n(q+3)+2(2n+1)(q−1)+q3−2q2−2q−1(q−1)2)12n+1limn→∞(q−n(3q+1)+4n(q−1)+q3−2q2−2q−1(q−1)2)12n}=2q−1
We are interested in finding how large is the average number of palindromes contained in the words of length n n nnn compared to the length n n nnn. The numerical estimations done for small values of n n nnn show that M q ( n ) M q ( n ) M_(q)(n)M_{q}(n)Mq(n) is comparable to n n nnn, but Corollary 1 allows us to show that for q ≥ 4 q ≥ 4 q >= 4q \geq 4q≥4 this does not hold.
Corollary 2 For an alphabet with q ≥ 4 q ≥ 4 q >= 4q \geq 4q≥4 letters,
(13) lim sup n → ∞ M q ( n ) n < 1 . (13) lim sup n → ∞   M q ( n ) n < 1 . {:(13)l i m   s u p_(n rarr oo)(M_(q)(n))/(n) < 1.:}\begin{equation*} \limsup _{n \rightarrow \infty} \frac{M_{q}(n)}{n}<1 . \tag{13} \end{equation*}(13)lim supn→∞Mq(n)n<1.
In the proof of Theorem 2 we have used the rough inequality (11), which was sufficient to prove the result. In fact, it is not difficult to calculate exactly
(14) S n , p = ∑ w ∈ A n ∑ π ∈ PAL ( w ) ∩ A p 1 for p = 1 , 2 . (14) S n , p = ∑ w ∈ A n   ∑ π ∈ PAL ( w ) ∩ A p   1  for  p = 1 , 2 . {:(14)S_(n,p)=sum_(w inA^(n))sum_(pi inPAL(w)nnA^(p))1" for "p=1","2.:}\begin{equation*} S_{n, p}=\sum_{w \in A^{n}} \sum_{\pi \in \mathrm{PAL}(w) \cap A^{p}} 1 \text { for } p=1,2 . \tag{14} \end{equation*}(14)Sn,p=∑w∈An∑π∈PAL(w)∩Ap1 for p=1,2.
This result has intrinsic importance.
Theorem 3 The number of occurrences of the palindromes of length 1, respectively 2 , in all words of length n n nnn (counted once if a palindrome appears in a word, and once again if it appears in another one) is given by
(15) S n , 1 = q n + 1 − q ( q − 1 ) n , (15) S n , 1 = q n + 1 − q ( q − 1 ) n , {:(15)S_(n,1)=q^(n+1)-q(q-1)^(n)",":}\begin{equation*} S_{n, 1}=q^{n+1}-q(q-1)^{n}, \tag{15} \end{equation*}(15)Sn,1=qn+1−q(q−1)n,
respectively by
S n , 2 = q n + 1 − q ( q − 1 ) q 2 + q − 3 ( ( q − 1 + q 2 + q − 3 2 ) n + 2 (16) − ( q − 1 − q 2 + q − 3 2 ) n + 2 ) S n , 2 = q n + 1 − q ( q − 1 ) q 2 + q − 3 q − 1 + q 2 + q − 3 2 n + 2 (16) − q − 1 − q 2 + q − 3 2 n + 2 {:[S_(n,2)=q^(n+1)-(q)/((q-1)sqrt(q^(2)+q-3))(((q-1+sqrt(q^(2)+q-3))/(2))^(n+2):}],[(16){:-((q-1-sqrt(q^(2)+q-3))/(2))^(n+2))]:}\begin{align*} S_{n, 2}= & q^{n+1}-\frac{q}{(q-1) \sqrt{q^{2}+q-3}}\left(\left(\frac{q-1+\sqrt{q^{2}+q-3}}{2}\right)^{n+2}\right. \\ & \left.-\left(\frac{q-1-\sqrt{q^{2}+q-3}}{2}\right)^{n+2}\right) \tag{16} \end{align*}Sn,2=qn+1−q(q−1)q2+q−3((q−1+q2+q−32)n+2(16)−(q−1−q2+q−32)n+2)
Proof. We use Iverson's convention [11]
[ α ] = { 1 , if α is true 0 , if α is false [ α ] = 1 ,  if  α  is true  0 ,  if  α  is false  [alpha]={[1","" if "alpha" is true "],[0","" if "alpha" is false "]:}[\alpha]=\left\{\begin{array}{l} 1, \text { if } \alpha \text { is true } \\ 0, \text { if } \alpha \text { is false } \end{array}\right.[α]={1, if α is true 0, if α is false 
and obtain
S n , 1 = ∑ w ∈ A n ∑ a ∈ A [ a in w ] = q ∑ w ∈ A n [ a 1 in w ] S n , 1 = ∑ w ∈ A n   ∑ a ∈ A   [ a  in  w ] = q ∑ w ∈ A n   a 1  in  w S_(n,1)=sum_(w inA^(n))sum_(a in A)[a" in "w]=qsum_(w inA^(n))[a_(1)" in "w]S_{n, 1}=\sum_{w \in A^{n}} \sum_{a \in A}[a \text { in } w]=q \sum_{w \in A^{n}}\left[a_{1} \text { in } w\right]Sn,1=∑w∈An∑a∈A[a in w]=q∑w∈An[a1 in w]
where a 1 a 1 a_(1)a_{1}a1 is a fixed letter of the alphabet A A AAA. Then
S n , 1 = q ∑ w ∈ A n [ a 1 in w ] = q ( q n − ∑ w ∈ A n [ a 1 not in w ] ) = q n + 1 − q ( q − 1 ) n S n , 1 = q ∑ w ∈ A n   a 1  in  w = q q n − ∑ w ∈ A n   a 1 not  in  w = q n + 1 − q ( q − 1 ) n S_(n,1)=qsum_(w inA^(n))[a_(1)" in "w]=q(q^(n)-sum_(w inA^(n))[a_(1)not" in "w])=q^(n+1)-q(q-1)^(n)S_{n, 1}=q \sum_{w \in A^{n}}\left[a_{1} \text { in } w\right]=q\left(q^{n}-\sum_{w \in A^{n}}\left[a_{1} \operatorname{not} \text { in } w\right]\right)=q^{n+1}-q(q-1)^{n}Sn,1=q∑w∈An[a1 in w]=q(qn−∑w∈An[a1not in w])=qn+1−q(q−1)n
We proceed similarly to calculate S n , 2 = ∑ w ∈ A n ∑ π ∈ PAL ( w ) ∩ A 2 1 S n , 2 = ∑ w ∈ A n   ∑ π ∈ PAL ( w ) ∩ A 2   1 S_(n,2)=sum_(w inA^(n))sum_(pi in PAL(w)nnA^(2))1S_{n, 2}=\sum_{w \in A^{n}} \sum_{\pi \in \operatorname{PAL}(w) \cap A^{2}} 1Sn,2=∑w∈An∑π∈PAL(w)∩A21 and obtain
S n , 2 = ∑ w ∈ A n ∑ a ∈ A [ a a in w ] = q ∑ w ∈ A n [ a 1 a 1 in w ] S n , 2 = ∑ w ∈ A n   ∑ a ∈ A   [ a a  in  w ] = q ∑ w ∈ A n   a 1 a 1  in  w S_(n,2)=sum_(w inA^(n))sum_(a in A)[aa" in "w]=qsum_(w inA^(n))[a_(1)a_(1)" in "w]S_{n, 2}=\sum_{w \in A^{n}} \sum_{a \in A}[a a \text { in } w]=q \sum_{w \in A^{n}}\left[a_{1} a_{1} \text { in } w\right]Sn,2=∑w∈An∑a∈A[aa in w]=q∑w∈An[a1a1 in w]
where a 1 a 1 a_(1)a_{1}a1 is again a fixed letter of the alphabet A A AAA. We denote φ ( n ) := ∑ w ∈ A n [ a 1 a 1 φ ( n ) := ∑ w ∈ A n   a 1 a 1 varphi(n):=sum_(w inA^(n))[a_(1)a_(1):}\varphi(n):=\sum_{w \in A^{n}}\left[a_{1} a_{1}\right.φ(n):=∑w∈An[a1a1 in w ] w ] w]w]w], for which φ ( 2 ) = 1 φ ( 2 ) = 1 varphi(2)=1\varphi(2)=1φ(2)=1 and φ ( 3 ) = 2 q − 1 φ ( 3 ) = 2 q − 1 varphi(3)=2q-1\varphi(3)=2 q-1φ(3)=2q−1. It is easier to establish a recurrence formula for ψ ( n ) = q n − φ ( n ) = ∑ w ∈ A n [ a 1 a 1 ψ ( n ) = q n − φ ( n ) = ∑ w ∈ A n   a 1 a 1 psi(n)=q^(n)-varphi(n)=sum_(w inA^(n))[a_(1)a_(1):}\psi(n)=q^{n}-\varphi(n)=\sum_{w \in A^{n}}\left[a_{1} a_{1}\right.ψ(n)=qn−φ(n)=∑w∈An[a1a1 not in w ] w {:w]\left.w\right]w]. The number ψ ( n ) ψ ( n ) psi(n)\psi(n)ψ(n) is obtained from:
  • the number ( q − 1 ) ψ ( n − 1 ) ( q − 1 ) ψ ( n − 1 ) (q-1)psi(n-1)(q-1) \psi(n-1)(q−1)ψ(n−1) of words which do not end in a 1 a 1 a_(1)a_{1}a1 and have not a 1 a 1 a 1 a 1 a_(1)a_(1)a_{1} a_{1}a1a1 in their first n − 1 n − 1 n-1n-1n−1 positions;
  • the number ( q − 1 ) ψ ( n − 2 ) ( q − 1 ) ψ ( n − 2 ) (q-1)psi(n-2)(q-1) \psi(n-2)(q−1)ψ(n−2) of words which end in a 1 a 1 a_(1)a_{1}a1, have the n − 1 n − 1 n-1n-1n−1 position occupied by one of the other q − 1 q − 1 q-1q-1q−1 letters and have not a 1 a 1 a 1 a 1 a_(1)a_(1)a_{1} a_{1}a1a1 in the first n − 2 n − 2 n-2n-2n−2 positions.
It follows that ψ ψ psi\psiψ satisfies the recurrence formula
(17) ψ ( n ) = ( q − 1 ) ( ψ ( n − 1 ) + ψ ( n − 2 ) ) (17) ψ ( n ) = ( q − 1 ) ( ψ ( n − 1 ) + ψ ( n − 2 ) ) {:(17)psi(n)=(q-1)(psi(n-1)+psi(n-2)):}\begin{equation*} \psi(n)=(q-1)(\psi(n-1)+\psi(n-2)) \tag{17} \end{equation*}(17)ψ(n)=(q−1)(ψ(n−1)+ψ(n−2))
with ψ ( 2 ) = q 2 − 1 ψ ( 2 ) = q 2 − 1 psi(2)=q^(2)-1\psi(2)=q^{2}-1ψ(2)=q2−1 and ψ ( 3 ) = q 3 − 2 q + 1 ψ ( 3 ) = q 3 − 2 q + 1 psi(3)=q^(3)-2q+1\psi(3)=q^{3}-2 q+1ψ(3)=q3−2q+1. Its solution is
ψ ( n ) = 1 ( q − 1 ) q 2 + q − 3 ( ( q − 1 + q 2 + q − 3 2 ) n + 2 − ( q − 1 − q 2 + q − 3 2 ) n + 2 ) ψ ( n ) = 1 ( q − 1 ) q 2 + q − 3 q − 1 + q 2 + q − 3 2 n + 2 − q − 1 − q 2 + q − 3 2 n + 2 {:[psi(n)=(1)/((q-1)sqrt(q^(2)+q-3))(((q-1+sqrt(q^(2)+q-3))/(2))^(n+2):}],[{:-((q-1-sqrt(q^(2)+q-3))/(2))^(n+2))]:}\begin{aligned} \psi(n)= & \frac{1}{(q-1) \sqrt{q^{2}+q-3}}\left(\left(\frac{q-1+\sqrt{q^{2}+q-3}}{2}\right)^{n+2}\right. \\ & \left.-\left(\frac{q-1-\sqrt{q^{2}+q-3}}{2}\right)^{n+2}\right) \end{aligned}ψ(n)=1(q−1)q2+q−3((q−1+q2+q−32)n+2−(q−1−q2+q−32)n+2)
and (16) follows from the fact that
(18) S n , 2 = q ( q n − ψ ( n ) ) . (18) S n , 2 = q q n − ψ ( n ) . {:(18)S_(n,2)=q(q^(n)-psi(n)).:}\begin{equation*} S_{n, 2}=q\left(q^{n}-\psi(n)\right) . \tag{18} \end{equation*}(18)Sn,2=q(qn−ψ(n)).
The expression of S n , 2 S n , 2 S_(n,2)S_{n, 2}Sn,2 from (16) allows us to improve Corollary 1.
Corollary 3 The following inequality holds
(19) lim sup n → ∞ M q ( n ) n ≤ q + 1 q ( q − 1 ) . (19) lim sup n → ∞   M q ( n ) n ≤ q + 1 q ( q − 1 ) . {:(19)l i m   s u p_(n rarr oo)(M_(q)(n))/(n) <= (q+1)/(q(q-1)).:}\begin{equation*} \limsup _{n \rightarrow \infty} \frac{M_{q}(n)}{n} \leq \frac{q+1}{q(q-1)} . \tag{19} \end{equation*}(19)lim supn→∞Mq(n)n≤q+1q(q−1).
Proof. Taking into account the inequality
∑ w ∈ A n ∑ π ∈ PAL ( w ) ∩ A 1 1 ≤ q q n = q n + 1 , ∑ w ∈ A n   ∑ π ∈ PAL ( w ) ∩ A 1   1 ≤ q q n = q n + 1 , sum_(w inA^(n))sum_(pi in PAL(w)nnA^(1))1 <= qq^(n)=q^(n+1),\sum_{w \in A^{n}} \sum_{\pi \in \operatorname{PAL}(w) \cap A^{1}} 1 \leq q q^{n}=q^{n+1},∑w∈An∑π∈PAL(w)∩A11≤qqn=qn+1,
and (18), we get
M q ( n ) ≤ 1 q n ( S n , 1 + S n , 2 + ∑ k = 3 n ∑ π ∈ PAL k ( A ) ( n − k + 1 ) q n − k ) ≤ q ( 2 − ψ ( n ) q n ) + ∑ k = 3 n ( n − k + 1 ) q − k + ⌊ ( k + 1 ) / 2 ⌋ . M q ( n ) ≤ 1 q n S n , 1 + S n , 2 + ∑ k = 3 n   ∑ π ∈ PAL k ( A )   ( n − k + 1 ) q n − k ≤ q 2 − ψ ( n ) q n + ∑ k = 3 n   ( n − k + 1 ) q − k + ⌊ ( k + 1 ) / 2 ⌋ . {:[M_(q)(n) <= (1)/(q^(n))(S_(n,1)+S_(n,2)+sum_(k=3)^(n)sum_(pi inPAL_(k)(A))(n-k+1)q^(n-k))],[ <= q(2-(psi(n))/(q^(n)))+sum_(k=3)^(n)(n-k+1)q^(-k+|__(k+1)//2__|).]:}\begin{aligned} M_{q}(n) & \leq \frac{1}{q^{n}}\left(S_{n, 1}+S_{n, 2}+\sum_{k=3}^{n} \sum_{\pi \in \mathrm{PAL}_{k}(A)}(n-k+1) q^{n-k}\right) \\ & \leq q\left(2-\frac{\psi(n)}{q^{n}}\right)+\sum_{k=3}^{n}(n-k+1) q^{-k+\lfloor(k+1) / 2\rfloor} . \end{aligned}Mq(n)≤1qn(Sn,1+Sn,2+∑k=3n∑π∈PALk(A)(n−k+1)qn−k)≤q(2−ψ(n)qn)+∑k=3n(n−k+1)q−k+⌊(k+1)/2⌋.
But 0 < ( q − 1 + q 2 + q − 3 ) / 2 < q 0 < q − 1 + q 2 + q − 3 / 2 < q 0 < (q-1+sqrt(q^(2)+q-3))//2 < q0<\left(q-1+\sqrt{q^{2}+q-3}\right) / 2<q0<(q−1+q2+q−3)/2<q and − 1 < ( q − 1 − q 2 + q − 3 ) / 2 < 0 − 1 < q − 1 − q 2 + q − 3 / 2 < 0 -1 < (q-1-sqrt(q^(2)+q-3))//2 < 0-1<\left(q-1-\sqrt{q^{2}+q-3}\right) / 2<0−1<(q−1−q2+q−3)/2<0 for q ≥ 2 q ≥ 2 q >= 2q \geq 2q≥2, hence lim n → ∞ ψ ( n ) / q n = 0 lim n → ∞   ψ ( n ) / q n = 0 lim_(n rarr oo)psi(n)//q^(n)=0\lim _{n \rightarrow \infty} \psi(n) / q^{n}=0limn→∞ψ(n)/qn=0. Then
lim sup n → ∞ M q ( n ) n ≤ lim n → ∞ 1 n ∑ k = 3 n ( n − k + 1 ) q − k + ⌊ ( k + 1 ) / 2 ⌋ ≤ ∑ k = 3 ∞ q − k + ⌊ ( k + 1 ) / 2 ⌋ = ∑ i = 1 ∞ q − 2 i − 1 + i + 1 + ∑ i = 2 ∞ q − 2 i + i = − 1 q + 2 ∑ i = 1 ∞ q − i = q + 1 q ( q − 1 ) . lim sup n → ∞   M q ( n ) n ≤ lim n → ∞   1 n ∑ k = 3 n   ( n − k + 1 ) q − k + ⌊ ( k + 1 ) / 2 ⌋ ≤ ∑ k = 3 ∞   q − k + ⌊ ( k + 1 ) / 2 ⌋ = ∑ i = 1 ∞   q − 2 i − 1 + i + 1 + ∑ i = 2 ∞   q − 2 i + i = − 1 q + 2 ∑ i = 1 ∞   q − i = q + 1 q ( q − 1 ) . {:[l i m   s u p_(n rarr oo)(M_(q)(n))/(n) <= lim_(n rarr oo)(1)/(n)sum_(k=3)^(n)(n-k+1)q^(-k+|__(k+1)//2__|)],[ <= sum_(k=3)^(oo)q^(-k+|__(k+1)//2__|)=sum_(i=1)^(oo)q^(-2i-1+i+1)+sum_(i=2)^(oo)q^(-2i+i)],[=-(1)/(q)+2sum_(i=1)^(oo)q^(-i)=(q+1)/(q(q-1)).]:}\begin{aligned} \limsup _{n \rightarrow \infty} \frac{M_{q}(n)}{n} & \leq \lim _{n \rightarrow \infty} \frac{1}{n} \sum_{k=3}^{n}(n-k+1) q^{-k+\lfloor(k+1) / 2\rfloor} \\ & \leq \sum_{k=3}^{\infty} q^{-k+\lfloor(k+1) / 2\rfloor}=\sum_{i=1}^{\infty} q^{-2 i-1+i+1}+\sum_{i=2}^{\infty} q^{-2 i+i} \\ & =-\frac{1}{q}+2 \sum_{i=1}^{\infty} q^{-i}=\frac{q+1}{q(q-1)} . \end{aligned}lim supn→∞Mq(n)n≤limn→∞1n∑k=3n(n−k+1)q−k+⌊(k+1)/2⌋≤∑k=3∞q−k+⌊(k+1)/2⌋=∑i=1∞q−2i−1+i+1+∑i=2∞q−2i+i=−1q+2∑i=1∞q−i=q+1q(q−1).
Corollary 4 The inequality (13) holds for q = 3 q = 3 q=3q=3q=3 too.
It seems that (13) holds also for q = 2 q = 2 q=2q=2q=2. Using a computer program we obtained some values for the terms of the sequence M ∗ ( n ) = M 2 ( n ) / n , n ≥ 2 M ∗ ( n ) = M 2 ( n ) / n , n ≥ 2 M^(**)(n)=M_(2)(n)//n,n >= 2M^{*}(n)=M_{2}(n) / n, n \geq 2M∗(n)=M2(n)/n,n≥2. The first values are: M ∗ ( n ) = 1 , n = 2 , … , 7 ; M ∗ ( 8 ) = 0.99750 ; M ∗ ( 9 ) = M ∗ ( n ) = 1 , n = 2 , … , 7 ; M ∗ ( 8 ) = 0.99750 ; M ∗ ( 9 ) = M^(**)(n)=1,n=2,dots,7;M^(**)(8)=0.99750;M^(**)(9)=M^{*}(n)=1, n=2, \ldots, 7 ; M^{*}(8)=0.99750 ; M^{*}(9)=M∗(n)=1,n=2,…,7;M∗(8)=0.99750;M∗(9)= 0.98550 , which were close to 1 . We tried for greater values of n n nnn and get
M ∗ ( 20 ) = 0.89975 , M ∗ ( 21 ) = 0.89002 , M ∗ ( 22 ) = 0.88043 M ∗ ( 23 ) = 0.87101 , M ∗ ( 24 ) = 0.86177 , … , M ∗ ( 30 ) = 0.81064 M ∗ ( 20 ) = 0.89975 , M ∗ ( 21 ) = 0.89002 , M ∗ ( 22 ) = 0.88043 M ∗ ( 23 ) = 0.87101 , M ∗ ( 24 ) = 0.86177 , … , M ∗ ( 30 ) = 0.81064 {:[M^(**)(20)=0.89975",",M^(**)(21)=0.89002",",M^(**)(22)=0.88043],[M^(**)(23)=0.87101",",M^(**)(24)=0.86177","dots",",M^(**)(30)=0.81064]:}\begin{array}{lll} M^{*}(20)=0.89975, & M^{*}(21)=0.89002, & M^{*}(22)=0.88043 \\ M^{*}(23)=0.87101, & M^{*}(24)=0.86177, \ldots, & M^{*}(30)=0.81064 \end{array}M∗(20)=0.89975,M∗(21)=0.89002,M∗(22)=0.88043M∗(23)=0.87101,M∗(24)=0.86177,…,M∗(30)=0.81064
The last value was obtained in a very long time, so for greater values of n n nnn we generated some random words w 1 , w 2 , … , w ℓ w 1 , w 2 , … , w ℓ w_(1),w_(2),dots,w_(ℓ)w_{1}, w_{2}, \ldots, w_{\ell}w1,w2,…,wℓ of length 100 , respectively 200 , 300, 400 and 500 over A = { 0 , 1 } A = { 0 , 1 } A={0,1}A=\{0,1\}A={0,1} and get some roughly approximate values M ∗ ( n ) ≃ ( pal w 1 ( n ) + ⋯ + pal w ℓ ( n ) ) / ℓ M ∗ ( n ) ≃ pal w 1 ( n ) + ⋯ + pal w ℓ ( n ) / ℓ M^(**)(n)≃(pal_(w_(1))(n)+cdots+pal_(w_(ℓ))(n))//ℓM^{*}(n) \simeq\left(\operatorname{pal}_{w_{1}}(n)+\cdots+\operatorname{pal}_{w_{\ell}}(n)\right) / \ellM∗(n)≃(palw1(n)+⋯+palwℓ(n))/ℓ. For ℓ = 200 ℓ = 200 ℓ=200\ell=200ℓ=200 we obtained
M ∗ ( 100 ) ≃ 0.53 , M ∗ ( 200 ) ≃ 0.39 , M ∗ ( 300 ) ≃ 0.32 M ∗ ( 400 ) ≃ 0.29 , M ∗ ( 500 ) ≃ 0.26 M ∗ ( 100 ) ≃ 0.53 , M ∗ ( 200 ) ≃ 0.39 , M ∗ ( 300 ) ≃ 0.32 M ∗ ( 400 ) ≃ 0.29 , M ∗ ( 500 ) ≃ 0.26 {:[M^(**)(100)≃0.53","quadM^(**)(200)≃0.39","quadM^(**)(300)≃0.32],[M^(**)(400)≃0.29","quadM^(**)(500)≃0.26]:}\begin{aligned} & M^{*}(100) \simeq 0.53, \quad M^{*}(200) \simeq 0.39, \quad M^{*}(300) \simeq 0.32 \\ & M^{*}(400) \simeq 0.29, \quad M^{*}(500) \simeq 0.26 \end{aligned}M∗(100)≃0.53,M∗(200)≃0.39,M∗(300)≃0.32M∗(400)≃0.29,M∗(500)≃0.26
This method allows us to obtain the previous exactly computed values M ∗ ( 20 ) M ∗ ( 20 ) M^(**)(20)M^{*}(20)M∗(20), … , M ∗ ( 30 ) … , M ∗ ( 30 ) dots,M^(**)(30)\ldots, M^{*}(30)…,M∗(30) with two exact digits. These numerical results allow us to formulate the following
Conjecture The sequence M q ( n ) / n M q ( n ) / n M_(q)(n)//nM_{q}(n) / nMq(n)/n is strictly decreasing for n ≥ 7 n ≥ 7 n >= 7n \geq 7n≥7.
Acknowledgements. The first and the third author acknowledge the support of the Romanian Academy (Grant 13 GAR/2006) and the kind hospitality of Rényi Institute in the frame of the cooperation program between the Romanian Academy and the Hungarian Academy of Sciences.

References

[1] J.-P. Allouche, M. Baake, J. Cassaigne and D. Damanik, Palindrome complexity, Theoret. Comput. Sci., 292 (2003), 9-31.
[2] M.-C. Anisiu and J. Cassaigne, Properties of the complexity function for finite words, Rev. Anal. Num. Théor. Approx., 33 (2004), 123-139.
[3] J.-P. Borel and C. Reutenauer, Palindromic factors of billiard words, Theoret. Comput. Sci., 340 (2005), 334-348.
[4] N.G. De Bruijn, A combinatorial problem, Nederl. Akad. Wetensch. Proc., 49 (1946), 758-764 = Indag. Math., 8 (1946), 461-467.
[5] A. Ehrenfeucht, K.P. Lee and G. Rozenberg, Subword complexities of various classes of deterministic developmental languages without interactions, Theoret. Comput. Sci., 1 (1975), 59-75.
[6] C. Flye Sainte-Marie, Solution to question nr. 48, l'Intermédiaire des Mathématiciens, 1 (1894), 107-110.
[7] H. Fredricksen, A survey of full length nonlinear shift register cycle algorithms, SIAM Review, 24 (1982), 195-221.
[8] R.A. Games, A generalized recursive construction for De Bruijn sequences, IEEE Trans. Inform. Theory, 29 (1983), 843-850.
[9] M. Giel-Pietraszuk, M. Hoffmann, S. Dolecka, J. Rychlewski and J. Barciszewski, Palindromes in proteins, J. Protein Chem., 22 (2003), 109-113.
[10] I.J. Good, Normal recurring decimals, J. London Math. Soc., 21 (1946), 167-169.
[11] R.L. Graham, D.E. Knuth and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd edition (Reading, Massachusetts: Addison-Wesley), 1994.
[12] M. Heinz, Zur Teilwortkomplexität für Wörter und Folgen über einem endlichen Alphabet, EIK, 13 (1977), 27-38.
[13] A. de Luca, On the combinatorics of finite words, Theoret. Comput. Sci., 218 (1999), 13-39.
[14] A. de Luca and Al. de Luca, Combinatorial properties of Sturmian palindromes, Int. J. Found. Comput. Sci., 17 (2006), 557-573.
[15] F. Levé and P. Séébold, Proof of a conjecture on word complexity, Bull. Belg. Math. Soc. Simon Stevin, 8 (2001), 277-291.
[16] M.H. Martin, A problem in arrangements, Bull. American Math. Soc., 40 (1934), 859-864.
[17] M. Morse and G.A. Hedlund, Symbolic dynamics, Amer. J. Math., 60 (1938), 815-866.
[18] A. Ralston, A new memoryless algorithm for De Bruijn sequences, J. Algorithms, 2 (1981), 50-62.
2006

Related Posts