A011948 -id:A011948 - cp's OEIS frontend

A309784 T(n,k) is the number of non-equivalent distinguishing coloring partitions of the cycle on n vertices with exactly k parts. Regular triangle read by rows, n >= 1, 1 <= k <= n.

0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 4, 2, 1, 0, 1, 8, 10, 3, 1, 0, 1, 25, 32, 16, 3, 1, 0, 4, 62, 129, 84, 27, 4, 1, 0, 7, 176, 468, 433, 171, 37, 4, 1, 0, 18, 470, 1806, 2260, 1248, 338, 54, 5, 1, 0, 31, 1311, 6780, 11515, 8388, 3056, 590, 70, 5, 1, 0, 70, 3620, 25917, 58312, 56065, 26695, 6907, 1014, 96, 6, 1

Offset: 1

Mohammad Hadi Shekarriz, Aug 17 2019

The cycle graph is defined for n>=3; extended to n=1,2 using the closed form.
A vertex-coloring of a graph G is called distinguishing if it is only preserved by the identity automorphism of G. This notion is considered in the subject of symmetry breaking of simple (finite or infinite) graphs. A distinguishing coloring partition of a graph G is a partition of the vertices of G such that it induces a distinguishing coloring for G. We say two distinguishing coloring partitions P1 and P2 of G are equivalent if there is a nontrivial automorphism of G which maps P1 onto P2. Given a graph G, we use the notation psi_k(G) to denote the number of non-equivalent distinguishing coloring partitions of G with exactly k parts. For n>=3, this sequence gives T(n,k) = psi_k(C_n), i.e., the number of non-equivalent distinguishing coloring partitions of the cycle C_n on n vertices with exactly k parts.
T(n,k) is the number of primitive (period n) n-bead bracelet structures which are not periodic palindromes using exactly k different colored beads. - Andrew Howroyd, Sep 20 2019

			The triangle begins:
  0;
  0,  0;
  0,  0,   1;
  0,  0,   1,    1;
  0,  0,   4,    2,    1;
  0,  1,   8,   10,    3,    1;
  0,  1,  25,   32,   16,    3,   1;
  0,  4,  62,  129,   84,   27,   4,  1;
  0,  7, 176,  468,  433,  171,  37,  4, 1;
  0, 18, 470, 1806, 2260, 1248, 338, 54, 5, 1;
  ...
For n=6, we can partition the vertices of C_6 into exactly 3 parts in 8 ways such that all these partitions induce distinguishing colorings for C_6 and that all the 8 partitions are non-equivalent. The partitions are as follows:
    { { 1 }, { 2 }, { 3, 4, 5, 6 } }
    { { 1 }, { 2, 3 }, { 4, 5, 6 } }
    { { 1 }, { 2, 3, 4, 6 }, { 5 } }
    { { 1 }, { 2, 3, 5 }, { 4, 6 } }
    { { 1 }, { 2, 3, 6 }, { 4, 5 } }
    { { 1 }, { 2, 4, 5 }, { 3, 6 } }
    { { 1, 2 }, { 3, 4 }, { 5, 6 } }
    { { 1, 2 }, { 3, 5 }, { 4, 6 } }
For n=6, the above 8 partitions can be written as the following 3 colored bracelet structures: ABCCCC, ABBCCC, ABBBCB, ABBCBC, ABBCCB, ABCBBC, AABBCC, AABCBC. - _Andrew Howroyd_, Sep 22 2019

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.
Mohammad Hadi Shekarriz, GAP Program

Column k=2 appears to be A011948.
Columns k=3..4 are A328038, A328039.
Row sums are A328035.
Cf. A107424, A152175, A152176, A276543, A276544, A285012, A285037, A309748, A309785.

