A284873 -id:A284873 - cp's OEIS frontend

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

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

nonn

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

a(n) = sum of the orbit sizes of all achiral necklaces (or bracelets) under the action of the cyclic (or dihedral) group. - Mathieu Gagne, Jul 29 2025

			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

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

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.

Column 2 of A284873.
For the nonempty words in the language S, see A057148 and A006995.
Cf. A007056-A007058, A023900, A187272-A187275.

# 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)];

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 *)

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

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

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

A284877 Irregular triangle T(n,k) for 1 <= k <= n/2 + 1: T(n,k) = number of double palindrome structures of length n using exactly k different symbols.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 7, 2, 1, 15, 5, 1, 25, 21, 3, 1, 49, 42, 7, 1, 79, 122, 44, 4, 1, 129, 225, 90, 9, 1, 211, 570, 375, 80, 5, 1, 341, 990, 715, 165, 11, 1, 517, 2321, 2487, 930, 132, 6, 1, 819, 3913, 4550, 1820, 273, 13, 1, 1275, 8827, 14350, 8330, 2009, 203, 7

Offset: 1

Andrew Howroyd, Apr 04 2017

A double palindrome is the concatenation of two palindromes. Permuting the symbols will not change the structure. For the purposed of this sequence, valid palindromes include both the empty word and a singleton symbol.

			Triangle starts:
1
1     1
1     3
1     7      2
1    15      5
1    25     21       3
1    49     42       7
1    79    122      44       4
1   129    225      90       9
1   211    570     375      80       5
1   341    990     715     165      11
1   517   2321    2487     930     132      6
1   819   3913    4550    1820     273     13
1  1275   8827   14350    8330    2009    203      7
1  1863  14480   25515   15750    3990    420     15
1  2959  31802   75724   64004   23296   3920    296     8
1  4335  51425  132090  118167   44982   7854    612    17
1  6703 110928  376779  445275  229257  57078   7074   414   9
1  9709 177270  647995  807975  433713 111720  14250   855  19
1 15067 377722 1798175 2892470 2023135 698670 126300 12000 560 10
....
The first few structures are:
n = 1: a => 1
n = 2: aa; ab => 1 + 1
n = 3: aaa; aab, aba, abb => 1 + 3
n = 4: aaaa; aaab, aaba, aabb, abaa, abab, abba, abbb; abac, abcb => 1 + 7 + 2

Andrew Howroyd, Table of n, a(n) for n = 1..960

Columns k=2..4 are A328688, A328689, A328690.
Row sums are A165137.
Partial row sums include A180249, A328692, A328693.
Cf. A284873, A284826.

