A164090 -id:A164090 - cp's OEIS frontend

A000029 Number of necklaces with n beads of 2 colors, allowing turning over (these are also called bracelets).

1, 2, 3, 4, 6, 8, 13, 18, 30, 46, 78, 126, 224, 380, 687, 1224, 2250, 4112, 7685, 14310, 27012, 50964, 96909, 184410, 352698, 675188, 1296858, 2493726, 4806078, 9272780, 17920860, 34669602, 67159050, 130216124, 252745368, 490984488, 954637558, 1857545300

Offset: 0

N. J. A. Sloane

"Necklaces with turning over allowed" are usually called bracelets. - Joerg Arndt, Jun 10 2016

			For n=2, the three bracelets are AA, AB, and BB. For n=3, the four bracelets are AAA, AAB, ABB, and BBB. - _Robert A. Russell_, Sep 24 2018

J. L. Fisher, Application-Oriented Algebra (1977), ISBN 0-7002-2504-8, circa p. 215.
Martin Gardner, "New Mathematical Diversions from Scientific American" (Simon and Schuster, New York, 1966), pages 245-246.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.

N. J. A. Sloane, Table of n, a(n) for n = 0..300
Hoda Abbasizanjani and Oliver Kullmann, Classification of minimally unsatisfiable 2-CNFs, arXiv:2003.03639 [cs.DM], 2020.
Joerg Arndt, Matters Computational (The Fxtbook), p. 151
Henry Bottomley, Illustration of initial terms
Emanuele Brugnoli, Enumerating the Walecki-Type Hamiltonian Cycle Systems, Journal of Combinatorial Designs, Volume 25, Issue 11, November 2017, pp. 481-493.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Vladimir Dotsenko and Irvin Roy Hentzel, On the conjecture of Kashuba and Mathieu about free Jordan algebras, arXiv:2507.00437 [math.RA], 2025. See p. 14.
S. N. Ethier and J. Lee, Parrondo games with spatial dependence, arXiv preprint arXiv:1202.2609 [math.PR], 2012. - From _N. J. A. Sloane_, Jun 10 2012
S. N. Ethier and J. Lee, Parrondo games with spatial dependence II, Fluctuation and Noise Letters 11 (4) (2012), 1250030.
S. N. Ethier, Counting toroidal binary arrays, arXiv preprint arXiv:1301.2352 [math.CO], 2013.
S. N. Ethier, Counting toroidal binary arrays, Journal of Integer Sequences 16 (2013), Article 13.4.7.
N. J. Fine, Classes of periodic sequences, Illinois J. Math., 2 (1958), 285-302.
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
Jurij Kovič, Regular polygonal systems, Ars Mathematica Contemporanea (2019) Vol. 16, No. 2, 157-171.
Jia Liu, L. Lalouat, E. Drouard, and R. Orobtchouk, Binary coded patterns for photon control using necklace problem concept, Optics Express Vol. 24, Issue 2, pp. 1133-1142 (2016).
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Zhe Sun, T. Suenaga, P. Sarkar, S. Sato, M. Kotani, and H. Isobe, Stereoisomerism, crystal structures, and dynamics of belt-shaped cyclonaphthylenes, Proc. Nat. Acad. Sci. USA, vol. 113 no. 29, pp. 8109-8114, doi: 10.1073/pnas.1606530113.
James Tilley, Stan Wagon, and Eric Weisstein, A Catalog of Facially Complete Graphs, arXiv:2409.11249 [math.CO], 2024. See p. 11.
A. M. Uludag, A. Zeytin and M. Durmus, Binary Quadratic Forms as Dessins, 2012. - From _N. J. A. Sloane_, Dec 31 2012
Eric Weisstein's World of Mathematics, Necklace
Eric Weisstein's World of Mathematics, e
Index entries for "core" sequences
Index entries for sequences related to bracelets
Index entries for sequences related to necklaces

Row sums of triangle in A052307, second column of A081720, column 2 of A051137.
Cf. A000011, A000013, A000031 (turning over not allowed), A001371 (primitive necklaces), A059076, A164090.
Cf. A000031, A051137.

