|
%I M1124 #63 Feb 18 2024 22:57:24
%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 Chai Wah Wu, <a href="/A007055/b007055.txt">Table of n, a(n) for n = 0..6617</a>
%H Chuan Guo, J. Shallit, and 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_ *)
%o (Python)
%o from functools import lru_cache
%o from sympy import totient, proper_divisors
%o @lru_cache(maxsize=None)
%o 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
%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
|
