A007055 Let S denote the palindromes in the language {0,1}*; a(n) = number of words of length n in the language SS. (Formerly M1124)

1, 2, 4, 8, 16, 32, 52, 100, 160, 260, 424, 684, 1036, 1640, 2552, 3728, 5920, 8672, 13408, 19420, 30136, 42736, 66840, 94164, 145900, 204632, 317776, 441764, 685232, 950216, 1469632, 2031556, 3139360, 4323888, 6675904, 9174400, 14139496, 19398584, 29864888, 40891040, 62882680, 85983152

Offset

0,2

Comments

Number of words in {0,1}* of length n that are rotations of their reversals. - David W. Wilson, Jan 01 2012

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Chai Wah Wu, Table of n, a(n) for n = 0..6617

Chuan Guo, J. Shallit, and A. M. Shur, On the Combinatorics of Palindromes and Antipalindromes, arXiv preprint arXiv:1503.09112 [cs.FL], 2015.

R. Kemp, On the number of words in the language {w in Sigma* | w = w^R }^2, Discrete Math., 40 (1982), 225-234.

Formula

a(n) = A187272(n) - Sum_{d|n, d<n} phi(n/d)*a(d). - Andrew Howroyd, Mar 29 2016

Example

S = {e, 0, 1, 11, 101, 111, 1001, 1111, 10001, 10101, 11011, 11111, 100001, ...}, where e is the empty word.
SS contains all words in {0,1}* of length <= 5, but at length 6 is missing the 12 words { 001011, 001101, 010011, 010110, 011001, 011010, 100101, 100110, 101001, 101100, 110010, 110100 }.
In more detail: All words in SS of length 6 have one of the following 6 patterns: abccba, abbacc, aabccb, abcbad, abacdc, abcdcb. This gives a total of 3*(2^3 + 2^4) = 72 = A187272(n) words with some words being counted multiple times as follows: (x6): 000000, 111111; (x3): 010101, 101010; (x2): 001001, 010010, 011011, 100100, 101101, 110110. These are exactly the repetitions of shorter words in SS. Subtracting gives a(6) = 72 - 5*2 - 2*2 - 1*6 = 52.
For length n=7: All words in SS of length 7 have one of the following 7 patterns: abcdcba, abccbad, abcbadd, abbacdc, abacddc, aabcdcb, abcddcb. This gives a total of 7*2^4 = 112 = A187272(n) words with some words being counted multiple times. In particular, the words 0000000 and 1111111 are counted 7 times each so a(7) = 112 - 6*2 = 100. - Information about examples courtesy of Andrew Howroyd, Mar 30 2016

Maple

# A023900:
f:=proc(n) local t0, t1, t2; if n=1 then RETURN(1) else
t0:=1; t1:=ifactors(n); t2:=t1[2]; for i from 1 to nops(t2) do t0:=t0*(1-t2[i][1]); od; RETURN(t0); fi; end;
# A187272, A187273, A187274, A187275:
R:=(a, n)->
expand(simplify( (n/4)*a^(n/2)*( (1+sqrt(a))^2+ (-1)^n*(1-sqrt(a))^2 ) ));
# A007055, A007056, A007057, A007058
F:=(b, n)-> if n=0 then 1 else expand(simplify( add( f(d)*R(b, n/d), d in divisors(n) ) )); fi;
# A007055:
[seq(F(2, n), n=0..60)];

Mathematica

A187272[n_] := A187272[n] = (n/4)*2^(n/2)*((1 + Sqrt[2])^2 + (-1)^n*(1 - Sqrt[2])^2) // Round;
a[n_ /; n <= 5] := 2^n; a[n_] := a[n] = A187272[n] - Sum[n, EulerPhi[n/d] * a[d], {d, Most[Divisors[n]]}];
Table[a[n], {n, 0, 41}] (* Jean-François Alcover, Oct 08 2017, after Andrew Howroyd *)

Prog

(Python)
from functools import lru_cache
from sympy import totient, proper_divisors
@lru_cache(maxsize=None)
def A007055(n): return (n<<(n+1>>1) if n&1 else 3*n<<(n-2>>1))-sum(totient(n//d)*A007055(d) for d in proper_divisors(n, generator=True)) if n else 1 # Chai Wah Wu, Feb 18 2024

Crossrefs

Column 2 of A284873.

For the nonempty words in the language S, see A057148 and A006995.

Cf. A007056-A007058, A023900, A187272-A187275.

Sequence in context: A326751 A297702 A306314 * A175951 A072207 A176718

Adjacent sequences: A007052 A007053 A007054 * A007056 A007057 A007058

Keyword

nonn

Author

N. J. A. Sloane, Mira Bernstein, R. Kemp

Extensions

Entry revised by N. J. A. Sloane, Mar 07 2011

Status

approved