with(numtheory): A000029 := proc(n) local d,s; if n = 0 then return 1 else if n mod 2 = 1 then s := 2^((n-1)/2) else s := 2^(n/2-2)+2^(n/2-1) fi; for d in divisors(n) do s := s+phi(d)*2^(n/d)/(2*n) od; return s; fi end:

a[0] := 1; a[n_] := Fold[#1 + EulerPhi[#2]2^(n/#2)/(2n) &, If[OddQ[n], 2^((n - 1)/2), 2^(n/2 - 1) + 2^(n/2 - 2)], Divisors[n]]
mx=40;CoefficientList[Series[(1-Sum[ EulerPhi[n]*Log[1-2*x^n]/n,{n,mx}]+(1+x)^2/(1-2*x^2))/2,{x,0,mx}],x] (* Herbert Kociemba, Nov 02 2016 *)
a[0] = 1; a[n_] := (1/4)*(Mod[n, 2] + 3)*2^Quotient[n, 2] + DivisorSum[n, EulerPhi[#]*2^(n/#)&]/(2*n); Array[a, 36, 0] (* Jean-François Alcover, Nov 05 2017 *)

a(n)=if(n<1,!n,(n%2+3)/4*2^(n\2)+sumdiv(n,d,eulerphi(n/d)*2^d)/2/n)

from sympy import divisors, totient
def a(n):
    return 1 if n<1 else ((2**(n//2+1) if n%2 else 3*2**(n//2-1)) + sum(totient(n//d)*2**d for d in divisors(n))//n)//2
print([a(n) for n in range(51)]) # Indranil Ghosh, Apr 23 2017

a(n) = Sum_{d divides n} phi(d)*2^(n/d)/(2*n) + either 2^((n - 1)/2) if n odd or 2^(n/2 - 1) + 2^(n/2 - 2) if n even.
G.f.: (1 - Sum_{n>=1} phi(n)*log(1 - 2*x^n)/n + (1 + x)^2/(1 - 2*x^2))/2. - Herbert Kociemba, Nov 02 2016
Equals (A000031 + A164090) / 2 = A000031 - A059076 = A059076 + A164090. - Robert A. Russell, Sep 24 2018
From Richard L. Ollerton, May 04 2021: (Start)
a(0) = 1; a(n) = Sum_{k=1..n} 2^gcd(n,k)/(2*n) + either 2^((n - 1)/2) if n odd or 2^(n/2 - 1) + 2^(n/2 - 2) if n even.
a(0) = 1; a(n) = A000031(n)/2 + (2^floor((n+1)/2) + 2^ceiling((n+1)/2))/4. See A051137. (End)

More terms from Christian G. Bower

A090989 Number of meaningful differential operations of the n-th order on the space R^4.

Original entry on oeis.org

4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576, 32768, 49152, 65536, 98304, 131072, 196608, 262144, 393216, 524288, 786432, 1048576, 1572864, 2097152, 3145728, 4194304, 6291456, 8388608

Offset: 1

Branko Malesevic, Feb 29 2004

G. C. Greubel, Table of n, a(n) for n = 1..1000
Branko Malesevic, Some combinatorial aspects of differential operation composition on the space R^n , Univ. Beograd, Publ. Elektrotehn. Fak., Ser. Mat. 9 (1998), 29-33.
Branko Malesevic, Some combinatorial aspects of differential operation compositions on space R^n, arXiv:0704.0750 [math.DG], 2007.
Index entries for linear recurrences with constant coefficients, signature (0,2).

Cf. A063759, A029744.

Cf. A090990, A090991, A090992, A090993, A090994, A090995.

a:=[4,6];; for n in [3..40] do a[n]:=2*a[n-2]; od; a; # G. C. Greubel, Feb 02 2019

m:=40; R:=PowerSeriesRing(Integers(), m); Coefficients(R!(  2*x*(2+3*x)/(1-2*x^2) )); // G. C. Greubel, Feb 02 2019

NUM := proc(k :: integer) local i,j,n,Fun,Identity,v,A; n := 4; # <- DIMENSION Fun := (i,j)->piecewise(((j=i+1) or (i+j=n+1)),1,0); Identity := (i,j)->piecewise(i=j,1,0); v := matrix(1,n,1); A := piecewise(k>1,(matrix(n,n,Fun))^(k-1),k=1,matrix(n,n,Identity)); return(evalm(v&*A&*transpose(v))[1,1]); end:

LinearRecurrence[{0,2}, {4,6}, 40] (* G. C. Greubel, Feb 02 2019 *)

my(x='x+O('x^40)); Vec(2*x*(2+3*x)/(1-2*x^2)) \\ G. C. Greubel, Feb 02 2019

(2*(2+3*x)/(1-2*x^2)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, Feb 02 2019

a(k+2) = 2*a(k).
a(n) = b(n+3) where b(n) = gcdConv(c(n)) = Sum_{k=0..n} gcd(c(k),c(n-k)) and c(k)=A000079(k) for k>0 and c(0)=1. - Tilman Neumann, Jan 11 2009 [Updated by Sean A. Irvine, Jan 15 2025]
G.f.: 2*x*(2+3*x)/(1-2*x^2). - Colin Barker, May 03 2012
a(n) = 2*A164090(n). - R. J. Mathar, Jan 25 2023
a(n) = (sqrt(2))^n*(3/2 + sqrt(2) + (-1)^n*(3/2 - sqrt(2))). - Taras Goy, Jan 04 2025

More terms from Tilman Neumann, Feb 06 2009

A059076 Number of pairs of orientable necklaces with n beads and two colors; i.e., turning the necklace over does not leave it unchanged.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 2, 6, 14, 30, 62, 128, 252, 495, 968, 1866, 3600, 6917, 13286, 25476, 48916, 93837, 180314, 346554, 666996, 1284570, 2477342, 4781502, 9240012, 17871708, 34604066, 67060746, 130085052, 252548760, 490722344

Offset: 0

Henry Bottomley, Dec 22 2000

nonn

Number of chiral bracelets with n beads and two colors.

			For n=6, the only chiral pair is AABABB-AABBAB.  For n=7, the two chiral pairs are AAABABB-AAABBAB and AABABBB-AABBBAB. - _Robert A. Russell_, Sep 24 2018

G. C. Greubel, Table of n, a(n) for n = 0..1000
Daniel Gabric and Joe Sawada, Efficient Construction of Long Orientable Sequences, arXiv:2401.14341 [cs.DS], 2024.
Petros Hadjicostas, Formulas for chiral bracelets, 2019; see Section 5.
John P. McSorley and Alan H. Schoen, Rhombic tilings of (n,k)-ovals, (n, k, lambda)-cyclic difference sets, and related topics, Discrete Math., 313 (2013), 129-154. - From _N. J. A. Sloane_, Nov 26 2012

Column 2 of A293496.
Cf. A059053.
Column 2 of A305541.
Equals (A000031 - A164090) / 2.
a(n) = (A052823(n) - A027383(n-2)) / 2.

nn=35;Table[CoefficientList[Series[CycleIndex[CyclicGroup[n],s]-CycleIndex[DihedralGroup[n],s]/.Table[s[i]->2,{i,1,n}],{x,0,nn}],x],{n,1,nn}]//Flatten  (* Geoffrey Critzer, Mar 26 2013 *)
mx=40; CoefficientList[Series[(1-Sum[ EulerPhi[n]*Log[1-2*x^n]/n, {n, mx}]-(1+x)^2/(1-2*x^2))/2, {x, 0, mx}], x] (* Herbert Kociemba, Nov 02 2016 *)
terms = 36; a29[0] = 1; a29[n_] := (1/4)*(Mod[n, 2] + 3)*2^Quotient[n, 2] + DivisorSum[n, EulerPhi[#]*2^(n/#) & ]/(2*n); Array[a29, 36, 0] - LinearRecurrence[{0, 2}, {1, 2, 3}, 36] (* Jean-François Alcover, Nov 05 2017 *)
k = 2; Prepend[Table[DivisorSum[n, EulerPhi[#] k^(n/#) &]/(2n)(k^Floor[(n+1)/2] + k^Ceiling[(n+1)/2])/4, {n, 1, 30}], 0] (* Robert A. Russell, Sep 24 2018 *)

a(n) = A000031(n) - A000029(n) = A000029(n) - A029744(n) = (A000031(n) - A029744(n))/2 = A008965(n) - A091696(n)
G.f.: (1 - Sum_{n>=1} phi(n)*log(1 - 2*x^n)/n - (1 + x)^2/(1 - 2*x^2))/2. - Herbert Kociemba, Nov 02 2016
For n > 0, a(n) = -(k^floor((n + 1)/2) + k^ceiling((n + 1)/2))/4 + (1/(2*n))* Sum_{d|n} phi(d)*k^(n/d), where k = 2 is the maximum number of colors. - Robert A. Russell, Sep 24 2018

A284855 Array read by antidiagonals: T(n,k) = number of necklaces with n beads and k colors that are the same when turned over.

Original entry on oeis.org

1, 2, 1, 3, 3, 1, 4, 6, 4, 1, 5, 10, 9, 6, 1, 6, 15, 16, 18, 8, 1, 7, 21, 25, 40, 27, 12, 1, 8, 28, 36, 75, 64, 54, 16, 1, 9, 36, 49, 126, 125, 160, 81, 24, 1, 10, 45, 64, 196, 216, 375, 256, 162, 32, 1, 11, 55, 81, 288, 343, 756, 625, 640, 243, 48, 1

Offset: 1

Andrew Howroyd, Apr 04 2017

Number of periodic palindromes of length n using a maximum of k different symbols.
From Petros Hadjicostas, Sep 02 2018: (Start)
According to Christian Bower's theory of transforms, we have boxes of different sizes and different colors. The size of a box is determined by the number of balls it can hold. In this case, we assume all balls are the same and are unlabeled.  Assume also that the number of possible colors a box with m balls can have is given by c(m). We place the boxes on a circle at equal distances from each other. Two configurations of boxes on the circle are considered equivalent if one can be obtained from the other by rotation. We are interested about circular configurations of boxes that are circular palindromes (i.e., necklaces with boxes that are the same when turned over). Let b(n) be the number of circularly palindromic configurations of boxes on a circle when the total number of balls in the boxes is n (and each box contains at least one ball).
Bower calls the sequence (b(n): n >= 1), the CPAL ("circular palindrome") transform of the input sequence (c(m): m >= 1). If the g.f. of the input sequence (c(m): m >= 1) is C(x) = Sum_{m>=1} c(m)*x^m, then the g.f. of the output sequence (b(n): n >= 1) is B(x) = Sum_{n >= 1} b(n)*x^n = (1 + C(x))^2/(2*(1 - C(x^2))) - 1/2.
In the current sequence, each box holds only one ball but can have one of k colors. Hence, c(1) = k but c(m) = 0 for m >= 2. Thus, C(x) = k*x. Then, for fixed k, the output sequence is (b(n): n >= 1) = (T(n, k): n >= 1), where T(n, k) = number of necklaces with n beads and k colors that are the same when turned over. If we let B_k(x) = Sum_{n>=1} T(n, k)*x^n, then B_k(x) = (1 + k*x)^2/(2*(1 - k*x^2)) - 1/2. From this, we can easily prove the formulae below.
Note that T(n, k=2) - 1 is the total number of Sommerville symmetric cyclic compositions of n. See pp. 301-304 in his paper in the links below. To see why this is the case, we use MacMahon's method of representing a cyclic composition of n with a necklace of 2 colors (see p. 273 in Sommerville's paper where the two "colors" are an x and a dot . rather than B and W). Given a Sommerville symmetrical composition b_1 + ... + b_r of n (with b_i >= 1 for all i and 1 <= r <= n), create the following circularly palindromic necklace with n beads of 2 colors: Start with a B bead somewhere on the circle and place b_1 - 1 W beads to the right of it; place a B bead to the right of the W beads (if any) followed by b_2 - 1 W beads; and so on. At the end, place a B bead followed with b_r - 1 W beads. (If b_i = 1 for some i, then a B bead follows a B bead since there are 0 W beads between them.) We thus get a circularly palindromic necklace with n beads of two colors. (The only necklace we cannot get with this method is the one than has all n beads colored W.)
It is interesting that the representation of a necklace of length n, say s_1, s_2, ..., s_n, as a periodic sequence (..., s_{-2}, s_{-1}, s_0, s_1, s_2, ...) with the property s_i = s_{i+n} for all i, as was done by Marks R. Nester in Chapter 2 of his 1999 PhD thesis, was considered by Sommerville in his 1909 paper (in the very first paragraph of his paper). (End)

			Table starts:
1  2   3    4    5     6     7      8      9     10 ...
1  3   6   10   15    21    28     36     45     55 ...
1  4   9   16   25    36    49     64     81    100 ...
1  6  18   40   75   126   196    288    405    550 ...
1  8  27   64  125   216   343    512    729   1000 ...
1 12  54  160  375   756  1372   2304   3645   5500 ...
1 16  81  256  625  1296  2401   4096   6561  10000 ...
1 24 162  640 1875  4536  9604  18432  32805  55000 ...
1 32 243 1024 3125  7776 16807  32768  59049 100000 ...
1 48 486 2560 9375 27216 67228 147456 295245 550000 ...
...
For n = 4 and k = 2, the palindromic necklaces are 0000, 0001, 0011, 0111, 0101, 1111 so T(4,2) = 6. Necklaces are only counted up to cyclic equivalence.
For n = 4 and k = 2, using MacMahon's bijection, with B = 0 and W = 1, the corresponding Sommerville symmetrical cyclic compositions of n = 4 are as follows: 1+1+1+1, 1+1+2, 1+3, 4, 2+2 (with none for 1111). If we let B = 1 and W = 0, we get the corresponding symmetrical cyclic compositions of n=4: (none for 0000) 4, 1+3, 1+1+2, 2+2, 1+1+1+1. (All these cyclic compositions must viewed on a circle.) - _Petros Hadjicostas_, Sep 02 2018

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for the pdf file of Chap. 2]

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Christian G. Bower, Transforms (2).
Petros Hadjicostas, Generalized colored circular palindromic compositions, Moscow Journal of Combinatorics and Number Theory, 9(2) (2020), 173-186.
D. M. Y. Sommerville, On certain periodic properties of cyclic compositions of numbers, Proc. London Math. Soc. S2-7(1) (1909), 263-313.

Columns 2-6 are A164090, A182751(n-1), A056486, A056487(n-1), A056488.

Cf. A037306, A081720, A075195, A119963, A284856, A277504.

a[n_, k_] := If[EvenQ[n], (k^(n/2) + k^(n/2 + 1))/2, k^((n+1)/2)];
Table[a[n-k+1, k], {n, 1, 11}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Jun 05 2017, translated from PARI *)

a(n,k) = if(n % 2 == 0, (k^(n/2) + k^(n/2+1))/2, k^((n+1)/2));
for(n=1, 10, for(k=1, 10, print1( a(n,k),", ");); print(););

T(2*n, k) = (k^(n+1) + k^n) / 2.
T(2*n + 1, k) = k^(n+1).
T(n, k) = 2 * A081720(n, k) - A075195(n, k).
From Petros Hadjicostas, Sep 02 2018: (Start)
For fixed k >= 1, the k-th column (T(n, k): n >= 1) is the CPAL ("circular palindrome") transform of the sequence k, 0, 0, ...
G.f. of column k: Sum_{n>=1} T(n,k)*x^n = (1 + k*x)^2/(2*(1 - k*x^2)) - 1/2. (End)

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

Original entry on oeis.org

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

A056503 Number of periodic palindromic structures of length n using a maximum of two different symbols.

Original entry on oeis.org

1, 2, 2, 4, 4, 7, 8, 14, 16, 26, 32, 51, 64, 100, 128, 198, 256, 392, 512, 778, 1024, 1552, 2048, 3091, 4096, 6176, 8192, 12324, 16384, 24640, 32768, 49222, 65536, 98432, 131072, 196744, 262144, 393472, 524288, 786698, 1048576, 1573376, 2097152, 3146256, 4194304

Offset: 1

Marks R. Nester

nonn

For example, aaabbb is not a (finite) palindrome but it is a periodic palindrome. Permuting the symbols will not change the structure.
A periodic palindrome is just a necklace that is equivalent to its reverse. The number of binary periodic palindromes of length n is given by A164090(n). A binary periodic palindrome can only be equivalent to its complement when there are an equal number of 0's and 1's. - Andrew Howroyd, Sep 29 2017
Number of cyclic compositions (necklaces of positive integers) summing to n that can be rotated to form a palindrome. - Gus Wiseman, Sep 16 2018

			From _Gus Wiseman_, Sep 16 2018: (Start)
The sequence of palindromic cyclic compositions begins:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)
       (11)  (111)  (22)    (113)    (33)      (115)
                    (112)   (122)    (114)     (133)
                    (1111)  (11111)  (222)     (223)
                                     (1122)    (11113)
                                     (11112)   (11212)
                                     (111111)  (11122)
                                               (1111111)
(End)

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

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

Row sums of A179181.
Cf. A016116, A045674, A056508, A164090, A285012.
Cf. A000740, A000837, A008965, A025065, A059966, A242414, A296302, A317085, A317086, A317087, A318731.

(* b = A164090, c = A045674 *)
b[n_] := (1/4)*(7 - (-1)^n)*2^((1/4)*(2*n + (-1)^n - 1));
c[0] = 1; c[n_] := c[n] = If[EvenQ[n], 2^(n/2-1) + c[n/2], 2^((n-1)/2)];
a[n_?OddQ] := b[n]/2; a[n_?EvenQ] := (1/2)*(b[n] + c[n/2]);
Array[a, 45] (* Jean-François Alcover, Oct 08 2017, after Andrew Howroyd *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Function[q,And[Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And],Array[SameQ[RotateRight[q,#],Reverse[RotateRight[q,#]]]&,Length[q],1,Or]]]]],{n,15}] (* Gus Wiseman, Sep 16 2018 *)

a(2n+1) = A164090(2n+1)/2 = 2^n, a(2n) = (A164090(2n) + A045674(n))/2. - Andrew Howroyd, Sep 29 2017

a(17)-a(45) from Andrew Howroyd, Apr 07 2017

A056513 Number of primitive (period n) periodic palindromic structures using a maximum of two different symbols.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 4, 7, 10, 14, 21, 31, 42, 63, 91, 123, 184, 255, 371, 511, 750, 1015, 1519, 2047, 3030, 4092, 6111, 8176, 12222, 16383, 24486, 32767, 49024, 65503, 98175, 131061, 196308, 262143, 392959, 524223, 785910, 1048575, 1572256, 2097151, 3144702, 4194162

Offset: 0

Marks R. Nester

nonn

For example, aaabbb is not a (finite) palindrome but it is a periodic palindrome. Permuting the symbols will not change the structure.

Number of Lyndon compositions (aperiodic necklaces of positive integers) summing to n that can be rotated to form a palindrome. - Gus Wiseman, Sep 16 2018

			From _Gus Wiseman_, Sep 16 2018: (Start)
The sequence of palindromic Lyndon compositions begins:
  (1)  (2)  (3)  (4)    (5)    (6)      (7)
                 (112)  (113)  (114)    (115)
                        (122)  (1122)   (133)
                               (11112)  (223)
                                        (11113)
                                        (11212)
                                        (11122)
(End)

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Row sums of A179317.

Cf. A008965, A025065, A056476, A059966, A242414, A285037, A317085, A317086, A317087, A318731.

(* b = A164090, c = A045674 *)
b[n_] := (1/4)*(7 - (-1)^n)*2^((1/4)*(2*n + (-1)^n - 1));
c[0] = 1;
c[n_] := c[n] = If[EvenQ[n], 2^(n/2 - 1) + c[n/2], 2^((n - 1)/2)];
a56503[n_] := If[OddQ[n], b[n]/2, (1/2)*(b[n] + c[n/2])];
a[n_] := DivisorSum[n, MoebiusMu[#] a56503[n/#]&];
Array[a, 45] (* Jean-François Alcover, Jun 29 2018, after Andrew Howroyd *)

a(n) = {if(n < 1, n==0, sumdiv(n, d, moebius(d)*(2 + d%2)*(2^(n/d\2)))/(4 - n%2))} \\ Andrew Howroyd, Sep 26 2019

seq(n) = Vec(1 + (1/2)*sum(k=1, n, moebius(k)*x^k*(2 + 3*x^k)/(1 - 2*x^(2*k)) - moebius(2*k)*x^(2*k)*(1 + x^(2*k))/(1 - 2*x^(4*k)) + O(x*x^n))) \\ Andrew Howroyd, Sep 27 2019

a(n) = Sum_{d|n} mu(d)*A056503(n/d) for n > 0.
a(n) = Sum_{k=1..2} A285037(n, k). - Andrew Howroyd, Apr 08 2017
G.f.: 1 + (1/2)*Sum_{k>=1} mu(k)*x^k*(2 + 3*x^k)/(1 - 2*x^(2*k)) - mu(2*k)*x^(2*k)*(1 + x^(2*k))/(1 - 2*x^(4*k)). - Andrew Howroyd, Sep 27 2019

a(17)-a(45) from Andrew Howroyd, Apr 08 2017

a(0)=1 prepended by Andrew Howroyd, Sep 27 2019

A164034 a(n) = ((4+3sqrt(2))(4+sqrt(2))^n + (4-3sqrt(2))(4-sqrt(2))^n)/4.

Original entry on oeis.org

2, 11, 60, 326, 1768, 9580, 51888, 280984, 1521440, 8237744, 44601792, 241485920, 1307462272, 7078895296, 38326690560, 207508990336, 1123498254848, 6082860174080, 32933905824768, 178311204161024, 965414951741440

Offset: 0

Al Hakanson (hawkuu(AT)gmail.com), Aug 08 2009

nonn

Binomial transform of A164033. Fourth binomial transform of A164090. Inverse binomial transform of A164035.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (8,-14).

Cf. A164033, A164090, A164035.

Z:= PolynomialRing(Integers()); N:=NumberField(x^2-2); S:=[ ((4+3*r)*(4+r)^n+(4-3*r)*(4-r)^n)/4: n in [0..20] ]; [ Integers()!S[j]: j in [1..#S] ]; // Klaus Brockhaus, Aug 09 2009

LinearRecurrence[{8,-14},{2,11},30] (* Harvey P. Dale, Aug 09 2016 *)

x='x+O('x^50); Vec((2-5*x)/(1-8*x+14*x^2)) \\ G. C. Greubel, Sep 08 2017

a(n) = 8*a(n-1) - 14*a(n-2) for n > 1; a(0) = 2, a(1) = 11.
G.f.: (2-5*x)/(1-8*x+14*x^2).
E.g.f.: (2*cosh(sqrt(2)*x) + (3*sqrt(2)/2)*sinh(sqrt(2)*x))*exp(4*x). - G. C. Greubel, Sep 08 2017

Edited and extended beyond a(5) by Klaus Brockhaus, Aug 09 2009

A056508 Number of periodic palindromic structures of length n using exactly two different symbols.

Original entry on oeis.org

0, 1, 1, 3, 3, 6, 7, 13, 15, 25, 31, 50, 63, 99, 127, 197, 255, 391, 511, 777, 1023, 1551, 2047, 3090, 4095, 6175, 8191, 12323, 16383, 24639, 32767, 49221, 65535, 98431, 131071, 196743, 262143, 393471, 524287, 786697, 1048575, 1573375, 2097151, 3146255, 4194303

Offset: 1

Marks R. Nester

nonn

For example, aaabbb is not a (finite) palindrome but it is a periodic palindrome. Permuting the symbols will not change the structure.

For odd n, a palindrome cannot be the complement of itself, so a(n) is given by A284855(n,2)/2 - 1. - Andrew Howroyd, Apr 08 2017

			From _Andrew Howroyd_, Apr 07 2017: (Start)
Example for n=6:
Periodic symmetry means results are either in the form abccba or abcdcb.
There are 3 binary words in the form abccba that start with 0 and contain a 1 which are 001100, 010010, 011110. Of these, 011110 is equivalent to 001100 after rotation.
There are 7 binary words in the form abcdcb that start with 0 and contain a 1 which are 000100, 001010, 001110, 010001, 010101, 011011, 011111. Of these, 011111 is equivalent to 000100, 010001 is equivalent to 001010 and 011011 is equivalent to 010010 from the first set.
There are therefore a total of 7 + 3 - 4 = 6 equivalence classes so a(6) = 6.
(End)

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Giovanni Resta, Table of n, a(n) for n = 1..1000

Column 2 of A285012.

Cf. A052551.

(* b = A164090, c = A045674 *)
b[n_] := (1/4)*(7 - (-1)^n)*2^((1/4)*(2*n + (-1)^n - 1));
c[0] = 1;
c[n_] := c[n] = If[EvenQ[n], 2^(n/2 - 1) + c[n/2], 2^((n - 1)/2)];
a[n_] := If[OddQ[n], b[n]/2, (1/2)*(b[n] + c[n/2])] - 1;
Array[a, 45] (* Jean-François Alcover, Jun 29 2018, after Andrew Howroyd *)

a(n) = A056503(n) - 1.

a(2n + 1) = 2^n - 1. - Andrew Howroyd, Apr 07 2017

a(17)-a(45) from Andrew Howroyd, Apr 07 2017

A164033 a(n) = ((4+3sqrt(2))(3+sqrt(2))^n + (4-3sqrt(2))(3-sqrt(2))^n)/4.

Original entry on oeis.org

2, 9, 40, 177, 782, 3453, 15244, 67293, 297050, 1311249, 5788144, 25550121, 112783718, 497851461, 2197622740, 9700776213, 42821298098, 189022355097, 834385043896, 3683153777697, 16258227358910, 71767287709581

Offset: 0

Al Hakanson (hawkuu(AT)gmail.com), Aug 08 2009

nonn

Binomial transform of A020727. Third binomial transform of A164090. Inverse binomial transform of A164034.

Matthew House, Table of n, a(n) for n = 0..1542
Index entries for linear recurrences with constant coefficients, signature (6,-7).

Cf. A020727, A164090 (2, 3, 4, 6, 8, 12), A164034.

Z:= PolynomialRing(Integers()); N:=NumberField(x^2-2); S:=[ ((4+3*r)*(3+r)^n+(4-3*r)*(3-r)^n)/4: n in [0..21] ]; [ Integers()!S[j]: j in [1..#S] ]; // Klaus Brockhaus, Aug 09 2009

CoefficientList[Series[(2-3*x)/(1-6*x+7*x^2), {x, 0, 1000}],
  x] (* or *) LinearRecurrence[{6,-7},{2,9}, 50] (* G. C. Greubel, Sep 08 2017 *)

x='x+O('x^50); Vec((2-3*x)/(1-6*x+7*x^2)) \\ G. C. Greubel, Sep 08 2017

a(n) = 6*a(n-1) - 7*a(n-2) for n > 1; a(0) = 2, a(1) = 9.
G.f.: (2-3*x)/(1-6*x+7*x^2).
E.g.f.: (2*cosh(sqrt(2)*x) + (3/sqrt(2))*sinh(sqrt(2)*x))*exp(3*x). - G. C. Greubel, Sep 08 2017

Edited and extended beyond a(5) by Klaus Brockhaus, Aug 09 2009

cp's OEIS Frontend

A000029 Number of necklaces with n beads of 2 colors, allowing turning over (these are also called bracelets).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A090989 Number of meaningful differential operations of the n-th order on the space R^4.

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A059076 Number of pairs of orientable necklaces with n beads and two colors; i.e., turning the necklace over does not leave it unchanged.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A284855 Array read by antidiagonals: T(n,k) = number of necklaces with n beads and k colors that are the same when turned over.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

A056503 Number of periodic palindromic structures of length n using a maximum of two different symbols.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A164034 a(n) = ((4+3sqrt(2))(4+sqrt(2))^n + (4-3sqrt(2))(4-sqrt(2))^n)/4.

A164033 a(n) = ((4+3sqrt(2))(3+sqrt(2))^n + (4-3sqrt(2))(3-sqrt(2))^n)/4.