login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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)
9
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 (list; graph; refs; listen; history; text; internal format)
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

Table of n, a(n) for n=0..41.

Chuan Guo, J. Shallit, 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 *)

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: A226930 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 26 19:44 EDT 2019. Contains 323597 sequences. (Running on oeis4.)