A320743 -id:A320743 - cp's OEIS frontend

A002076 Number of equivalence classes of base-3 necklaces of length n, where necklaces are considered equivalent under both rotations and permutations of the symbols.

1, 1, 2, 3, 6, 9, 26, 53, 146, 369, 1002, 2685, 7434, 20441, 57046, 159451, 448686, 1266081, 3588002, 10195277, 29058526, 83018783, 237740670, 682196949, 1961331314, 5648590737, 16294052602, 47071590147, 136171497650, 394427456121, 1143839943618, 3320824711205

Offset: 0

N. J. A. Sloane

Number of set partitions of an oriented cycle of length n with 3 or fewer subsets. - Robert A. Russell, Nov 05 2018

			E.g., a(2) = 2 as there are two equivalence classes of the 9 strings {00,01,02,10,11,12,20,21,22}: {00,11,22} form one equivalence class and {01,02,10,12,20,21} form the other. To see that (for example) 01 and 02 are equivalent, rotate 01 to 10 and then subtract 1 mod 3 from each element in 10 to get 02.
For a(6)=26, there are 18 achiral patterns (AAAAAA, AAAAAB, AAAABB, AAABAB, AAABBB, AABAAB, AABABB, ABABAB, AAAABC, AAABAC, AAABCB, AABAAC, AABBCC, AABCBC, AABCCB, ABABAC, ABACBC, ABCABC) and 8 chiral patterns in four pairs (AAABBC-AAABCC, AABABC-AABCAC, AABACB-AABCAB, AABACC-AABBAC). - _Robert A. Russell_, Nov 05 2018

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

Vincenzo Librandi, Table of n, a(n) for n = 0..500
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.
Marko Riedel, Necklaces with swappable colors by Power Group Enumeration
Marko Riedel, Maple code for any necklace size, any number of swappable colors, by Power Group Enumeration.
N. J. A. Sloane, Maple code for this and related sequences
Index entries for sequences related to necklaces

Cf. A000013, A000048, A002075.

Cf. A056353 (unoriented), A320743 (chiral), A182522 (achiral).

Adn[d_, n_] := Module[{ c, t1, t2}, t2 = 0; For[c = 1, c <= d, c++, If[Mod[d, c] == 0 , t2 = t2 + (x^c/c)*(E^(c*z) - 1)]]; t1 = E^t2; t1 = Series[t1, {z, 0, n+1}]; Coefficient[t1, z, n]*n!]; Pn[n_] := Module[{ d, e, t1}, t1 = 0; For[d = 1, d <= n, d++, If[Mod[n, d] == 0, t1 = t1 + EulerPhi[d]*Adn[d, n/d]/n]]; t1/(1 - x)]; Pnq[n_, q_] := Module[{t1}, t1 = Series[Pn[n], {x, 0, q+1}] ; Coefficient[t1, x, q]]; a[n_] := Pnq[n, 3]; Print[1]; Table[Print[an = a[n]]; an, {n, 1, 28}] (* Jean-François Alcover, Oct 04 2013, after N. J. A. Sloane's Maple code *)
(* This Mathematica program uses Gilbert and Riordan's recurrence formula, which they recommend for calculations: *)
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]];
Join[{1},Table[SeriesCoefficient[DivisorSum[n, EulerPhi[#] Adn[#, n/#] &] /(n (1 - x)), {x, 0, 3}], {n,40}]]  (* Robert A. Russell, Feb 24 2018 *)
From Robert A. Russell, May 29 2018: (Start)
Join[{1},Table[(1/n) DivisorSum[n, EulerPhi[#] Which[Divisible[#, 6], 3 StirlingS2[n/#+2, 3] - 9 StirlingS2[n/#+1, 3] + 6 StirlingS2[n/#, 3], Divisible[#, 3], 2 StirlingS2[n/#+2, 3] - 7 StirlingS2[n/#+1, 3] + 6 StirlingS2[n/#, 3], Divisible[#, 2], 2 StirlingS2[n/#+2, 3] - 6 StirlingS2[n/#+1, 3] + 4 StirlingS2[n/#, 3], True, StirlingS2[n/#+2, 3] - 4 StirlingS2[n/#+1, 3] + 4 StirlingS2[n/#, 3]] &], {n,40}]] (* or *)
mx = 40; CoefficientList[Series[1 - Sum[(EulerPhi[d] / d) Which[
  Divisible[d, 6], Log[1 - 3x^d], Divisible[d, 3], (Log[1 - 3x^d] +
  Log[1 - x^d]) / 2, Divisible[d, 2], 2 Log[1 - 3x^d] / 3, True, (Log[1 - 3x^d] + 3 Log[1 - x^d]) / 6], {d, 1, mx}], {x, 0, mx}], x]
(End)
(* Adnk(n,d,k) is coefficient of x^k in A(d,n)(x) from Gilbert & Riordan *)
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]]
k=3; Join[{1},Table[Sum[DivisorSum[n,EulerPhi[#] Adnk[#,n/#,j] &],{j,k}]/n,{n,40}]] (* Robert A. Russell, Nov 05 2018 *)

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

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

a(0)=1 prepended by Robert A. Russell, Nov 05 2018

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

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

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 1, 0, 0, 0, 0, 0, 0, 6, 13, 2, 0, 0, 0, 0, 0, 0, 6, 30, 46, 7, 0, 0, 0, 0, 0, 0, 6, 34, 130, 144, 12, 0, 0, 0, 0, 0, 0, 6, 34, 181, 532, 420, 31, 0, 0, 0, 0, 0, 0, 6, 34, 190, 871, 2006, 1221, 58, 0, 0, 0, 0, 0, 0, 6, 34, 190, 996, 4016, 7626, 3474, 126, 0, 0, 0, 0, 0, 0, 6, 34, 190, 1011, 5070, 18526, 28401, 9856, 234, 0

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.

			Array begins with T(1,1):
0  0    0     0     0      0      0      0      0      0      0      0 ...
0  0    0     0     0      0      0      0      0      0      0      0 ...
0  0    0     0     0      0      0      0      0      0      0      0 ...
0  0    0     0     0      0      0      0      0      0      0      0 ...
0  0    0     0     0      0      0      0      0      0      0      0 ...
0  0    4     6     6      6      6      6      6      6      6      6 ...
0  1   13    30    34     34     34     34     34     34     34     34 ...
0  2   46   130   181    190    190    190    190    190    190    190 ...
0  7  144   532   871    996   1011   1011   1011   1011   1011   1011 ...
0 12  420  2006  4016   5070   5328   5352   5352   5352   5352   5352 ...
0 31 1221  7626 18526  26454  29215  29705  29740  29740  29740  29740 ...
0 58 3474 28401 85101 139484 165164 171556 172415 172466 172466 172466 ...
For T(6,4)=6, the chiral pairs are AAABBC-AAABCC, AABABC-AABCAC, AABACB-AABCAB, AABACC-AABBAC, AABACD-AABCAD and AABCBD-AABCDC.

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 A320647.
Columns 1-6 are A000004, A059053, A320743, A320744, A320745, A320746
For increasing k, columns converge to A320749.
Cf. A320747 (oriented), A320748 (unoriented), 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]]
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 *)
Table[Sum[(DivisorSum[n, EulerPhi[#] Adnk[#,n/#,j]&]/n - Ach[n,j])/2, {j,k-n+1}], {k,15}, {n,k}] // Flatten

\\ Ach is A304972 and R is A152175 as square matrices.
Ach(n)={my(M=matrix(n, n, i, k, i>=k)); for(i=3, n, for(k=2, n, M[i, k]=k*M[i-2, k] + M[i-2, k-1] + if(k>2, M[i-2, k-2]))); M}
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) - Ach(n))/2); 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) = Sum_{j=1..k} -Ach(n,j)/2 + (1/2n)*Sum_{d|n} phi(d)*A(d,n/d,j), where 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)).

T(n,k) = (A320747(n,k) - A305749(n,k)) / 2 = A320747(n,k) - A320748(n,k)= A320748(n,k) - A305749(n,k).

cp's OEIS Frontend

A002076 Number of equivalence classes of base-3 necklaces of length n, where necklaces are considered equivalent under both rotations and permutations of the symbols.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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