\\ 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(A=Ach(n), M=R(n), S=matrix(n, n, n, k, stirling(n, k, 2))); Mat(vectorv(n, n, sumdiv(n, d, moebius(d)*(M[n/d,] + A[n/d,])/2 - moebius(d)*(S[(n/d+1)\2, ] + S[n/d\2+1, ] + if((n-d)%2, A[(n/d+1)\2, ] + A[n/d\2+1, ]))/if(d%2, 2, 1) )))}
{ my(A=T(12)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Oct 02 2019

T(n,k) = A276543(n,k) - A285037(n,k). - Andrew Howroyd, Sep 20 2019

T(10,6) corrected by Mohammad Hadi Shekarriz, Sep 28 2019

a(56)-a(78) from Andrew Howroyd, Sep 28 2019

A045668 Number of 2n-bead balanced binary strings of fundamental period 2n, rotationally equivalent to complement, inequivalent to reverse and reversed complement.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 24, 28, 128, 252, 720, 1364, 3360, 6552, 14616, 29040, 61440, 122400, 253008, 504868, 1028160, 2054388, 4149288, 8294444, 16679040, 33349800, 66895920, 133775712, 267976800, 535920696, 1072758840, 2145452092

Offset: 0

David W. Wilson

nonn

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

Cf. A011948, A045663, A045665, A045686.

It seems that a(n) = 4*n*A011948(n). - Ralf Stephan, Aug 30 2003
From Andrew Howroyd, Sep 14 2019: (Start)
a(n) = 2*n*A045686(n).
a(n) = A045663(n) - A045665(n). (End)

A011768 Number of Barlow packings that repeat after exactly n layers.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 3, 6, 7, 16, 21, 43, 63, 129, 203, 404, 685, 1343, 2385, 4625, 8492, 16409, 30735, 59290, 112530, 217182, 415620, 803076, 1545463, 2990968, 5778267, 11201472, 21702686, 42140890, 81830744, 159139498, 309590883, 602935713, 1174779333, 2290915478, 4469734225, 8726815264

Offset: 1

N. J. A. Sloane and Michael OKeeffe (MOKeeffe(AT)asu.edu)

N. J. A. Sloane, Table of n, a(n) for n = 1..200
Dennis S. Bernstein and Omran Kouba, Counting Colorful Necklaces and Bracelets in Three Colors, arXiv:1901.10703 [math.CO], 2019.
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.
Ernesto Estevez-Rams, Cristy Azanza Ricardo and Beatriz Aragón Fernández, An alternative expression for counting the number of close-packaged polytypes, Z. Krist. 220 (2005) 592-595, Table 1
T. J. McLarnan, The numbers of polytypes in close-packings and related structures, Zeits. Krist. 155, 269-291 (1981).

Cf. A114438, A371991, A371992.

Cf. A011946, A011947, A011948, A011949, A011950, A011951, A011952, A011953, A011954, A011955, A011956.

with(numtheory); read transforms; M:=200;
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 t1[N]:=PP(N); od:
P:=proc(N) local s,d; s:=0; for d from 1 to N do if N mod d = 0 then s:=s+mobius(N/d)*t1[d]; fi; od: s; end; for N from 1 to M do lprint(N,P(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/(2 d)), {d, 1, n/2}], (n/3)(2^((n+1)/2) + 2 Cos[Pi(n+1)/2])];
PP[n_] := PP[n] = (1/(4n))(Sum[did[n, d] EulerPhi[d] A[n, d], {d, 1, n}] + EE[n]);
P[n_] := Module[{s = 0, d}, For[d = 1, d <= n, d++, If[Mod[n, d] == 0, s += MoebiusMu[n/d] PP[d]]]; s];
Array[P, M] (* Jean-François Alcover, Apr 21 2020, from Maple *)

apply( {A011768(n)=A371991(n)+if(n%3, 0, n>3, A371992(n/3), 1)}, [1..42]) \\ M. F. Hasler, May 27 2025

a(n) = (A011946(n/4) + A011947((n-2)/4) + A011948(n/2) + A011949(n/2) + A011950((n+1)/2) + A011951(n/2) + A011952(n/2) + A011953(n)) + (A011954((n-3)/6) + A011955(n/6-1) + A011955(n/6) + A011956(n/3)), where the terms with non-integer indices are set to 0. For n > 3, the two parenthesized terms are resp. A371991(n) and A371992(n/3). - Andrey Zabolotskiy, Feb 14 2024 and May 27 2025

More terms from N. J. A. Sloane, Aug 10 2006

cp's OEIS Frontend

A309784 T(n,k) is the number of non-equivalent distinguishing coloring partitions of the cycle on n vertices with exactly k parts. Regular triangle read by rows, n >= 1, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A045668 Number of 2n-bead balanced binary strings of fundamental period 2n, rotationally equivalent to complement, inequivalent to reverse and reversed complement.

Views

Author

Keywords

Links

Crossrefs

Formula

A011768 Number of Barlow packings that repeat after exactly n layers.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions