A139210 Number of recursively 3-palindromic words of length n over an alphabet of 2 letters.

2, 2, 4, 4, 8, 4, 8, 8, 16, 16, 32, 16, 32, 16, 64, 32, 64, 16, 32, 32, 64, 64, 128, 64, 128, 128, 256, 256, 512, 256, 512, 256, 1024, 512, 1024, 256, 512, 256, 1024, 512, 2048, 256, 1024, 512, 4096, 2048, 4096, 1024, 2048, 512, 4096, 1024, 2048, 256, 512, 512

Offset

1,1

Comments

We define a word of length n to be recursively 3-palindromic if it is empty, or it is a palindrome and its left third and right third of lengths Floor[n/3] and the remaining middle of length n-2Floor[n/3] are all recursively 3-palindromic.

See the Ji/Wilf reference for the definition of a recursively palindromic sequence. The number of recursively palindromic words of length n over an alphabet of 2 letters is given in A001316.

Links

Table of n, a(n) for n=1..56.

Kathy Q. Ji and Herbert S. Wilf, Extreme Palindromes, Amer. Math. Monthly 115 (2008), 447-451.

Formula

a(1)=2, a(2)=2 and, for n>2, a(n)=a([n/3])*a(n-2[n/3])., where [...] denotes the floor or greatest integer function.

Example

{0,0,0,0,0,0,0}, {0,0,0,1,0,0,0}, {0,0,1,0,1,0,0}, {0,0,1,1,1,0,0}, {1,1,0,0,0,1,1}, {1,1,0,1,0,1,1}, {1,1,1,0,1,1,1}, {1,1,1,1,1,1,1} are the eight recursively 3-palindromic words of length seven over an alphabet of two letters, so a(7)=8.

Crossrefs

Cf. A001316.

Sequence in context: A385435 A292253 A115209 * A300123 A175359 A336125

Adjacent sequences: A139207 A139208 A139209 * A139211 A139212 A139213

Keyword

nonn

Author

John W. Layman, Jun 06 2008

Status

approved