r[d_, k_]:=If[OddQ[d], d*k^((d + 1)/2), (d/2)*(k + 1)*k^(d/2)]; a[n_, k_]:= r[n, k] - Sum[If[dIndranil Ghosh, Apr 07 2017 *)

r(d,k)=if (d % 2 == 0, (d/2)*(stirling(d/2,k,2)+stirling(d/2+1,k,2)), d*stirling((d+1)/2, k,2));
a(n,k) = r(n,k) - sumdiv(n,d, if (d

from sympy import totient, divisors, binomial, factorial
def r(d, k): return (d//2)*(k + 1)*k**(d//2) if d%2 == 0 else d*k**((d + 1)//2)
def a(n, k): return r(n, k) - sum([totient(n//d)*a(d, k) for d in divisors(n) if dIndranil Ghosh, Apr 07 2017

T(n, k) = (Sum_{j=0..k} (-1)^j * binomial(k, j) * A284873(n, k-j)) / k!.

T(n, k) = r(n, k) - Sum_{d|n, d

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

Original entry on oeis.org

1, 3, 9, 21, 57, 123, 279, 549, 1209, 2127, 4689, 7989, 17031, 28395, 60615, 98061, 208569, 334563, 705789, 1121877, 2356737, 3718827, 7786359, 12223077, 25488903, 39857523, 82876257, 129135729, 267784119, 416118219, 860825439, 1334448261, 2754778809, 4261609131, 8781196329, 13559714109, 27893530029

Offset: 0

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

nonn

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

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

Column 3 of A284873.

Maple
```
See A007055.
```

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

a(n) = A187273(n) - Sum_{d|n,dSean A. Irvine, Sep 27 2017

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

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

Original entry on oeis.org

1, 4, 16, 40, 136, 304, 880, 1768, 4936, 9112, 25216, 45016, 121600, 212944, 571552, 982240, 2616136, 4456384, 11785408, 19922872, 52402336, 88076560, 230641504, 385875880, 1006499200, 1677720304, 4361862976, 7247738776, 18789905872, 31138512784, 80529599680, 133143986056, 343594756936

Offset: 0

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

nonn

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

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

Column 4 of A284873.

Maple
```
See A007055.
```

from functools import lru_cache
from sympy import totient, proper_divisors
@lru_cache(maxsize=None)
def A007057(n): return (n<>1)<A007057(d) for d in proper_divisors(n,generator=True)) if n else 1 # Chai Wah Wu, Feb 19 2024

a(n) = A187274(n) - Sum_{d|n,dSean A. Irvine, Sep 27 2017

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

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

Original entry on oeis.org

1, 5, 25, 65, 265, 605, 2125, 4345, 14665, 27965, 93025, 171825, 559645, 1015565, 3276725, 5857865, 18734665, 33203045, 105436225, 185546785, 585842065, 1025381485, 3222484125, 5615234265, 17577530845, 30517575605, 95213827825, 164794865465, 512692025285, 885009765485, 2746575977125

Offset: 0

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

nonn

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

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

Column 5 of A284873.

Cf. A007055, A007056, A007057.

Maple
```
See A007055.
```

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

a(n) = A187275(n) - Sum_{d|n,dSean A. Irvine, Sep 27 2017

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

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

Original entry on oeis.org

1, 16, 57, 136, 265, 456, 721, 1072, 1521, 2080, 2761, 3576, 4537, 5656, 6945, 8416, 10081, 11952, 14041, 16360, 18921, 21736, 24817, 28176, 31825, 35776, 40041, 44632, 49561, 54840, 60481, 66496, 72897, 79696, 86905, 94536, 102601, 111112, 120081, 129520, 139441, 149856, 160777, 172216, 184185

Offset: 1

N. J. A. Sloane, Mar 07 2011

nonn

G. C. Greubel, Table of n, a(n) for n = 1..1000
R. Kemp, On the number of words in the language {w in Sigma* | w = w^R }^2, Discrete Math., 40 (1982), 225-234. See Table 1.

Row 4 of A284873.

[2*n^3 + n^2 - 2*n: n in [1..50]]; // G. C. Greubel, Jul 25 2018

Using the Maple code from A007055: [seq(F(b,4),b=1..50)];

Array[# (2 #^2 + # - 2) &, 45] (* or *)
Rest@ CoefficientList[Series[-x (x^2 - 12 x - 1)/(x - 1)^4, {x, 0, 45}], x] (* Michael De Vlieger, Oct 10 2017 *)

a(n) = 2*n^3 + n^2 - 2*n; \\ Andrew Howroyd, Oct 10 2017

def A187277(n): return n*(n*((n<<1)|1)-2) # Chai Wah Wu, Feb 19 2024

From Colin Barker, Jul 24 2013: (Start) (Conjectured formulas; later proven)
a(n) = n*(2*n^2 +n -2).
G.f.: x*(1 +12*x - x^2)/(x-1)^4. (End)
The above conjecture is true: A284873(4, n) evaluates to the same polynomial. - Andrew Howroyd, Oct 10 2017

A271532 a(n) = (-1)^n(n + 1)(5n^2 + 10n + 1).

Original entry on oeis.org

1, -32, 123, -304, 605, -1056, 1687, -2528, 3609, -4960, 6611, -8592, 10933, -13664, 16815, -20416, 24497, -29088, 34219, -39920, 46221, -53152, 60743, -69024, 78025, -87776, 98307, -109648, 121829, -134880, 148831, -163712, 179553, -196384, 214235, -233136, 253117, -274208, 296439

Offset: 0

Ilya Gutkovskiy, Apr 09 2016

Alternating sum of centered dodecahedral numbers (A005904).

Without signs and up to offset, this is row 5 of the array A284873. - Andrey Zabolotskiy, Oct 10 2017

OEIS Wiki, Centered Platonic numbers
Eric Weisstein's World of Mathematics, Platonic Solid
Index entries for linear recurrences with constant coefficients, signature (-4,-6,-4,-1)

Cf. A000578, A004466, A005904, A006527, A005900, A006566.

Table[(-1)^n (n + 1) (5 n^2 + 10 n + 1), {n, 0, 38}]
LinearRecurrence[{-4, -6, -4, -1}, {1, -32, 123, -304}, 39]

a(n)=(-1)^n*(n+1)*(5*n^2+10*n+1) \\ Charles R Greathouse IV, Jul 26 2016

for n in range(0,10**3):print((-1)**n*(n+1)*(5*n**2+10*n+1)) # Soumil Mandal, Apr 10 2016

G.f.: (1 - 28*x + x^2)/(1 + x)^4.
E.g.f.: exp(-x)*(1 - 31*x + 30*x^2 - 5*x^3).
a(n) = -4*a(n-1) - 6*a(n-2) - 4*a(n-3) - a(n-4).

Showing 1-7 of 7 results.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A284877 Irregular triangle T(n,k) for 1 <= k <= n/2 + 1: T(n,k) = number of double palindrome structures of length n using exactly k different symbols.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

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

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Python

Formula

Extensions

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

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Python

Formula

Extensions

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

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Python

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A271532 a(n) = (-1)^n*(n + 1)*(5*n^2 + 10*n + 1).

Views

A271532 a(n) = (-1)^n(n + 1)(5n^2 + 10n + 1).