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

%I M1124

%S 1,2,4,8,16,32,52,100,160,260,424,684,1036,1640,2552,3728,5920,8672,

%T 13408,19420,30136,42736,66840,94164,145900,204632,317776,441764,

%U 685232,950216,1469632,2031556,3139360,4323888,6675904,9174400,14139496,19398584,29864888,40891040,62882680,85983152

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

%C Number of words in {0,1}* of length n that are rotations of their reversals. - _David W. Wilson_, Jan 01 2012

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

%H Chuan Guo, J. Shallit, A. M. Shur, <a href="http://arxiv.org/abs/1503.09112">On the Combinatorics of Palindromes and Antipalindromes</a>, arXiv preprint arXiv:1503.09112 [cs.FL], 2015.

%H R. Kemp, <a href="http://dx.doi.org/10.1016/0012-365X(82)90123-6">On the number of words in the language {w in Sigma* | w = w^R }^2</a>, Discrete Math., 40 (1982), 225-234.

%F a(n) = A187272(n) - Sum_{d|n, d<n} phi(n/d)*a(d). - _Andrew Howroyd_, Mar 29 2016

%e S = {e, 0, 1, 11, 101, 111, 1001, 1111, 10001, 10101, 11011, 11111, 100001, ...}, where e is the empty word.

%e 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 }.

%e 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.

%e 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

%p # A023900:

%p f:=proc(n) local t0,t1,t2; if n=1 then RETURN(1) else

%p 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;

%p # A187272, A187273, A187274, A187275:

%p R:=(a,n)->

%p expand(simplify( (n/4)*a^(n/2)*( (1+sqrt(a))^2+ (-1)^n*(1-sqrt(a))^2 ) ));

%p # A007055, A007056, A007057, A007058

%p F:=(b,n)-> if n=0 then 1 else expand(simplify( add( f(d)*R(b,n/d),d in divisors(n) ) )); fi;

%p # A007055:

%p [seq(F(2,n),n=0..60)];

%t A187272[n_] := A187272[n] = (n/4)*2^(n/2)*((1 + Sqrt[2])^2 + (-1)^n*(1 - Sqrt[2])^2) // Round;

%t a[n_ /; n <= 5] := 2^n; a[n_] := a[n] = A187272[n] - Sum[n, EulerPhi[n/d] * a[d], {d, Most[Divisors[n]]}];

%t Table[a[n], {n, 0, 41}] (* _Jean-Fran├žois Alcover_, Oct 08 2017, after _Andrew Howroyd_ *)

%Y Column 2 of A284873.

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

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

%K nonn

%O 0,2

%A _N. J. A. Sloane_, _Mira Bernstein_, R. Kemp

%E Entry revised by _N. J. A. Sloane_, Mar 07 2011

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 June 25 12:01 EDT 2019. Contains 324352 sequences. (Running on oeis4.)