A320647 -id:A320647 - cp's OEIS frontend

A059053 Number of chiral pairs of necklaces with n beads and two colors (color complements being equivalent); i.e., turning the necklace over neither leaves it unchanged nor simply swaps the colors.

0, 0, 0, 0, 0, 0, 0, 1, 2, 7, 12, 31, 58, 126, 234, 484, 906, 1800, 3402, 6643, 12624, 24458, 46686, 90157, 172810, 333498, 641340, 1238671, 2388852, 4620006, 8932032, 17302033, 33522698, 65042526, 126258960, 245361172, 477091232

Offset: 0

Henry Bottomley, Dec 21 2000

nonn

Number of chiral pairs of set partitions of a cycle of n elements using exactly two different elements. - Robert A. Russell, Oct 02 2018

			For a(7) = 1, the chiral pair is AAABABB-AAABBAB.
For a(8) = 2, the chiral pairs are AAAABABB-AAAABBAB and AAABAABB-AAABBAAB.

Andrew Howroyd, Table of n, a(n) for n = 0..1000
Illustration of initial terms
Index entries for sequences related to necklaces

Column 2 of A320647 and A320742.

Cf. A056295 (oriented), A056357 (unoriented), A052551(n-2) (achiral).

Prepend[Table[DivisorSum[n, EulerPhi[#] StirlingS2[n/# + If[Divisible[#,2],1,0], 2] &] / (2n) - StirlingS2[1+Floor[n/2],2] / 2, {n, 1, 40}],0] (* Robert A. Russell, Oct 02 2018 *)

a(n) = {if(n<1, 0, (sumdiv(n, k, eulerphi(2*k) * 2^(n/k)) / (2*n) - 2^(n\2))/2)}; \\ Andrew Howroyd, Nov 03 2019

a(n) = A000013(n) - A000011(n) = A000011(n) - A016116(n) = (A000013(n) - A016116(n))/2.
From Robert A. Russell, Oct 02 2018: (Start)
a(n) = (A056295(n)-A052551(n-2)) / 2 = A056295(n) - A056357(n) = A056357(n) - A052551(n-2).
a(n) = -S2(1+floor(n/2),2) + (1/2n) * Sum_{d|n} phi(d) * S2(n/d+[2|d],2), where S2 is a Stirling subset number A008277.
G.f.: -x(1+2x)/(2-4x^2) - Sum_{d>0} phi(d) * log(1-2x^d) / (2d*(2-[2|d])).
(End)

Name clarified by Robert A. Russell, Oct 02 2018

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

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

Original entry on oeis.org

0, 0, 0, 0, 0, 4, 12, 44, 137, 408, 1190, 3416, 9730, 27560, 78148, 221250, 627960, 1784038, 5081154, 14496956, 41455409, 118764600, 340919744, 980315700, 2823696150, 8145853520, 23533759241, 68081765650, 197206716570, 571906256808, 1660387879116, 4825525985408, 14037945170525, 40875277302720, 119122416494961, 347440682773324, 1014151818975190, 2962391932326680, 8659301777595196, 25328461701728194

Offset: 1

Robert A. Russell, Oct 18 2018

Two color patterns are the same if the colors are permuted. A chiral cycle is different from its reverse.
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 A056296 and A304973, 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 A320647.

Cf. A056296 (oriented), A056358 (unoriented), A304973 (achiral).

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 *)
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; Table[DivisorSum[n,EulerPhi[#]Adnk[#,n/#,k]&]/(2n) - Ach[n,k]/2,{n,40}]

a(n) = (A056296(n) - A304973(n)) / 2 = A056296(n) - A056358(n) = A056358(n) - A304973(n).

a(n) = -Ach(n,k)/2 + (1/2n)*Sum_{d|n} phi(d)*A(d,n/d,k), where k=3 is number of colors or sets, 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)).

A320644 Number of chiral pairs of color patterns (set partitions) in a cycle of length n using exactly 4 colors (subsets).

Original entry on oeis.org

0, 0, 0, 0, 0, 2, 17, 84, 388, 1586, 6405, 24927, 96404, 368641, 1407515, 5357974, 20403120, 77699323, 296229485, 1130614092, 4321324766, 16539645539, 63397442097, 243352167691, 935420468092, 3600493932070, 13876442107403, 53546144395718, 206864753332164, 800067806813323, 3097590602034137, 12004772596768984, 46568647645538594, 180809553280920680

Offset: 1

Robert A. Russell, Oct 18 2018

Two color patterns are the same if the colors are permuted. A chiral cycle is different from its reverse.
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 A056297 and A304974, which can be used in conjunction with the first formula.

			For a(6)=2, the chiral pairs are AABACD-AABCAD and AABCBD-AABCDC.

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 4 of A320647.

Cf. A056297 (oriented), A056359 (unoriented), A304974 (achiral).

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 *)
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=4; Table[DivisorSum[n,EulerPhi[#]Adnk[#,n/#,k]&]/(2n) - Ach[n,k]/2,{n,40}]

a(n) = (A056297(n) - A304974(n)) / 2 = A056297(n) - A056359(n) = A056359(n) - A304974(n).

a(n) = -Ach(n,k)/2 + (1/2n)*Sum_{d|n} phi(d)*A(d,n/d,k), where k=4 is number of colors or sets, 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)).

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

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 2, 0, 0, 0, 1, 12, 17, 4, 0, 0, 0, 2, 43, 82, 49, 9, 0, 0, 0, 7, 137, 388, 339, 125, 15, 0, 0, 0, 12, 404, 1572, 1994, 1044, 254, 24, 0, 0, 0, 31, 1190, 6405, 10900, 7928, 2761, 490, 35, 0, 0, 0, 57, 3394, 24853, 56586, 54272, 25609, 6365, 850, 51, 0, 0

Offset: 1

Bahman Ahmadi, Sep 04 2019

The cycle graph is defined for n>=3; extended to n=1,2 using the closed form.
Two partitions P1 and P2 of a the vertex set of a graph G are said to be equivalent if there is a nontrivial automorphism of G which maps P1 onto P2. A distinguishing partition is a partition of the vertex set of G such that no nontrivial automorphism of G can preserve it. Here T(n,k)=xi_k(C_n), the number of non-equivalent distinguishing partitions of the cycle on n vertices, with exactly k parts.
Number of n-bead bracelet structures using exactly k different colored beads that are not self-equivalent under either a nonzero rotation or reversal (turning over bracelet). Comparable sequences for unoriented (reversible) strings and necklaces (cyclic group) are A320525 and A327693. - Andrew Howroyd, Sep 23 2019

			Triangle begins:
  0;
  0,  0;
  0,  0,   0;
  0,  0,   0,    0;
  0,  0,   0,    0,    0;
  0,  0,   4,    2,    0,    0;
  0,  1,  12,   17,    4,    0,   0;
  0,  2,  43,   82,   49,    9,   0,  0;
  0,  7, 137,  388,  339,  125,  15,  0, 0;
  0, 12, 404, 1572, 1994, 1044, 254, 24, 0, 0;
  ...
For n=7, we can partition the vertices of the cycle C_7 with exactly 3 parts, in 12 ways, such that all these partitions are distinguishing for C_7 and that all the 12 partitions are non-equivalent. The partitions are as follows:
    { { 1 }, { 2, 3 }, { 4, 5, 6, 7 } },
    { { 1 }, { 2, 3, 4, 6 }, { 5, 7 } },
    { { 1 }, { 2, 3, 4, 7 }, { 5, 6 } },
    { { 1 }, { 2, 3, 5, 6 }, { 4, 7 } },
    { { 1 }, { 2, 3, 5, 7 }, { 4, 6 } },
    { { 1 }, { 2, 3, 6 }, { 4, 5, 7 } },
    { { 1 }, { 2, 3, 7 }, { 4, 5, 6 } },
    { { 1 }, { 2, 4, 5, 6 }, { 3, 7 } },
    { { 1 }, { 2, 4, 7 }, { 3, 5, 6 } },
    { { 1, 2 }, { 3, 4, 6 }, { 5, 7 } },
    { { 1, 2 }, { 3, 5, 6 }, { 4, 7 } },
    { { 1, 2, 4 }, { 3, 6 }, { 5, 7 } }.
From _Andrew Howroyd_, Sep 23 2019: (Start)
For n=6, k=4 the partitions are:
    { { 1, 2, 4 }, { 3 }, { 5 }, { 6 } },
    { { 1, 2 }, { 3, 5 }, { 4 }, { 6 } }.
These correspond to the bracelet structures AABACD and AABCBD.
(End)

Bahman Ahmadi, GAP Program
B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.

Column k=2 is A327734.
Row sums are A327740.
Cf. A309784, A309785, A320525, A320748, A152176, A320647, A324803, A327693.

T(n,k) = A324803(n,k) - A324803(n,k-1).

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

A320645 Number of chiral pairs of color patterns (set partitions) in a cycle of length n using exactly 5 colors (subsets).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 4, 51, 339, 2010, 10900, 56700, 286888, 1426542, 7014746, 34229050, 166197824, 804243285, 3883608940, 18729354638, 90266471623, 434946282498, 2096010533584, 10104160993993, 48733654211358, 235195966291020, 1135892493220025, 5490005931157446, 26555178320890184, 128550000630553133, 622790399873432344, 3019641804537586657

Offset: 1

Robert A. Russell, Oct 18 2018

Two color patterns are the same if the colors are permuted. A chiral cycle is different from its reverse.
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 A056298 and A304975, which can be used in conjunction with the first formula.

			For a(7)=4, the chiral pairs are AABACDE-AABCDAE, AABCBDE-AABCDED, AABCDBE-AABCDEC, and ABACBDE-ABACDBE.

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 5 of A320647.

Cf. A056298 (oriented), A056360 (unoriented), A304975 (achiral).

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 *)
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=5; Table[DivisorSum[n,EulerPhi[#]Adnk[#,n/#,k]&]/(2n) - Ach[n,k]/2,{n,40}]

a(n) = (A056298(n) - A304975(n)) / 2 = A056298(n) - A056360(n) = A056360(n) - A304975(n).

a(n) = -Ach(n,k)/2 + (1/2n)*Sum_{d|n} phi(d)*A(d,n/d,k), where k=5 is number of colors or sets, 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)).

A320749 Number of chiral pairs of color patterns (set partitions) in a cycle of length n.

Original entry on oeis.org

0, 0, 0, 0, 0, 6, 34, 190, 1011, 5352, 29740, 172466, 1055232, 6793791, 46034940, 327303819, 2436650368, 18944771253, 153488081102, 1293086505784, 11306373089104, 102425178180769, 959825673145688, 9290807818971900, 92771800581171418, 954447025978145744, 10105871186441842623, 110009631951698573068, 1229996584263621368224, 14112483571723367245825, 166021918475962174194914, 2001010469483653602192695

Offset: 1

Robert A. Russell, Oct 22 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.

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

Row sums of A320647.
Columns of A320742 converge to this as k increases.
Cf. A084423 (oriented), A084708 (unoriented), A080107 (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]]
Table[Sum[(DivisorSum[n, EulerPhi[#] Adnk[#,n/#,j]&]/n - Ach[n,j])/2, {j,n}], {n,40}]

a(n) = Sum_{j=1..n} -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)).

a(n) = (A084423(n) - A080107(n)) / 2 = A084423(n) - A084708(n) = A084708(n) - A080107(n).

A320646 Number of chiral pairs of color patterns (set partitions) in a cycle of length n using exactly 6 colors (subsets).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 9, 125, 1054, 7928, 54383, 356594, 2259504, 14008733, 85422360, 514773336, 3074341497, 18238301412, 107649939612, 632987843336, 3711471738408, 21716706883190, 126879832615600, 740528154956264, 4319137675225128, 25181504728152534, 146788320134425736, 855660631677225738, 4988501691655508510, 29089896998939710698

Offset: 1

Robert A. Russell, Oct 19 2018

Two color patterns are the same if the colors are permuted. A chiral cycle is different from its reverse.
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 A056299 and A304976, which can be used in conjunction with the first formula.

			For a(8)=9, the chiral pairs are AABACDEF-AABCDEAF, AABCADEF-AABCDAEF, AABCBDEF-AABCDEFE, AABCDBEF-AABCDEFD, AABCDEBF-AABCDEFC, AABCDCEF-AABCDEDF, ABACDEBF-ABACDEBF, ABCADBEF-ABCADECF, and ABCDAEBF-ABCADBEF.

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 6 of A320647.

Cf. A056299 (oriented), A056361 (unoriented), A304976 (achiral).

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 *)
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=6; Table[DivisorSum[n,EulerPhi[#]Adnk[#,n/#,k]&]/(2n) - Ach[n,k]/2,{n,40}]

a(n) = (A056299(n) - A304976(n)) / 2 = A056299(n) - A056361(n) = A056361(n) - A304976(n).

a(n) = -Ach(n,k)/2 + (1/2n)*Sum_{d|n} phi(d)*A(d,n/d,k), where k=5 is number of colors or sets, 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)).

A324803 T(n,k) is the number of non-equivalent distinguishing partitions of the cycle on n vertices with at most k part. Square array read by descending antidiagonals, n >= 1, k >= 1.

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, 45, 7, 0, 0, 0, 0, 0, 0, 6, 34, 127, 144, 12, 0, 0, 0, 0, 0, 0, 6, 34, 176, 532, 416, 31, 0, 0, 0, 0, 0, 0, 6, 34, 185, 871, 1988, 1221, 57, 0, 0, 0, 0, 0, 0, 6, 34, 185, 996, 3982

Offset: 1

Bahman Ahmadi, Sep 04 2019

The cycle graph is defined for n >= 3; extended to n=1,2 using the closed form.

Two partitions P1 and P2 of a the vertex set of a graph G are said to be equivalent if there is a nontrivial automorphism of G which maps P1 onto P2. A distinguishing partition is a partition of the vertex set of G such that no nontrivial automorphism of G can preserve it. Here T(n,k)=Xi_k(C_n), the number of non-equivalent distinguishing partitions of the cycle on n vertices, with at most k parts.

			Table begins:
=================================================================
  n/k | 1   2    3     4     5     6     7     8     9    10
------+----------------------------------------------------------
    1 | 0,  0,   0,    0,    0,    0,    0,    0,    0,    0, ...
    2 | 0,  0,   0,    0,    0,    0,    0,    0,    0,    0, ...
    3 | 0,  0,   0,    0,    0,    0,    0,    0,    0,    0, ...
    4 | 0,  0,   0,    0,    0,    0,    0,    0,    0,    0, ...
    5 | 0,  0,   0,    0,    0,    0,    0,    0,    0,    0, ...
    6 | 0,  0,   4,    6,    6,    6,    6,    6,    6,    6, ...
    7 | 0,  1,  13,   30,   34,   34,   34,   34,   34,   34, ...
    8 | 0,  2,  45,  127,  176,  185,  185,  185,  185,  185, ...
    9 | 0,  7, 144,  532,  871,  996, 1011, 1011, 1011, 1011, ...
   10 | 0, 12, 416, 1988, 3982, 5026, 5280, 5304, 5304, 5304, ...
  ...
For n=7, we can partition the vertices of the cycle C_7 with at most 3 parts, in 13 ways, such that all these partitions are distinguishing for C_7 and that all the 13 partitions are non-equivalent. The partitions are as follows:
    { { 1 }, { 2, 3 }, { 4, 5, 6, 7 } },
    { { 1 }, { 2, 3, 4, 6 }, { 5, 7 } },
    { { 1 }, { 2, 3, 4, 7 }, { 5, 6 } },
    { { 1 }, { 2, 3, 5, 6 }, { 4, 7 } },
    { { 1 }, { 2, 3, 5, 7 }, { 4, 6 } },
    { { 1 }, { 2, 3, 6 }, { 4, 5, 7 } },
    { { 1 }, { 2, 3, 7 }, { 4, 5, 6 } },
    { { 1 }, { 2, 4, 5, 6 }, { 3, 7 } },
    { { 1 }, { 2, 4, 7 }, { 3, 5, 6 } },
    { { 1, 2 }, { 3, 4, 6 }, { 5, 7 } },
    { { 1, 2 }, { 3, 5, 6 }, { 4, 7 } },
    { { 1, 2, 4 }, { 3, 6 }, { 5, 7 } },
    { { 1, 2, 3, 5 }, { 4, 6, 7 } }.

Bahman Ahmadi, GAP Program
B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.

Column k=2 is A327734.

Cf. A309784, A309785, A320748, A152176, A320647, A324802.

T(n,k) = Sum_{i<=k} A324802(n,i).

cp's OEIS Frontend

A059053 Number of chiral pairs of necklaces with n beads and two colors (color complements being equivalent); i.e., turning the necklace over neither leaves it unchanged nor simply swaps the colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A320644 Number of chiral pairs of color patterns (set partitions) in a cycle of length n using exactly 4 colors (subsets).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A324802 T(n,k) is the number of non-equivalent distinguishing 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

Formula

Extensions

A320645 Number of chiral pairs of color patterns (set partitions) in a cycle of length n using exactly 5 colors (subsets).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A320749 Number of chiral pairs of color patterns (set partitions) in a cycle of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula