A056353 -id:A056353 - cp's OEIS frontend

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

1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 3, 5, 2, 1, 1, 7, 14, 11, 3, 1, 1, 8, 31, 33, 16, 3, 1, 1, 17, 82, 137, 85, 27, 4, 1, 1, 22, 202, 478, 434, 171, 37, 4, 1, 1, 43, 538, 1851, 2271, 1249, 338, 54, 5, 1, 1, 62, 1401, 6845, 11530, 8389, 3056, 590, 70, 5, 1, 1, 121, 3838, 26148

Offset: 1

Vladeta Jovovic, Nov 27 2008

Number of bracelet structures of length n using exactly k different colored beads. Turning over will not create a new bracelet. Permuting the colors of the beads will not change the structure. - Andrew Howroyd, Apr 06 2017
The number of achiral structures (A) is given in A140735 (odd n) and A293181 (even n).  The number of achiral structures plus twice the number of chiral pairs (A+2C) is given in A152175.  These can be used to determine A+C by taking half their average, as is done in the Mathematica program. - Robert A. Russell, Feb 24 2018
T(n,k)=pi_k(C_n) which is the number of non-equivalent partitions of the cycle on n vertices, with exactly k parts. Two partitions P1 and P2 of a graph G are said to be equivalent if there is a nontrivial automorphism of G which maps P1 onto P2. - Mohammad Hadi Shekarriz, Aug 21 2019

			Triangle begins:
  1;
  1,  1;
  1,  1,   1;
  1,  3,   2,    1;
  1,  3,   5,    2,    1;
  1,  7,  14,   11,    3,    1;
  1,  8,  31,   33,   16,    3,   1;
  1, 17,  82,  137,   85,   27,   4,  1;
  1, 22, 202,  478,  434,  171,  37,  4, 1;
  1, 43, 538, 1851, 2271, 1249, 338, 54, 5, 1;
  ...

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
B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
Tilman Piesk, Partition related number triangles
Marko Riedel, Bracelets with swappable colors classified by the distribution of colors, Power Group Enumeration algorithm
Marko Riedel, Maple code for the number of bracelets with some number of swappable colors by Power Group Enumeration
Mohammad Hadi Shekarriz, GAP Program

Columns 2-6 are A056357, A056358, A056359, A056360, A056361.
Row sums are A084708.
Partial row sums include A000011, A056353, A056354, A056355, A056356.
Cf. A081720, A273891, A008277 (set partitions), A284949 (up to reflection), A152175 (up to rotation).

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]];
Ach[n_, k_] := Ach[n, k] = Switch[k, 0, If[0==n, 1, 0], 1, If[n>0, 1, 0],
  (* else *) _, If[OddQ[n], Sum[Binomial[(n-1)/2, i] Ach[n-1-2i, k-1],
  {i, 0, (n-1)/2}], Sum[Binomial[n/2-1, i] (Ach[n-2-2i, k-1]
  + 2^i Ach[n-2-2i, k-2]), {i, 0, n/2-1}]]] (* achiral loops of length n, k colors *)
Table[(CoefficientList[DivisorSum[n, EulerPhi[#] Adn[#, n/#] &]/(x n), x]
+ Table[Ach[n, k],{k,1,n}])/2, {n, 1, 20}] // Flatten (* Robert A. Russell, Feb 24 2018 *)

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

\\ 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)={(R(n) + Ach(n))/2}
{ my(A=T(12)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Sep 20 2019

A027671 Number of necklaces with n beads of 3 colors, allowing turning over.

Original entry on oeis.org

1, 3, 6, 10, 21, 39, 92, 198, 498, 1219, 3210, 8418, 22913, 62415, 173088, 481598, 1351983, 3808083, 10781954, 30615354, 87230157, 249144711, 713387076, 2046856566, 5884491500, 16946569371, 48883660146, 141217160458, 408519019449, 1183289542815

Offset: 0

Alford Arnold

Number of bracelets of n beads using up to three different colors. - Robert A. Russell, Sep 24 2018

			For n=2, the six bracelets are AA, AB, AC, BB, BC, and CC. - _Robert A. Russell_, Sep 24 2018

J. L. Fisher, Application-Oriented Algebra (1977), ISBN 0-7002-2504-8, circa p. 215.
M. Gardner, "New Mathematical Diversions from Scientific American" (Simon and Schuster, New York, 1966), pp. 245-246.

T. D. Noe, Table of n, a(n) for n = 0..200
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
M. Taniguchi, H. Du, and J. S. Lindsey, Enumeration of virtual libraries of combinatorial modular macrocyclic (bracelet, necklace) architectures and their linear counterparts, Journal of Chemical Information and Modeling, 53 (2013), 2203-2216.
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.
Eric Weisstein's World of Mathematics, Necklace.
Index entries for sequences related to bracelets

Cf. A056353, A114438.
a(n) = A081720(n,3), n >= 3. - Wolfdieter Lang, Jun 03 2012
Column 3 of A051137.
a(n) = A278639(n) + A182751(n+1).
Equals A001867 - A278639.

Needs["Combinatorica`"];  Join[{1}, Table[CycleIndex[DihedralGroup[n], s]/.Table[s[i]->3, {i,1,n}], {n,1,30}]] (* Geoffrey Critzer, Sep 29 2012 *)
Needs["Combinatorica`"]; Join[{1}, Table[NumberOfNecklaces[n, 3, Dihedral], {n, 30}]] (* T. D. Noe, Oct 02 2012 *)
mx=40;CoefficientList[Series[(1-Sum[ EulerPhi[n]*Log[1-3*x^n]/n,{n,mx}]+(1+3 x+3 x^2)/(1-3 x^2))/2,{x,0,mx}],x] (* Herbert Kociemba, Nov 02 2016 *)
t[n_, k_] := (For[t1 = 0; d = 1, d <= n, d++, If[Mod[n, d] == 0, t1 = t1 + EulerPhi[d]*k^(n/d)]]; If[EvenQ[n], (t1 + (n/2)*(1+k)*k^(n/2))/(2*n), (t1 + n*k^((n+1)/2))/(2*n)]); a[0] = 1; a[n_] := t[n, 3]; Array[a, 30, 0] (* Jean-François Alcover, Nov 02 2017, after Maple code for A081720 *)
k=3; Prepend[Table[DivisorSum[n, EulerPhi[#] k^(n/#) &]/(2n) + (k^Floor[(n+1)/2] + k^Ceiling[(n+1)/2])/4, {n, 1, 30}], 1] (* Robert A. Russell, Sep 24 2018 *)

a(n,k=3) = if(n==0,1,(k^floor((n+1)/2) + k^ceil((n+1)/2))/4 + (1/(2*n))* sumdiv(n, d, eulerphi(d)*k^(n/d) ) );
vector(55,n,a(n-1)) \\ Joerg Arndt, Oct 20 2019

G.f.: (1 - Sum_{n>=1} phi(n)*log(1 - 3*x^n)/n + (1+3*x+3*x^2)/(1-3*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=3 is the maximum number of colors. - Robert A. Russell, Sep 24 2018
a(0) = 1; a(n) = (k^floor((n+1)/2) + k^ceiling((n+1)/2))/4 + (1/(2*n))*Sum_{i=1..n} k^gcd(n,i), where k=3 is the maximum number of colors.
(See A075195 formulas.) - Richard L. Ollerton, May 04 2021
2*a(n) = A182751(n+1) + A001867(n), n>0.

More terms from Christian G. Bower

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.

Original entry on oeis.org

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

A320748 Array read by antidiagonals: T(n,k) is the number of color patterns (set partitions) in an unoriented 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, 22, 9, 1, 1, 2, 3, 7, 12, 33, 40, 18, 1, 1, 2, 3, 7, 12, 36, 73, 100, 23, 1, 1, 2, 3, 7, 12, 37, 89, 237, 225, 44, 1, 1, 2, 3, 7, 12, 37, 92, 322, 703, 582, 63, 1, 1, 2, 3, 7, 12, 37, 93, 349, 1137, 2433, 1464, 122, 1, 1, 2, 3, 7, 12, 37, 93, 353, 1308, 4704, 8309, 3960, 190, 1, 1, 2, 3, 7, 12, 37, 93, 354, 1345, 5953, 19839, 30108, 10585, 362, 1

Offset: 1

Robert A. Russell, Oct 21 2018

Two color patterns are equivalent if the colors are permuted. An unoriented cycle counts each chiral pair as one, i.e., they are equivalent.
Adnk[d,n,k] in Mathematica program is coefficient of x^k in A(d,n)(x) in Gilbert and Riordan reference.
T(n,k)=Pi_k(C_n) which is the number of non-equivalent partitions of the cycle on n vertices, with at most k parts. Two partitions P1 and P2 of a graph G are said to be equivalent if there is a nontrivial automorphism of G which maps P1 onto P2. - Bahman Ahmadi, Aug 21 2019
In other words, the number of n-bead bracelet 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   22    33    36     37     37     37     37     37     37     37 ...
1   9   40    73    89     92     93     93     93     93     93     93 ...
1  18  100   237   322    349    353    354    354    354    354    354 ...
1  23  225   703  1137   1308   1345   1349   1350   1350   1350   1350 ...
1  44  582  2433  4704   5953   6291   6345   6350   6351   6351   6351 ...
1  63 1464  8309 19839  28228  31284  31874  31944  31949  31950  31950 ...
1 122 3960 30108 88508 144587 171283 178190 179204 179300 179306 179307 ...
For T(7,2)=9, the patterns are AAAAAAB, AAAAABB, AAAABAB, AAAABBB, AAABAAB, AAABABB, AABAABB, AABABAB, and AAABABB; only the last is chiral, paired with AAABBAB.

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
B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

Partial row sums of A152176.
Columns 1-6 are A057427, A000011, A056353, A056354, A056355, A056356
For increasing k, columns converge to A084708.
Cf. A320747 (oriented), 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]]
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) - A320742(n,k) = A320742(n,k) + A305749(n,k).

A056358 Number of bracelet structures using exactly three different colored beads.

Original entry on oeis.org

0, 0, 1, 2, 5, 14, 31, 82, 202, 538, 1401, 3838, 10395, 28890, 80207, 225368, 634265, 1796648, 5100325, 14535298, 41513434, 118880650, 341094843, 980665898, 2824223495, 8146908210, 23535345372, 68084937912, 197211483155, 571915789978, 1660402195255, 4825554617686

Offset: 1

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 = 1..200

Column 3 of A152176.

Cf. A000011, A056296, A056353, A214307.

a(n) = A056353(n) - A000011(n).

Terms a(28) and beyond from Andrew Howroyd, Oct 24 2019

A056359 Number of bracelet structures using exactly four different colored beads.

Original entry on oeis.org

0, 0, 0, 1, 2, 11, 33, 137, 478, 1851, 6845, 26148, 98406, 374010, 1416251, 5380907, 20440250, 77795428, 296384565, 1131011633, 4321964768, 16541275068, 63400061153, 243358803904, 935431121462, 3600520831215, 13876485252323, 53546253055179, 206864927506166, 800068244639812

Offset: 1

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 = 1..200

Column 4 of A152176.

Cf. A056297, A056353, A056354, A214309.

a(n) = A056354(n) - A056353(n).

Terms a(27) and beyond from Andrew Howroyd, Oct 24 2019

A056362 Number of primitive (period n) bracelet structures using a maximum of three different colored beads.

Original entry on oeis.org

1, 1, 1, 2, 4, 8, 18, 39, 94, 222, 572, 1463, 3934, 10584, 29211, 80808, 226430, 636320, 1800318, 5107479, 14548360, 41538874, 118927919, 341187047, 980838750, 2824561080, 8147547156, 23536592010, 68087313892, 197216119544, 571924673368, 1660419530055, 4825587979390

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

Cf. A002075, A056353, A056367, A276543.

a(n) = Sum_{d|n} mu(d)*A056353(n/d) for n > 0.

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

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

A114438 Number of Barlow packings that repeat after n (or a divisor of n) layers.

Original entry on oeis.org

0, 1, 1, 2, 1, 4, 3, 8, 8, 18, 21, 48, 63, 133, 205, 412, 685, 1354, 2385, 4644, 8496, 16431, 30735, 59344, 112531, 217246, 415628, 803210, 1545463, 2991192, 5778267, 11201884, 21702708, 42141576, 81830748, 159140896, 309590883, 602938099, 1174779397, 2290920128

Offset: 1

N. J. A. Sloane, Feb 28 2006; more terms, Aug 10 2006

nonn

See A011768 for the number of Barlow packings that repeat after exactly n layers.

Like A056353 but with additional restriction that adjacent beads must have different colors.

N. J. A. Sloane, Table of n, a(n) for n = 1..500
Dennis S. Bernstein, Omran Kouba, Counting Colorful Necklaces and Bracelets in Three Colors, arXiv:1901.10703 [math.CO], 2019.
J. H. Conway and N. J. A. Sloane, What are all the best sphere packings in low dimensions?, Discr. Comp. Geom., 13 (1995), 383-403.
E. Estevez-Rams, C. Azanza-Ricardo, J. Martínez García and B. Aragón-Fernández, On the algebra of binary codes representing closed-packed staking sequences, Acta Cryst. A61 (2005), 201-208.
T. J. McLarnan, The numbers of polytypes in close packings and related structures, Zeits. Krist. 155, 269-291 (1981). [See P'(N) on page 272.]
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. A027671, A056353.

with(numtheory); read transforms; M:=500;
A:=proc(N,d) if d mod 3 = 0 then 2^(N/d) else (1/3)*(2^(N/d)+2*cos(Pi*N/d)); fi; end;
E:=proc(N) if N mod 2 = 0 then N*2^(N/2) + add( did(N/2,d)*phi(2*d)*2^(N/(2*d)),d=1..N/2) else (N/3)*(2^((N+1)/2)+2*cos(Pi*(N+1)/2)); fi; end;
PP:=proc(N) (1/(4*N))*(add(did(N,d)*phi(d)*A(N,d), d=1..N)+E(N)); end; for N from 1 to M do lprint(N,PP(N)); od: # N. J. A. Sloane, Aug 10 2006

M = 40;
did[m_, n_] := If[Mod[m, n] == 0, 1, 0];
A[n_, d_] := If[Mod[d, 3] == 0, 2^(n/d), (1/3)(2^(n/d) + 2 Cos[Pi n/d])];
EE[n_] := If[Mod[n, 2] == 0, n 2^(n/2) + Sum[did[n/2, d] EulerPhi[2d] 2^(n/(2d)), {d, 1, n/2}], (n/3)(2^((n+1)/2) + 2 Cos[Pi(n+1)/2])];
a[n_] := (1/(4n))(Sum[did[n, d] EulerPhi[d] A[n, d], {d, 1, n}] + EE[n]);
Array[a, M] (* Jean-François Alcover, Apr 20 2020, from Maple *)

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

A027671 Number of necklaces with n beads of 3 colors, allowing turning over.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A056358 Number of bracelet structures using exactly three different colored beads.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

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