A309784 -id:A309784 - cp's OEIS frontend

A309748 The number of non-equivalent distinguishing coloring partitions of the path on n vertices (n>=1) with exactly k parts (k>=1). Regular triangle read by rows: the rows are indexed by n, the number of vertices of the path, and the columns are indexed by k, the number of parts.

1, 0, 1, 0, 1, 1, 0, 4, 4, 1, 0, 6, 14, 6, 1, 0, 16, 49, 37, 9, 1, 0, 28, 154, 182, 76, 12, 1, 0, 64, 496, 876, 542, 142, 16, 1, 0, 120, 1520, 3920, 3522, 1346, 242, 20, 1, 0, 256, 4705, 17175, 21392, 11511, 2980, 390, 25, 1, 0, 496, 14266, 73030, 123665, 89973, 32141, 5990, 595, 30, 1

Offset: 1

Mohammad Hadi Shekarriz, Aug 15 2019

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 at exactly k parts. For n>=1, this sequence gives T(n,k) = psi_k(P_n), i.e., the number of non-equivalent distinguishing coloring partitions of the path P_n on n vertices with exactly k parts.

Also, for n > 1 the number of reversible string structures of length n using exactly k different symbols that are not equivalent to their reversal (compare A284949). - Andrew Howroyd, Aug 15 2019

			The triangle begins:
  1;
  0,   1;
  0,   1,    1;
  0,   4,    4,     1;
  0,   6,   14,     6,     1;
  0,  16,   49,    37,     9,     1;
  0,  28,  154,   182,    76,    12,    1;
  0,  64,  496,   876,   542,   142,   16,   1;
  0, 120, 1520,  3920,  3522,  1346,  242,  20,  1;
  0, 256, 4705, 17175, 21392, 11511, 2980, 390, 25, 1;
  ...
----
For n=4, we can partition the vertices of P_4 into exactly 3 parts in 4 ways such that all these partitions induce distinguishing colorings for P_4 and that all the 4 partitions are non-equivalent. The partitions are as follows:
    { { 1 }, { 2 }, { 3, 4 } }
    { { 1 }, { 2, 3 }, { 4 } }
    { { 1 }, { 2, 4 }, { 3 } }
    { { 1, 4 }, { 2 }, { 3 } }

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

Columns k=2..4 are A007179, A327610, A327611.
Row sums are A327612(n > 1).
Cf. A284949, A304972, A309635, A309784.

