A324802 -id:A324802 - cp's OEIS frontend

A327693 Triangle read by rows: T(n,k) is the number of n-bead necklace structures which are not self-equivalent under a nonzero rotation using exactly k different colored beads.

1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 3, 5, 2, 0, 0, 4, 13, 9, 2, 0, 0, 9, 43, 50, 20, 3, 0, 0, 14, 116, 206, 127, 31, 3, 0, 0, 28, 335, 862, 772, 293, 51, 4, 0, 0, 48, 920, 3384, 4226, 2263, 580, 72, 4, 0, 0, 93, 2591, 13250, 22430, 16317, 5817, 1080, 105, 5, 0

Offset: 1

Andrew Howroyd, Sep 22 2019

Permuting the colors does not change the structure.

The definition requires that a necklace must not be equivalent to itself by permutation of colors and rotation (except for identity rotation). For example the length 2 necklace AB is excluded because a rotation of 1 gives BA and permutation of colors brings back to AB.

			Triangle begins:
  1;
  0,  0;
  0,  1,   0;
  0,  1,   1,    0;
  0,  3,   5,    2,    0;
  0,  4,  13,    9,    2,    0;
  0,  9,  43,   50,   20,    3,   0;
  0, 14, 116,  206,  127,   31,   3,  0;
  0, 28, 335,  862,  772,  293,  51,  4, 0;
  0, 48, 920, 3384, 4226, 2263, 580, 72, 4, 0;
  ...
T(6, 4) = 9: {aaabcd, aabacd, aabcad, aabbcd, aabcbd, aabcdb, aacbdb, ababcd, abacbd}. Compared with A107424 the patterns {abacad, aacbbd, abcabd, acabdb} are excluded.

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Columns k=2..4 are A051841, A328740, A328741.
Row sums are A327696.
Partial row sums include A328742, A328743.
Cf. A324802 (not self-equivalent under reversal and rotations).
Cf. A107424, A152175.

R(n) = {Mat(Col([Vecrev(p/y, n) | p<-Vec(intformal(sum(m=1, n, moebius(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])) }

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

A327734 Number of n-bead bracelet structures using exactly two different colored beads that are not self-equivalent under either a nonzero rotation or reversal (turning over bracelet).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 2, 7, 12, 31, 57, 126, 232, 484, 900, 1800, 3388, 6643, 12594, 24457, 46624, 90157, 172680, 333498, 641088, 1238664, 2388357, 4620006, 8931052

Offset: 1

Andrew Howroyd, Sep 23 2019

			Case n=7: There are 7 necklace structures using exactly two colors. See example in A056295. Of these, 5 are achiral and the other two a chiral pair: AAABABB/AAABBAB. a(7) = 1, since this sequence considers chiral pairs as the same bracelet structure.

Column k=2 of A324802.

Cf. A056295, A056357.

cp's OEIS Frontend

A327693 Triangle read by rows: T(n,k) is the number of n-bead necklace structures which are not self-equivalent under a nonzero rotation using exactly k different colored beads.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A327734 Number of n-bead bracelet structures using exactly two different colored beads that are not self-equivalent under either a nonzero rotation or reversal (turning over bracelet).

Views

Author

Keywords

Examples

Crossrefs

A327740 Number of n-bead bracelet structures using an infinite alphabet that are not self-equivalent under either a nonzero rotation or reversal (turning over bracelet).

Views

Author

Keywords

Crossrefs

Formula