A002076 -id:A002076 - cp's OEIS frontend

A000048 Number of n-bead necklaces with beads of 2 colors and primitive period n, when turning over is not allowed but the two colors can be interchanged.

1, 1, 1, 1, 2, 3, 5, 9, 16, 28, 51, 93, 170, 315, 585, 1091, 2048, 3855, 7280, 13797, 26214, 49929, 95325, 182361, 349520, 671088, 1290555, 2485504, 4793490, 9256395, 17895679, 34636833, 67108864, 130150493, 252645135, 490853403, 954437120, 1857283155

Offset: 0

N. J. A. Sloane

Also, for any m which is a multiple of n, the number of 2m-bead balanced binary necklaces of fundamental period 2n that are equivalent to their complements. [Clarified by Aaron Meyerowitz, Jun 01 2024]
Also binary Lyndon words of length n with an odd number of 1's (for n>=1).
Also number of binary irreducible polynomials of degree n having trace 1.
Also number of binary irreducible polynomials of degree n having linear coefficient 1 (this is the same as the trace-1 condition, as the reciprocal of an irreducible polynomial is again irreducible).
Also number of binary irreducible self-reciprocal polynomials of degree 2*n; there is no such polynomial for odd degree except for x+1.
Also number of binary vectors (x_1,...x_n) satisfying Sum_{i=1..n} i*x_i = 1 (mod n+1) = size of Varshamov-Tenengolts code VT_1(n).
Also the number of dynamical cycles of period 2n of a threshold Boolean automata network which is a quasi-minimal negative circuit of size nq where q is odd and which is updated in parallel. - Mathilde Noual (mathilde.noual(AT)ens-lyon.fr), Mar 03 2009
Also the number of 3-elements orbits of the symmetric group S3 action on irreducible polynomials of degree 2n, n>1, over GF(2). - Jean Francis Michon, Philippe Ravache (philippe.ravache(AT)univ-rouen.fr), Oct 04 2009
Conjecture: Also the number of caliber-n cycles of Zagier-reduced indefinite binary quadratic forms with sum invariant equal to s, where (s-1)/n is an odd integer. - Barry R. Smith, Dec 14 2014
The Metropolis, Stein, Stein (1973) reference on page 31 Table II lists a(k) for k = 2 to 15 and is actually for sequence A056303 since there a(k) = 0 for k<2. - Michael Somos, Dec 20 2014

			a(5) = 3 corresponding to the necklaces 00001, 00111, 01011.
a(6) = 5 from 000001, 000011, 000101, 000111, 001011.

B. D. Ginsburg, On a number theory function applicable in coding theory, Problemy Kibernetiki, No. 19 (1967), pp. 249-252.
H. Kawakami, Table of rotation sequences of x_{n+1} = x_n^2 - lambda, pp. 73-92 of G. Ikegami, Editor, Dynamical Systems and Nonlinear Oscillations, Vol. 1, World Scientific, 1986.
Robert M. May, "Simple mathematical models with very complicated dynamics." Nature, Vol. 261, June 10, 1976, pp. 459-467; reprinted in The Theory of Chaotic Attractors, pp. 85-93. Springer, New York, NY, 2004. The sequences listed in Table 2 are A000079, A027375, A000031, A001037, A000048, A051841. - N. J. A. Sloane, Mar 17 2019
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).

G. C. Greubel, Table of n, a(n) for n = 0..3320 (terms 0..200 from T. D. Noe)
Joerg Arndt, Matters Computational (The Fxtbook), p.408 and p.848.
L. Carlitz, A theorem of Dickson on irreducible polynomials, Proc. Amer. Math. Soc. 3, (1952). 693-700.
CombOS - Combinatorial Object Server, Generate necklaces, Lyndon words, chord diagrams, and relatives
J. Demongeot, M. Noual and S. Sene, On the number of attractors of positive and negative threshold Boolean automata circuits, hal-00647877 preprint (2009). [From Mathilde Noual (mathilde.noual(AT)ens-lyon.fr), Mar 03 2009]
N. J. Fine, Classes of periodic sequences, Illinois J. Math., 2 (1958), 285-302.
H. L. Fisher, Letter to N. J. A. Sloane, Mar 16 1989
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
R. W. Hall and P. Klingsberg, Asymmetric rhythms and tiling canons, Amer. Math. Monthly, 113 (2006), 887-896.
J. E. Iglesias, A formula for the number of closest packings of equal spheres having a given repeat period, Z. Krist. 155 (1981) 121-127, Table 2.
J. E. Iglesias, Enumeration of polytypes MX and MX_2 through the use of the symmetry of the Zhadanov symbol, Acta Cryst. A 62 (3) (2006) 178-194, Table 1.
Veronika Irvine, Lace Tessellations: A mathematical model for bobbin lace and an exhaustive combinatorial search for patterns, PhD Dissertation, University of Victoria, 2016.
A. A. Kulkarni, N. Kiyavash and R. Sreenivas, On the Varshamov-Tenengolts Construction on Binary Strings, 2013.
R. P. Loh, A. G. Shannon, A. F. Horadam, Divisibility Criteria and Sequence Generators Associated with Fermat Coefficients, Preprint, 1980.
R. M. May, Simple mathematical models with very complicated dynamics, Nature, 261 (Jun 10, 1976), 459-467.
N. Metropolis, M. L. Stein and P. R. Stein, On finite limit sets for transformations on the unit interval, J. Combin. Theory, A 15 (1973), 25-44; reprinted in P. Cvitanovic, ed., Universality in Chaos, Hilger, Bristol, 1986, pp. 187-206.
H. Meyn and W. Götz, Self-reciprocal polynomials over finite fields, Séminaire Lotharingien de Combinatoire, B21d (1989), 8 pp.
Simon Michalowsky, Bahman Gharesifard, Christian Ebenbauer, A Lie bracket approximation approach to distributed optimization over directed graphs, arXiv:1711.05486 [math.OC], 2017.
Tilman Piesk, Lists of the three sets of necklaces for n=1..12
R. Pries and C. Weir, The Ekedahl-Oort type of Jacobians of Hermitian curves, arXiv preprint arXiv:1302.6261 [math.NT], 2013.
Frank Ruskey, Number of q-ary Lyndon words with given trace mod q
Frank Ruskey, Number of Lyndon words over GF(q) with given trace
N. J. A. Sloane, On single-deletion-correcting codes, arXiv:math/0207197 [math.CO], 2002; in Codes and Designs (Columbus, OH, 2000), 273-291, Ohio State Univ. Math. Res. Inst. Publ., 10, de Gruyter, Berlin, 2002.
N. J. A. Sloane, On single-deletion-correcting codes
B. R. Smith, Reducing quadratic forms by kneading sequences, Journal of Integer Sequences, 17 (2014), article 14.11.8.
P. R. Stein, Letter to N. J. A. Sloane, Jun 02 1971
J.-Y. Thibon, The cycle enumerator of unimodal permutations, arXiv:math/0102051 [math.CO], 2001.
Index entries for "core" sequences
Index entries for sequences related to Lyndon words
Index entries for sequences related to subset sums modulo m

Like A000013, but primitive necklaces. Half of A064355.
Equals A042981 + A042982.
Cf. A002823, A000016, A053633, A051841, A001037, A002075, A002076, A008683.
Cf. also A001037, A056303.
Very close to A006788 [Fisher, 1989].
bisection (odd terms) is A131203

with(numtheory); A000048 := proc(n) local d,t1; if n = 0 then RETURN(1) else t1 := 0; for d from 1 to n do if n mod d = 0 and d mod 2 = 1 then t1 := t1+mobius(d)*2^(n/d)/(2*n); fi; od; RETURN(t1); fi; end;

a[n_] := Total[ MoebiusMu[#]*2^(n/#)& /@ Select[ Divisors[n], OddQ]]/(2n); a[0] = 1; Table[a[n], {n,0,35}] (* Jean-François Alcover, Jul 21 2011 *)
a[ n_] := If[ n < 1, Boole[n == 0], DivisorSum[ n, MoebiusMu[#] 2^(n/#) &, OddQ] / (2 n)]; (* Michael Somos, Dec 20 2014 *)

A000048(n) = sumdiv(n,d,(d%2)*(moebius(d)*2^(n/d)))/(2*n) \\ Michael B. Porter, Nov 09 2009

L(n, k) = sumdiv(gcd(n,k), d, moebius(d) * binomial(n/d, k/d) );
a(n) = sum(k=0, n, if( (n+k)%2==1, L(n, k), 0 ) ) / n;
vector(55,n,a(n)) \\ Joerg Arndt, Jun 28 2012

from sympy import divisors, mobius
def a(n): return 1 if n<1 else sum(mobius(d)*2**(n//d) for d in divisors(n) if d%2)//(2*n) # Indranil Ghosh, Apr 28 2017

a(n) = (1/(2*n)) * Sum_{odd d divides n} mu(d)*2^(n/d), where mu is the Mobius function A008683.
a(n) = A056303(n) for all integer n>=2. - Michael Somos, Dec 20 2014
Sum_{k dividing m for which m/k is odd} k*a(k) = 2^(m-1). (This explains the observation that the sequence is very close to A006788. Unless m has some nontrivial odd divisors that are small relative to m, the term m*a(m) will dominate the sum. Thus, we see for instance that a(n) = A006788(n) when n has one of the forms 2^m or 2^m*p where p is an odd prime with a(2^m) < p.) - Barry R. Smith, Oct 24 2015
A000013(n) = Sum_{d|n} a(d). - Robert A. Russell, Jun 09 2019
G.f.: 1 + Sum_{k>=1} mu(2*k)*log(1 - 2*x^k)/(2*k). - Ilya Gutkovskiy, Nov 11 2019

Additional comments from Frank Ruskey, Dec 13 1999

A152175 Triangle read by rows: T(n,k) is the number of k-block partitions of an n-set up to rotations.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 3, 5, 2, 1, 1, 7, 18, 13, 3, 1, 1, 9, 43, 50, 20, 3, 1, 1, 19, 126, 221, 136, 36, 4, 1, 1, 29, 339, 866, 773, 296, 52, 4, 1, 1, 55, 946, 3437, 4281, 2303, 596, 78, 5, 1, 1, 93, 2591, 13250, 22430, 16317, 5817, 1080, 105, 5, 1, 1, 179, 7254, 51075, 115100, 110462, 52376, 13299, 1873, 147, 6, 1

Offset: 1

Vladeta Jovovic, Nov 27 2008

Number of n-bead necklace structures using exactly k different colored beads. Turning over the necklace is not allowed. Permuting the colors does not change the structure. - Andrew Howroyd, Apr 06 2017

			Triangle begins with T(1,1):
  1;
  1,   1;
  1,   1,     1;
  1,   3,     2,      1;
  1,   3,     5,      2,      1;
  1,   7,    18,     13,      3,      1;
  1,   9,    43,     50,     20,      3,      1;
  1,  19,   126,    221,    136,     36,      4,      1;
  1,  29,   339,    866,    773,    296,     52,      4,     1;
  1,  55,   946,   3437,   4281,   2303,    596,     78,     5,    1;
  1,  93,  2591,  13250,  22430,  16317,   5817,   1080,   105   , 5,   1;
  1, 179,  7254,  51075, 115100, 110462,  52376,  13299,  1873,  147,   6, 1;
  1, 315, 20125, 194810, 577577, 717024, 439648, 146124, 27654, 3025, 187, 6, 1;
  ...
For T(4,2)=3, the set partitions are AAAB, AABB, and ABAB.
For T(4,3)=2, the set partitions are AABC and ABAC.

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..1275
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
Tilman Piesk, Partition related number triangles

Columns 2-6 are A056295, A056296, A056297, A056298, A056299.
Row sums are A084423.
Partial row sums include A000013, A002076, A056292, A056293, A056294.
Cf. A075195, A087854, A008277 (set partitions), A284949 (up to reflection), A152176 (up to rotation and reflection).
A(1,n,k) in formula is the Stirling subset number A008277.
A(2,n,k) in formula is A293181; A(3,n,k) in formula is A294201.

(* Using recursion formula from Gilbert and Riordan:*)
Adn[d_, n_] := Adn[d, n] = Which[0==n, 1, 1==n, DivisorSum[d, x^# &],
  1==d, Sum[StirlingS2[n, k] x^k, {k, 0, n}],
  True, Expand[Adn[d, 1] Adn[d, n-1] + D[Adn[d, n - 1], x] x]];
Table[CoefficientList[DivisorSum[n, EulerPhi[#] Adn[#, n/#] &]/(x n), x],
   {n, 1, 10}] // Flatten (* Robert A. Russell, Feb 23 2018 *)
Adnk[d_,n_,k_] := Adnk[d,n,k] = If[n>0 && k>0, Adnk[d,n-1,k]k + DivisorSum[d,Adnk[d,n-1,k-#] &], Boole[n==0 && k==0]]
Table[DivisorSum[n,EulerPhi[#]Adnk[#,n/#,k]&]/n,{n,1,12},{k,1,n}] // Flatten (* Robert A. Russell, Oct 16 2018 *)

\\ see A056391 for Polya enumeration functions
T(n,k) = NonequivalentStructsExactly(CyclicPerms(n), k); \\ Andrew Howroyd, Oct 14 2017

R(n) = {Mat(Col([Vecrev(p/y, n) | p<-Vec(intformal(sum(m=1, n, eulerphi(m) * subst(serlaplace(-1 + exp(sumdiv(m, d, y^d*(exp(d*x + O(x*x^(n\m)))-1)/d))), x, x^m))/x))]))}
{ my(A=R(12)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Sep 20 2019

T(n,k) = (1/n)*Sum_{d|n} phi(d)*A(d,n/d,k), where A(d,n,k) = [n==0 & k==0] + [n>0 & k>0]*(k*A(d,n-1,k) + Sum_{j|d} A(d,n-1,k-j)). - Robert A. Russell, Oct 16 2018

A130293 Number of necklaces of n beads with up to n colors, with cyclic permutation {1,..,n} of the colors taken to be equivalent.

Original entry on oeis.org

1, 2, 5, 20, 129, 1316, 16813, 262284, 4783029, 100002024, 2357947701, 61917406672, 1792160394049, 56693913450992, 1946195068379933, 72057594071484456, 2862423051509815809, 121439531097819321972, 5480386857784802185957, 262144000000051200072048, 13248496640331026150086281

Offset: 1

Wouter Meeussen, Aug 06 2007, Aug 14 2007

nonn

From Olivier Gérard, Aug 01 2016: (Start)
Equivalent to the definition: number of classes of endofunctions of [n] under rotation and translation mod n.
Classes can be of size between n and n^2 depending on divisibility properties of n.
  n   n   2n   3n  ...  n^2
  --------------------------
  1   1
  2   2
  3   3                   2
  4   4    2             14
  5   5    0            124
  6   6    6   22      1282
  7   7    0          16806
For prime n, the only possible class sizes are n and n^2, the classes of size n are the n arithmetical progression modulo n so #(c-n)=n, #(c-n^2)=(n^n - n*n)/n^2 = n^(n-2)-1 and a(n) = n^(n-2)+n-1.
(End)

			The 5 necklaces for n=3 are: 000, 001, 002, 012 and 021.

Stefano Spezia, Table of n, a(n) for n = 1..350
Darij Grinberg and Peter Mao, Necklaces over a group with identity product, arXiv:2405.08937 [math.CO], 2024. See p. 22.

Cf. A002075-A002076.
Cf. A081720.
Cf. A000312: All endofunctions.
Cf. A000169: Classes under translation mod n.
Cf. A001700: Classes under sort.
Cf. A056665: Classes under rotation.
Cf. A168658: Classes under complement to n+1.
Cf. A130293: Classes under translation and rotation.
Cf. A081721: Classes under rotation and reversal.
Cf. A275549: Classes under reversal.
Cf. A275550: Classes under reversal and complement.
Cf. A275551: Classes under translation and reversal.
Cf. A275552: Classes under translation and complement.
Cf. A275553: Classes under translation, complement and reversal.
Cf. A275554: Classes under translation, rotation and complement.
Cf. A275555: Classes under translation, rotation and reversal.
Cf. A275556: Classes under translation, rotation, complement and reversal.
Cf. A275557: Classes under rotation and complement.
Cf. A275558: Classes under rotation, complement and reversal.

tor8={};ru8=Thread[ i_ ->Table[ Mod[i+k,8],{k,8}]];Do[idi=IntegerDigits[k,8,8];try= Function[w, First[temp=Union[Join @@(Table[RotateRight[w,k],{k,8}]/.#&)/@ ru8]]][idi];If[idi===try, tor8=Flatten[ {tor8,{{Length[temp],idi}}},1] ],{k,0,8^8-1}];
a[n_]:=Sum[d EulerPhi[d]n^(n/d),{d,Divisors[n]}]/n^2; Array[a,21] (* Stefano Spezia, May 21 2024 *)

a(n) = sumdiv(n, d, d*eulerphi(d)*n^(n/d))/n^2; \\ Michel Marcus, Aug 05 2016

a(n) = (1/n^2)*Sum_{d|n} d*phi(d)*n^(n/d). - Vladeta Jovovic, Aug 14 2007, Aug 24 2007

A056353 Number of bracelet structures using a maximum of three different colored beads.

Original entry on oeis.org

1, 1, 2, 3, 6, 9, 22, 40, 100, 225, 582, 1464, 3960, 10585, 29252, 80819, 226530, 636321, 1800562, 5107480, 14548946, 41538916, 118929384, 341187048, 980842804, 2824561089, 8147557742, 23536592235, 68087343148, 197216119545, 571924754778, 1660419530056, 4825588205920

Offset: 0

Marks R. Nester

nonn

Turning over will not create a new bracelet. Permuting the colors of the beads will not change the structure.

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..200
R. M. Thompson and R. T. Downs, Systematic generation of all nonequivalent closest packed stacking sequences of length N using group theory, Acta Cryst. B57 (2001), 766-771; B58 (2002), 153.

Cf. A002076, A000011, A027671, A114438, A152176.

Use de Bruijn's generalization of Polya's enumeration theorem as discussed in reference.

a(n) = Sum_{k=1..3} A152176(n, k) for n > 0. - Andrew Howroyd, Oct 25 2019

a(0)=1 prepended and terms a(28) and beyond from Andrew Howroyd, Oct 25 2019

A182522 a(0) = 1; thereafter a(2n + 1) = 3^n, a(2n + 2) = 2 * 3^n.

Original entry on oeis.org

1, 1, 2, 3, 6, 9, 18, 27, 54, 81, 162, 243, 486, 729, 1458, 2187, 4374, 6561, 13122, 19683, 39366, 59049, 118098, 177147, 354294, 531441, 1062882, 1594323, 3188646, 4782969, 9565938, 14348907, 28697814, 43046721, 86093442, 129140163, 258280326, 387420489

Offset: 0

Michael Somos, May 03 2012

Row sums of triangle in A123149. - Philippe Deléham, May 04 2012
This is simply the classic sequence A038754 prefixed by a 1. - N. J. A. Sloane, Nov 23 2017
Binomial transform is A057960.
Range of row n of the circular Pascal array of order 6. - Shaun V. Ault, May 30 2014
a(n) is also the number of achiral color patterns in a row or cycle of length n using three or fewer colors. Two color patterns are the same if we permute the colors, so ABCAB=BACBA. For a cycle, we can rotate the colors, so ABCAB=CABAB. A row is achiral if it is the same as some color permutation of its reverse. Thus the reversal of ABCAB is BACBA, which is equivalent to ABCAB when we permute A and B. A cycle is achiral if it is the same as some rotation of some color permutation of its reverse. Thus CABAB reversed is BABAC. We can permute A and B to get ABABC and then rotate to get CABAB, so CABAB is achiral. It is interesting that the number of achiral color patterns is the same for rows and cycles. - Robert A. Russell, Mar 10 2018
Also, the number of walks of length n on the graph 0--1--2--3--4 starting at vertex 0. - Sean A. Irvine, Jun 03 2025

			G.f. = 1 + x + 2*x^2 + 3*x^3 + 6*x^4 + 9*x^5 + 18*x^6 + 27*x^7 + 54*x^8 + ...
From _Robert A. Russell_, Mar 10 2018: (Start)
For a(4) = 6, the achiral color patterns for rows are AAAA, AABB, ABAB, ABBA, ABBC, and ABCA.  Note that for cycles AABB=ABBA and ABBC=ABCA.  The achiral patterns for cycles are AAAA, AAAB, AABB, ABAB, ABAC, and ABBC.  Note that AAAB and ABAC are not achiral rows.
For a(5) = 9, the achiral color patterns (for both rows and cycles) are AAAAA, AABAA, ABABA, ABBBA, AABCC, ABACA, ABBBC, ABCAB, and ABCBA. (End)

G. C. Greubel, Table of n, a(n) for n = 0..1000
Shaun V. Ault and Charles Kicey, Counting paths in corridors using circular Pascal arrays, arXiv:1407.2197 [math.CO], 2014.
Shaun V. Ault and Charles Kicey, Counting paths in corridors using circular Pascal arrays, Discrete Mathematics, Volume 332, October 2014, Pages 45-54.
Daniel Birmajer, Juan B. Gil, Jordan O. Tirrell, and Michael D. Weiner, Pattern-avoiding stabilized-interval-free permutations, arXiv:2306.03155 [math.CO], 2023.
Johann Cigler, Some remarks and conjectures related to lattice paths in strips along the x-axis, arXiv:1501.04750 [math.CO], 2015-2016.
Johann Cigler, Recurrences for certain sequences of binomial sums in terms of (generalized) Fibonacci and Lucas polynomials, arXiv:2212.02118 [math.NT], 2022.
Sean A. Irvine, Walks on Graphs.
Index entries for linear recurrences with constant coefficients, signature (0,3).

Cf. A038754 (essentially the same sequence).
Cf. A008277, A052551, A057427, A057960.
Cf. A123149, A140735, A293181, A304973.
Also row sums of triangle in A169623.
Column 3 of A305749.
Cf. A124302 (oriented), A001998 (unoriented), A107767 (chiral), for rows, varying offsets.
Cf. A002076 (oriented), A056353 (unoriented), A320743 (chiral), for cycles.

I:=[1,1,2]; [n le 3 select I[n] else 3*Self(n-2): n in [1..40]]; // Bruno Berselli, Mar 19 2013

Join[{1}, RecurrenceTable[{a[1]==1, a[2]==2, a[n]==3 a[n-2]}, a, {n, 40}]] (* Bruno Berselli, Mar 19 2013 *)
CoefficientList[Series[(1+x-x^2)/(1-3*x^2), {x,0,50}], x] (* G. C. Greubel, Apr 14 2017 *)
Table[If[EvenQ[n], StirlingS2[(n+6)/2,3] - 4 StirlingS2[(n+4)/2,3] + 5 StirlingS2[(n+2)/2,3] - 2 StirlingS2[n/2,3], StirlingS2[(n+5)/2,3] - 3 StirlingS2[(n+3)/2,3] + 2 StirlingS2[(n+1)/2,3]], {n,0,40}] (* Robert A. Russell, Oct 21 2018 *)
Join[{1},Table[If[EvenQ[n], 2 3^((n-2)/2), 3^((n-1)/2)],{n,40}]] (* Robert A. Russell, Oct 28 2018 *)

makelist(if n=0 then 1 else (1+mod(n-1,2))*3^floor((n-1)/2), n, 0, 40); /* Bruno Berselli, Mar 19 2013 */

{a(n) = if( n<1, n==0, n--; (n%2 + 1) * 3^(n \ 2))}

my(x='x+O('x^50)); Vec((1+x-x^2)/(1-3*x^2)) \\ G. C. Greubel, Apr 14 2017

def A182522(n): return (3 -(3-2*sqrt(3))*((n+1)%2))*3^((n-3)/2) + int(n==0)/3
[A182522(n) for n in range(41)] # G. C. Greubel, Jul 17 2023

G.f.: (1 + x - x^2) / (1 - 3*x^2).
Expansion of 1 / (1 - x / (1 - x / (1 + x / (1 + x)))) in powers of x.
a(n+1) = A038754(n).
a(n) = Sum_{k=0..n} A123149(n,k). - Philippe Deléham, May 04 2012
a(n) = (3-(1+(-1)^n)*(3-2*sqrt(3))/2)*sqrt(3)^(n-3) for n>0, a(0)=1. - Bruno Berselli, Mar 19 2013
a(0) = 1, a(1) = 1, a(n) = a(n-1) + a(n-2) if n is odd, and a(n) = a(n-1) + a(n-2) + a(n-3) if n is even. - Jon Perry, Mar 19 2013
For odd n = 2m-1, a(2m-1) = T(m,1)+T(m,2)+T(m,3) for triangle T(m,k) of A140735; for even n = 2m, a(2m) = T(m,1)+T(m,2)+T(m,3) for triangle T(m,k) of A293181. - Robert A. Russell, Mar 10 2018
From Robert A. Russell, Oct 21 2018: (Start)
a(2m) = S2(m+3,3) - 4*S2(m+2,3) + 5*S2(m+1,3) - 2*S2(m,3).
a(2m-1) = S2(m+2,3) - 3*S2(m+1,3) + 2*S2(m,3), where S2(n,k) is the Stirling subset number A008277.
a(n) = 2*A001998(n-1) - A124302(n) = A124302(n) - 2*A107767(n-1) = A001998(n-1) - A107767(n-1).
a(n) = 2*A056353(n) - A002076(n) = A002076(n) - 2*A320743(n) = A056353(n) - A320743(n).
a(n) = A057427(n) + A052551(n-2) + A304973(n). (End)

Edited by Bruno Berselli, Mar 19 2013

Definition simplified by N. J. A. Sloane, Nov 23 2017

A002075 Number of equivalence classes with primitive period n of base 3 necklaces, where necklaces are equivalent under rotation and permutation of symbols.

Original entry on oeis.org

1, 1, 2, 4, 8, 22, 52, 140, 366, 992, 2684, 7404, 20440, 56992, 159440, 448540, 1266080, 3587610, 10195276, 29057520, 83018728, 237737984, 682196948, 1961323740, 5648590728, 16294032160, 47071589778, 136171440600

Offset: 1

N. J. A. Sloane

N. J. Fine, Classes of periodic sequences, Illinois J. Math., 2 (1958), 285-302.
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).

Index entries for sequences related to necklaces

Cf. A000013, A000048, A002076.

Reference gives formula.

Sequence A002076 can be found as follows: Let F3(n) = this sequence, F3*(n) = function from A002076. Then F3*(n) = Sum_{ d divides n } F3(d).

Better description and more terms from Mark Weston (mweston(AT)uvic.ca), Oct 07 2001

A056296 Number of n-bead necklace structures using exactly three different colored beads.

Original entry on oeis.org

0, 0, 1, 2, 5, 18, 43, 126, 339, 946, 2591, 7254, 20125, 56450, 158355, 446618, 1262225, 3580686, 10181479, 29032254, 82968843, 237645250, 682014587, 1960981598, 5647919645, 16292761730, 47069104613, 136166703562, 394418199725, 1143822046786, 3320790074371

Offset: 1

Marks R. Nester

nonn

Turning over the necklace is not allowed. Colors may be permuted without changing the necklace structure.

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]

E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

Column 3 of A152175.

Cf. A000013, A002076, A056283.

Adn[d_, n_] := Adn[d, n] = If[1==n, DivisorSum[d, x^# &], Expand[Adn[d, 1] Adn[d, n-1] + D[Adn[d, n-1], x] x]];
Table[Coefficient[DivisorSum[n, EulerPhi[#] Adn[#, n/#] &]/n , x, 3], {n, 1, 40}] (* Robert A. Russell, Feb 23 2018 *)
Table[(1/n) DivisorSum[n, EulerPhi[#] Which[Divisible[#,6], StirlingS2[n/#+2,3] - StirlingS2[n/#+1,3], Divisible[#,3], StirlingS2[n/#+2,3] - 3 StirlingS2[n/#+1,3] + 3 StirlingS2[n/#,3], Divisible[#,2], 2 StirlingS2[n/#+1,3] - 2 StirlingS2[n/#,3], True, StirlingS2[n/#,3]] &],{n, 1, 40}] (* Robert A. Russell, May 29 2018*)
mx = 40; Drop[CoefficientList[Series[-Sum[(EulerPhi[d] / d) Which[ Divisible[d, 6], Log[1 - 3x^d] - Log[1 - 2x^d], Divisible[d, 3] , (Log[1 - 3x^d] - Log[1 - 2x^d] + Log[1 - x^d]) / 2, Divisible[d, 2], (2 Log[1 - 3x^d] - 3 Log[1 - 2x^d]) / 3, True, (Log[1 - 3x^d] - 3Log[1 - 2x^d] + 3 Log[1 - x^d]) / 6], {d, 1, mx}], {x, 0, mx}], x], 1] (* Robert A. Russell, May 29 2018 *)

a(n) = A002076(n) - A000013(n).
From Robert A. Russell, May 29 2018: (Start)
a(n) = (1/n) * Sum_{d|n} phi(d) * ([d==0 mod 6] * (S2(n/d + 2, 3) - S2(n/d + 1, 3)) + [d==3 mod 6] * (S2(n/d + 2, 3) - 3*S2(n/d + 1, 3) + 3*S2(n/d, 3)) + [d==2 mod 6 | d==4 mod 6] * (2*S2(n/d + 1, 3) - 2*S2(n/d, 3)) + [d==1 mod 6 | d=5 mod 6] * S2(n/d, 3)), where S2(n,k) is the Stirling subset number, A008277.
G.f.: -Sum_{d>0} (phi(d) / d) * ([d==0 mod 6] * (log(1-3x^d) - log(1-x^d)) + [d==3 mod 6] * (log(1-3x^d) - log(1-2x^d) + log(1-x^d)) / 2 + [d==2 mod 6 | d==4 mod 6] * (2*log(1-3x^d) - 3*log(1-2x^d)) / 3 + [d==1 mod 6 | d=5 mod 6] * (log(1-3x^d) - 3*log(1-2x^d) + 3*log(1-x^d)) / 6).
(End)

A056297 Number of n-bead necklace structures using exactly four different colored beads.

Original entry on oeis.org

0, 0, 0, 1, 2, 13, 50, 221, 866, 3437, 13250, 51075, 194810, 742651, 2823766, 10738881, 40843370, 155494751, 592614050, 2261625725, 8643289534, 33080920607, 126797503250, 486710971595, 1870851589554, 7201014763285, 27752927359726, 107092397450897

Offset: 1

Marks R. Nester

nonn

Turning over the necklace is not allowed. Colors may be permuted without changing the necklace structure.

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]

E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

Column 4 of A152175.

Cf. A002076, A056284, A056292.

From Robert A. Russell, May 29 2018: (Start)
Adn[d_, n_] := Adn[d, n] = If[1==n, DivisorSum[d, x^# &], Expand[Adn[d, 1] Adn[d, n-1] + D[Adn[d, n-1], x] x]];
Table[Coefficient[DivisorSum[n, EulerPhi[#] Adn[#, n/#] &]/n , x, 4], {n, 1, 40}] (* after Gilbert and Riordan *)
Table[(1/n) DivisorSum[n, EulerPhi[#] Which[ Divisible[#,12], StirlingS2[n/#+3,4] - 3 StirlingS2[n/#+2,4] + 2 StirlingS2[n/#+1,4], Divisible[#,6], 3 StirlingS2[n/#+2,4] - 9 StirlingS2[n/#+1,4] + 6 StirlingS2[n/#,4], Divisible[#,4], StirlingS2[n/#+3,4] - 5 StirlingS2[n/#+2,4] + 10 StirlingS2[n/#+1,4] - 8 StirlingS2[n/#,4], Divisible[#,3], 2 StirlingS2[n/#+2,4] - 8 StirlingS2[n/#+1,4] + 9 StirlingS2[n/#,4], Divisible[#,2], StirlingS2[n/#+2,4] - StirlingS2[n/#+1,4] - 2 StirlingS2[n/#,4], True, StirlingS2[n/#,4]] &],{n, 1, 40}]
mx = 40; Drop[CoefficientList[Series[-Sum[(EulerPhi[d] / d) Which[ Divisible[d, 12], Log[1-4x^d] - Log[1-3x^d], Divisible[d, 6], (3 Log[1-4x^d] - 4 Log[1-3x^d]) / 4, Divisible[d, 4], (2 Log[1-4x^d] - 2 Log[1-3x^d] + Log[1-x^d]) / 3, Divisible[d, 3], (3 Log[1-4x^d] - 4 Log[1-3x^d] + 2 Log[1-2x^d] - 4 Log[1-x^d]) / 8, Divisible[d, 2], (5 Log[1-4x^d] - 8 Log[1-3x^d] + 4 Log[1-x^d]) / 12, True, (Log[1-4x^d] - 4 Log[1-3x^d] + 6 Log[1-2x^d] - 4 Log[1-x^d]) / 24], {d, 1, mx}], {x, 0, mx}], x], 1]
(End)

a(n) = A056292(n) - A002076(n).
From Robert A. Russell, May 29 2018: (Start)
a(n) = (1/n) * Sum_{d|n} phi(d) * ([d==0 mod 12] * (S2(n/d + 3, 4) - 3*S2(n/d+2,4) + 2*S2(n/d + 1, 4)) + [d==6 mod 12] * (3*S2(n/d + 2, 4) - 9*S2(n/d + 1, 4) + 3*S2(n/d, 4)) + [d==4 mod 12 | d==8 mod 12] * (S2(n/d + 3, 4) - 5*S2(n/d + 2, 4) - 10*S2(n/d + 1, 4) - 8*S2(n/d, 4)) + [d==3 mod 12 | d=9 mod 12] * (2*S2(n/d + 2, 4) - 8*S2(n/d + 1, 4) - 2*S2(n/d,4)) + [d==2 mod 12 | d==10 mod 12] * (S2(n/d + 2, 4) - S2(n/d + 1, 4) + 9*S2(n/d, 4)) + [d mod 12 in {1,5,7,11}] * S2(n/d, 4)), where S2(n,k) is the Stirling subset number, A008277.
G.f.: -Sum_{d>0} (phi(d) / d) * ([d==0 mod 12] * (log(1-4x^d) - log(1-3x^d)) +[d==6 mod 12] * (3*log(1-4x^d) - 4*log(1-3x^d)) / 4 + [d==4 mod 12 | d==8 mod 12] * (2*log(1-4x^d) - 2*log(1-3x^d) + log(1-x^d)) / 3 + [d==3 mod 12 | d==9 mod 12] * (3*log(1-4x^d) - 4*log(1-3x^d) + 2*log(1-2x^d) - 4*log(1-x^d)) / 8 + [d==2 mod 12 | d=10 mod 12] * (5*log(1-4x^d) - 8*log(1-3x^d) + 4*log(1-x^d)) / 12 + [d mod 12 in {1,5,7,11}] * (log(1-4x^d) - 4*log(1-3x^d) + 6*log(1-2x^d) - 4*log(1-x^d)) / 24).
(End)

A320743 Number of chiral pairs of color patterns (set partitions) in a cycle of length n using 3 or fewer colors (subsets).

Original entry on oeis.org

0, 0, 0, 0, 0, 4, 13, 46, 144, 420, 1221, 3474, 9856, 27794, 78632, 222156, 629760, 1787440, 5087797, 14509580, 41479867, 118811286, 341009901, 980488510, 2824029648, 8146494860, 23534997912, 68084154502, 197211336576, 571915188840, 1660405181149, 4825559508106, 14038010213051, 40875403561680, 119122661856133, 347441159864556, 1014152747485696

Offset: 1

Robert A. Russell, Oct 21 2018

Two color patterns are equivalent if the colors are permuted.
Adnk[d,n,k] in Mathematica program is coefficient of x^k in A(d,n)(x) in Gilbert and Riordan reference.
There are nonrecursive formulas, generating functions, and computer programs for A002076 and A182522, which can be used in conjunction with the first formula.

			For a(6)=4, the chiral pairs are AAABBC-AAABCC, AABABC-AABCAC, AABACB-AABCAB, and AABACC-AABBAC.

Andrew Howroyd, Table of n, a(n) for n = 1..200
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

Column 3 of A320742.

Cf. A002076 (oriented), A056353 (unoriented), A182522 (achiral).

Adnk[d_,n_,k_] := Adnk[d,n,k] = If[n>0 && k>0, Adnk[d,n-1,k]k + DivisorSum[d, Adnk[d,n-1,k-#]&], Boole[n == 0 && k == 0]]
Ach[n_, k_] := Ach[n, k] = If[n<2, Boole[n==k && n>=0], k Ach[n-2,k] + Ach[n-2,k-1] + Ach[n-2,k-2]] (* A304972 *)
k=3; Table[Sum[(DivisorSum[n,EulerPhi[#] Adnk[#,n/#,j]&]/n - Ach[n,j])/2, {j, k}], {n,40}]

a(n) = (A002076(n) - A182522(n)) / 2 = A002076(n) - A056353(n) = A056353(n) - A182522(n).
a(n) = Sum_{j=1..k} -Ach(n,j)/2 + (1/2n)*Sum_{d|n} phi(d)*A(d,n/d,j), where k=3 is the maximum number of colors, Ach(n,k) = [n>=0 & n<2 & n==k] + [n>1]*(k*Ach(n-2,k) + Ach(n-2,k-1) + Ach(n-2,k-2)), and A(d,n,k) = [n==0 & k==0] + [n>0 & k>0]*(k*A(d,n-1,k) + Sum_{j|d} A(d,n-1,k-j)).
a(n) = A059053(n) + A320643(n).

A320747 Array read by antidiagonals: T(n,k) is the number of color patterns (set partitions) in an oriented cycle of length n using k or fewer colors (subsets).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 3, 4, 1, 1, 2, 3, 6, 4, 1, 1, 2, 3, 7, 9, 8, 1, 1, 2, 3, 7, 11, 26, 10, 1, 1, 2, 3, 7, 12, 39, 53, 20, 1, 1, 2, 3, 7, 12, 42, 103, 146, 30, 1, 1, 2, 3, 7, 12, 43, 123, 367, 369, 56, 1, 1, 2, 3, 7, 12, 43, 126, 503, 1235, 1002, 94, 1, 1, 2, 3, 7, 12, 43, 127, 539, 2008, 4439, 2685, 180, 1, 1, 2, 3, 7, 12, 43, 127, 543, 2304, 8720, 15935, 7434, 316, 1, 1, 2, 3, 7, 12, 43, 127, 544, 2356, 11023, 38365, 58509, 20441, 596, 1

Offset: 1

Robert A. Russell, Oct 21 2018

Two color patterns are equivalent if the colors are permuted. An oriented cycle counts each chiral pair as two.
Adnk[d,n,k] in Mathematica program is coefficient of x^k in A(d,n)(x) in Gilbert and Riordan reference.
In other words, the number of n-bead necklace structures using a maximum of k different colored beads. - Andrew Howroyd, Oct 30 2019

			Array begins with T(1,1):
1   1    1     1      1      1      1      1      1      1      1      1 ...
1   2    2     2      2      2      2      2      2      2      2      2 ...
1   2    3     3      3      3      3      3      3      3      3      3 ...
1   4    6     7      7      7      7      7      7      7      7      7 ...
1   4    9    11     12     12     12     12     12     12     12     12 ...
1   8   26    39     42     43     43     43     43     43     43     43 ...
1  10   53   103    123    126    127    127    127    127    127    127 ...
1  20  146   367    503    539    543    544    544    544    544    544 ...
1  30  369  1235   2008   2304   2356   2360   2361   2361   2361   2361 ...
1  56 1002  4439   8720  11023  11619  11697  11702  11703  11703  11703 ...
1  94 2685 15935  38365  54682  60499  61579  61684  61689  61690  61690 ...
1 180 7434 58509 173609 284071 336447 349746 351619 351766 351772 351773 ...
For T(4,2)=4, the patterns are AAAA, AAAB, AABB, and ABAB.
For T(4,3)=6, the patterns are the above four, AABC and ABAC.

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..1275
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

Partial row sums of A152175.
Columns 1-6 are A057427, A000013, A002076, A056292, A056293, A056294.
For increasing k, columns converge to A084423.
Cf. A320748 (unoriented), A320742 (chiral), A305749 (achiral).

Adnk[d_,n_,k_] := Adnk[d,n,k] = If[n>0 && k>0, Adnk[d,n-1,k]k + DivisorSum[d, Adnk[d,n-1,k-#] &], Boole[n==0 && k==0]]
Table[Sum[DivisorSum[n, EulerPhi[#] Adnk[#,n/#,j] &], {j,k-n+1}]/n, {k,15}, {n,k}] // Flatten

\\ R is A152175 as square matrix
R(n) = {Mat(Col([Vecrev(p/y, n) | p<-Vec(intformal(sum(m=1, n, eulerphi(m) * subst(serlaplace(-1 + exp(sumdiv(m, d, y^d*(exp(d*x + O(x*x^(n\m)))-1)/d))), x, x^m))/x))]))}
T(n)={my(M=R(n)); for(i=2, n, M[,i] += M[,i-1]); M}
{ my(A=T(12)); for(n=1, #A, print(A[n, ])) } \\ Andrew Howroyd, Nov 03 2019

T(n,k) = (1/n)*Sum_{j=1..k} Sum_{d|n} phi(d)*A(d,n/d,j), where A(d,n,k) = [n==0 & k==0] + [n>0 & k>0]*(k*A(d,n-1,k) + Sum_{j|d} A(d,n-1,k-j)).

T(n,k) = A320748(n,k) + A320742(n,k) = 2*A320748(n,k) - A305749(n,k) = A305749(n,k) + 2*A320742(n,k).

cp's OEIS Frontend

A000048 Number of n-bead necklaces with beads of 2 colors and primitive period n, when turning over is not allowed but the two colors can be interchanged.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A152175 Triangle read by rows: T(n,k) is the number of k-block partitions of an n-set up to rotations.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A130293 Number of necklaces of n beads with up to n colors, with cyclic permutation {1,..,n} of the colors taken to be equivalent.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A056353 Number of bracelet structures using a maximum of three different colored beads.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A182522 a(0) = 1; thereafter a(2*n + 1) = 3^n, a(2*n + 2) = 2 * 3^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

PARI

PARI

SageMath

Formula

Extensions

A002075 Number of equivalence classes with primitive period n of base 3 necklaces, where necklaces are equivalent under rotation and permutation of symbols.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A182522 a(0) = 1; thereafter a(2n + 1) = 3^n, a(2n + 2) = 2 * 3^n.