\\ Ach is A304972 as square matrix.
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}
T(n)={(matrix(n, n, i, k, stirling(i, k, 2) - 2*stirling((i+1)\2, k, 2)) + Ach(n))/2}
{ my(A=T(10)); A[1,1]=1; for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Sep 18 2019

T(n,k) = A309635(n,k) - A309635(n,k-1) for k > 1.

T(n,k) = A284949(n,k) - Stirling2(ceiling(n/2), k) for n > 1. - Andrew Howroyd, Aug 15 2019

Terms a(56) and beyond from Andrew Howroyd, Sep 18 2019

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

A309785 The number of non-equivalent distinguishing coloring partitions of the cycle on n vertices with at most k parts (k>=1). The cycle graph is defined for n>=3; extended to n=1,2 using the closed form. Square array read by descending antidiagonals: the rows are indexed by n, the number of vertices of the cycle, and the columns are indexed by k, the number of parts.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 2, 4, 1, 0, 0, 0, 1, 2, 6, 9, 1, 0, 0, 0, 1, 2, 7, 19, 26, 4, 0, 0, 0, 1, 2, 7, 22, 58, 66, 7, 0, 0, 0, 1, 2, 7, 23, 74, 195, 183, 18, 0, 0, 0, 1, 2, 7, 23, 77, 279, 651, 488, 31, 0

Offset: 1

Bahman Ahmadi, Aug 17 2019

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 at most k parts. 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 at most k parts.

Note that, for any graph G, Psi_k(G) = Sum_{i<=k} psi_i(G), where psi_i(G) is the number of non-equivalent distinguishing coloring partitions of G with exactly i parts. For instance, here we have T(n,k) = Sum_{i<=k} A309784(n,i).

			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,   1,    1,    1,    1,    1,    1,    1,    1 ...
   4 | 0,  0,   1,    2,    2,    2,    2,    2,    2,    2 ...
   5 | 0,  0,   4,    6,    7,    7,    7,    7,    7,    7 ...
   6 | 0,  1,   9,   19,   22,   23,   23,   23,   23,   23 ...
   7 | 0,  1,  26,   58,   74,   77,   78,   78,   78,   78 ...
   8 | 0,  4,  66,  195,  279,  306,  310,  311,  311,  311 ...
   9 | 0,  7, 183,  651, 1084, 1255, 1292, 1296, 1297, 1297 ...
  10 | 0, 18, 488, 2294, 4554, 5802, 6140, 6194, 6199, 6200 ...
...
-------
For n=6, we can partition the vertices of C_6 into at most 4 parts in 10 ways such that all these partitions induce distinguishing colorings for C_6 and that all the 10 partitions are non-equivalent.
    { { 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, 3 }, { 4 }, { 5, 6 } }
    { { 1 }, { 2, 3 }, { 4, 6 }, { 5 } }
    { { 1 }, { 2, 4 }, { 3, 6 }, { 5 } }
    { { 1 }, { 2, 4, 6 }, { 3 }, { 5 } }
    { { 1 }, { 2, 5 }, { 3, 6 }, { 4 } }

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

Cf. A309635, A309784.

T(n,k) = Sum_{i=1..k} A309784(n,i).

A328035 Number of length n primitive (period n) bracelet structures which are not periodic palindromes using an infinite alphabet.

Original entry on oeis.org

0, 0, 1, 2, 7, 23, 78, 311, 1297, 6200, 31747, 178703, 1070388, 6842898, 46158435, 327718768, 2437732593, 18948528721, 153498234770, 1293122838953, 11306474635818, 102425551817363, 959826751122645, 9290811889272509, 92771812680385087, 954447072777977556

Offset: 1

Andrew Howroyd, Oct 02 2019

nonn

Equivalently, the number of length n bracelet structures that do not have any symmetry under the action of the dihedral group. The corresponding sequence for necklace structures that do not have any symmetry under the action of the cyclic group is A060223.

			For n = 5, the 7 bracelet structures have the patterns AAABC, AABAC, AABBC, ABABC, AABCD, ABACD, ABCDE.

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

Row sums of A309784.

Cf. A060223, A276548, A285042.

\\ Requires T from A309784.
seq(n)={my(A=T(n)); vector(n, i, vecsum(A[i, ]))}

a(n) = A276548(n) - A285042(n).

A328038 Number of primitive (period n) n-bead bracelet structures which are not periodic palindromes using exactly three different colored beads.

Original entry on oeis.org

0, 0, 1, 1, 4, 8, 25, 62, 176, 470, 1311, 3620, 10094, 28209, 79236, 223270, 631240, 1790213, 5090995, 14515788, 41484907, 118821599, 341008317, 980487770, 2823961866, 8146372122, 23534556225, 68083326558, 197209108054, 571910949743, 1660395053569, 4825540091342

Offset: 1

Andrew Howroyd, Oct 02 2019

nonn

Permuting the colors of the beads will not change the structure.

			For n = 3, the 1 bracelet structure has the pattern: ABC.
For n = 4, the 1 bracelet structure has the pattern: AABC.
For n = 5, the 4 bracelet structures have the patterns: AAABC, AABAC, AABBC, ABABC. The pattern ABBAC is excluded because it is a periodic palindrome.
For n = 6, the 8 bracelet structures have the patterns: ABCCCC, ABBCCC, ABBBCB, ABBCBC, ABBCCB, ABCBBC, AABBCC, AABCBC.

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

Column 3 of A309784.

Cf. A056367, A056519, A328035, A328039, A328657.

a(n) = A056367(n) - A056519(n).

A328039 Number of primitive (period n) n-bead bracelet structures which are not periodic palindromes using exactly four different colored beads.

Original entry on oeis.org

0, 0, 0, 1, 2, 10, 32, 129, 468, 1806, 6780, 25917, 98056, 372919, 1414548, 5375974, 20432480, 77773845, 296350460, 1130919576, 4321818986, 16540888897, 63399449652, 243357204415, 935428588930, 3600514267686, 13876474860110, 53546226302319, 206864885150216

Offset: 1

Andrew Howroyd, Oct 02 2019

nonn

Permuting the colors of the beads will not change the structure.

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

Column 4 of A309784.

Cf. A056368, A056521, A328035, A328038, A328658.

a(n) = A056368(n) - A056521(n).

A011948 Number of Barlow packings with group P63mc that repeat after 2n layers.

Original entry on oeis.org

1, 1, 4, 7, 18, 31, 70, 126, 261, 484, 960, 1800, 3514, 6643, 12852, 24457, 47151, 90157, 173740, 333498, 643230, 1238664, 2392650, 4620006, 8939657, 17302033, 33538048, 65042495, 126289800, 245361171, 477153040, 928510506, 1808276211, 3523813566, 6871685532, 13408154100, 26178323928, 51139027135

Offset: 6

N. J. A. Sloane

nonn

D. Bundala, M. Codish, L. Cruz-Filipe et al., Optimal-Depth Sorting Networks, arXiv preprint arXiv:1412.5302 [cs.DS], 2014. (See Table 4)
J. E. Iglesias, Enumeration of closest-packings by the space group: a simple approach, Z. Krist. 221 (2006) 237-245, Table 3.
T. J. McLarnan, The numbers of polytypes in close-packings and related structures, Zeits. Krist. 155, 269-291 (1981).

Appears to be column k=2 of A309784.

Cf. A045668.

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

A328657 Number of primitive (period n) n-bead bracelet structures which are not periodic palindromes using a maximum of three different colored beads.

Original entry on oeis.org

0, 0, 1, 1, 4, 9, 26, 66, 183, 488, 1342, 3690, 10220, 28470, 79720, 224230, 633040, 1793727, 5097638, 14528640, 41509364, 118868750, 341098474, 980661510, 2824295364, 8147015352, 23535794889, 68085719208, 197213728060, 571919889400, 1660412355602, 4825573629390

Offset: 1

Andrew Howroyd, Oct 24 2019

nonn

Permuting the colors of the beads will not change the structure.

			For n <= 5, the structures are the same as in A328038.
For n = 6, the 9 bracelet structures have the patterns: AABABB, ABCCCC, ABBCCC, ABBBCB, ABBCBC, ABBCCB, ABCBBC, AABBCC, AABCBC.

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

Cf. A056362, A056514, A309784, A328038.

a(n) = Sum_{k=1..3} A309784(n, k).

a(n) = A056362(n) - A056514(n).

A328658 Number of primitive (period n) n-bead bracelet structures which are not periodic palindromes using a maximum of four different colored beads.

Original entry on oeis.org

0, 0, 1, 2, 6, 19, 58, 195, 651, 2294, 8122, 29607, 108276, 401389, 1494268, 5600204, 21065520, 79567572, 301448098, 1145448216, 4363328350, 16659757647, 63740548126, 244337865925, 938252884294, 3608661283038, 13900010654999, 53614312021527, 207062098878276

Offset: 1

Andrew Howroyd, Oct 24 2019

nonn

Permuting the colors of the beads will not change the structure.

			For n = 4, the 2 bracelet structures are: AABC, ABCD.
For n = 5, the 6 bracelet structures are: AAABC, AABAC, AABBC, ABABC, AABCD, ABACD.

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

Cf. A056363, A056515, A309784, A328039.

a(n) = Sum_{k=1..4} A309784(n, k).

a(n) = A056363(n) - A056515(n).

cp's OEIS Frontend

A309748 The number of non-equivalent distinguishing coloring partitions of the path on n vertices (n>=1) with exactly k parts (k>=1). Regular triangle read by rows: the rows are indexed by n, the number of vertices of the path, and the columns are indexed by k, the number of parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A328035 Number of length n primitive (period n) bracelet structures which are not periodic palindromes using an infinite alphabet.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A328038 Number of primitive (period n) n-bead bracelet structures which are not periodic palindromes using exactly three different colored beads.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A328039 Number of primitive (period n) n-bead bracelet structures which are not periodic palindromes using exactly four different colored beads.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A011948 Number of Barlow packings with group P63mc that repeat after 2n layers.

Views

Author

Keywords

Links

Crossrefs

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

A328657 Number of primitive (period n) n-bead bracelet structures which are not periodic palindromes using a maximum of three different colored beads.

Views

Author

Keywords

Comments

Examples