A247000 Maximal number of palindromes in a circular binary word of length n.

1, 2, 4, 6, 7, 9, 10, 12, 13, 15, 16, 18, 19, 21, 23, 24, 26, 28, 29, 31, 33, 34, 36, 38, 39, 41, 43, 44, 46, 48

Offset

1,2

Comments

The word is to be imagined as written around a circle. We only count palindromes of length m with 1 <= m <= n.

Links

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

David Consiglio, Jr., Alternate Python Program

Jamie Simpson, Palindromes in circular words, Theoretical Computer Science, Volume 550, 18 September 2014, Pages 66-78; DOI: 10.1016/j.tcs.2014.07.012.

Formula

Conjectures from Colin Barker, Nov 14 2015: (Start)

a(n) = a(n-1)+a(n-3)-a(n-4) for n>4.

G.f.: x*(x^13-x^12+x^11-x^10+x^9-x^8+x^7-x^6+x^3+2*x^2+x+1) / ((x-1)^2*(x^2+x+1)).

(End)

Example

n      a(n)      Example of a word with a(n) palindromes
1       1       (a)
2       2       (aa)
3       4       (aab)
4       6       (aabb) Palindromes are a,b,aa,bb,abba,baab
5       7       (aaaab)
6       9       (aaaabb)
7       10      (aaaaaab)
8       12      (aaaaaabb)
9       13      (aaaaaaaab)
10      15      (aaaaaaaabb)
11      16      (aaaaaaaaaab)
12      18      (aaaaaaaaaabb)
13      19      (aaaaaaaaaaaab)
14      21      (aaaaaaaaaaaabb)
15      23      (aaaaabaaaabaaab)
16      24      (aaaaaaaaaaaaaabb)
17      26      (aaaaaabaaaaabaaab)
18      28      (aaaaaabaaaaabaaaab)
19      29      (aaaaaaabaaaaaabaaab)
20      31      (aaaaaaabaaaaaabaaaab)
21      33      (aaaaaaabaaaaaabaaaaab)
22      34      (aaaaaaaabaaaaaaabaaaab)
23      36      (aaaaaaaabaaaaaaabaaaaab)
24      38      (aaaaaaaabaaaaaaabaaaaaab)
25      39      (aaaaaaaaabaaaaaaaabaaaaab)
26      41      (aaaaaaaaabaaaaaaaabaaaaaab)
27      43      (aaaaaaaaabaaaaaaaabaaaaaaab)
28      44      (aaaaaaaaaabaaaaaaaaabaaaaaab)
29      46      (aaaaaaaaaabaaaaaaaaabaaaaaaab)
30      48      (aaaaaaaaaabaaaaaaaaabaaaaaaaab)

Prog

(Python)
def A247000(n):
....maxcount = 0
....for i in range(2**(n-1), 2**n):
........s = format(i, '0'+str(n)+'b')
........s, plist = s+s[:-1], []
........for j in range(n):
............for k in range(n):
................t = s[j:j+k+1]
................if t == t[::-1] and not t in plist:
....................plist.append(t)
........if len(plist) > maxcount:
............maxcount = len(plist)
....return maxcount # Chai Wah Wu, Sep 16 2014

Crossrefs

Sequence in context: A289243 A183569 A248612 * A213356 A079393 A047512

Adjacent sequences: A246997 A246998 A246999 * A247001 A247002 A247003

Keyword

nonn,more

Author

N. J. A. Sloane, Sep 15 2014

Extensions

More terms from David Consiglio, Jr., Sep 16 2014

Status

approved