A007055 Let S denote the palindromes in the language {0,1}*; a(n) = number of words of length n in the language SS.
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
Keywords
Examples
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
For n=6, there are 2 achiral necklaces with orbit size s=1, 1 with s=2, 2 with s=3, and 7 with s=6, giving a total of 2*1+1*2+2*3+7*6 = 52. - _Mathieu Gagne_, Jul 29 2025
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.
Crossrefs
Programs
-
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 *) Table[Sum[s * Sum[MoebiusMu[s/d] If[EvenQ[d], 3*2^((d/2) - 1), 2^((d + 1)/2)] , {d, Divisors[s]}], {s, Divisors[n]}], {n, 1, 41}] (* Mathieu Gagne, Jul 29 2025 *)
-
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
Formula
a(n) = A187272(n) - Sum_{d|n, dAndrew Howroyd, Mar 29 2016
a(0)=1; a(n) = Sum_{s|n} s * A056493(s) for n>0. - Mathieu Gagne, Jul 29 2025
a(0)=1; a(n) = Sum_{s|n} s * (Sum_{d|s} mu(d) * A164090(s/d)) for n>0. - Mathieu Gagne, Jul 29 2025
Extensions
Entry revised by N. J. A. Sloane, Mar 07 2011
Comments