A276544 -id:A276544 - cp's OEIS frontend

A276543 Triangle read by rows: T(n,k) = number of primitive (period n) n-bead bracelet structures using exactly k different colored beads.

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 3, 5, 2, 1, 0, 5, 13, 11, 3, 1, 0, 8, 31, 33, 16, 3, 1, 0, 14, 80, 136, 85, 27, 4, 1, 0, 21, 201, 478, 434, 171, 37, 4, 1, 0, 39, 533, 1849, 2270, 1249, 338, 54, 5, 1, 0, 62, 1401, 6845, 11530, 8389, 3056, 590, 70, 5, 1

Offset: 1

Andrew Howroyd, Apr 09 2017

Turning over will not create a new bracelet. Permuting the colors of the beads will not change the structure.

			Triangle starts:
  1
  0  1
  0  1   1
  0  2   2    1
  0  3   5    2    1
  0  5  13   11    3    1
  0  8  31   33   16    3   1
  0 14  80  136   85   27   4  1
  0 21 201  478  434  171  37  4 1
  0 39 533 1849 2270 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

Columns 1-6 are A063524, A056366, A056367, A056368, A056369, A056370.
Partial row sums include A000046, A056362, A056363, A056364, A056365.
Row sums are A276548.
Cf. A276550, A152175, A152176, A107424, A137651, A276544, A304972.

\\ 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); Mat(vectorv(n,n,sumdiv(n, d, moebius(d)*M[n/d,])))}
{ my(A=T(12)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Sep 20 2019

T(n, k) = Sum_{d|n} mu(n/d) * A152176(d, k).

A107424 Triangle read by rows: T(n, k) is the number of primitive (period n) n-bead necklace structures with k different colors. Only includes structures that contain all k colors.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 3, 5, 2, 1, 0, 5, 17, 13, 3, 1, 0, 9, 43, 50, 20, 3, 1, 0, 16, 124, 220, 136, 36, 4, 1, 0, 28, 338, 866, 773, 296, 52, 4, 1, 0, 51, 941, 3435, 4280, 2303, 596, 78, 5, 1, 0, 93, 2591, 13250, 22430, 16317, 5817, 1080, 105, 5, 1, 0, 170, 7234, 51061

Offset: 1

David Wasserman, May 26 2005

This classification is concerned with which beads are the same color, not with the colors themselves, so bbabcd is the same structure as aabacd. Cyclic permutations are also the same structure, e.g. abacda is also the same structure. However, order matters: the reverse of aabacd is equivalent to aabcad, which is also on the list.

			T(6, 4) = 13: {aaabcd, aabacd, aabcad, abacad, aabbcd, aabcbd, aabcdb, aacbbd, aacbdb, ababcd, abacbd, acabdb, abcabd}.
From _Andrew Howroyd_, Apr 09 2017 (Start)
Triangle starts:
1
0  1
0  1   1
0  2   2    1
0  3   5    2    1
0  5  17   13    3    1
0  9  43   50   20    3   1
0 16 124  220  136   36   4  1
0 28 338  866  773  296  52  4 1
0 51 941 3435 4280 2303 596 78 5 1
(End)

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

Columns 2-6 are A056303, A056304, A056305, A056306, A056307.
Partial row sums include A000048, A002075, A056300, A056301, A056302.
Row sums are A276547.
Cf. A074650, A152175, A276543, A137651, A276544.

A[d_, n_] := A[d, n] = Which[n == 0, 1, n == 1, DivisorSum[d, x^# &], d == 1, Sum[StirlingS2[n, k] x^k, {k, 0, n}], True, Expand[A[d, 1] A[d, n-1] + D[A[d, n-1], x] x]];
B[n_, k_] := Coefficient[DivisorSum[n, EulerPhi[#] A[#, n/#]&]/n/x, x, k];
T[n_, k_] := DivisorSum[n, MoebiusMu[n/#] B[#, k]&];
Table[T[n, k], {n, 1, 12}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, Jun 06 2018, after Andrew Howroyd and Robert A. Russell *)

\\ here R(n) is A152175 as square matrix.
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)); matrix(n, n, i, k, sumdiv(i, d, moebius(i/d)*M[d,k]))}
{ my(A=T(10)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Jan 09 2020

T(n, k) = Sum_{d|n} mu(n/d) * A152175(d, k). - Andrew Howroyd, Apr 09 2017

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.

Original entry on oeis.org

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

A276549 Number of primitive (aperiodic) reversible string structures with n beads using an infinite alphabet.

Original entry on oeis.org

1, 1, 3, 9, 31, 112, 467, 2141, 10739, 58454, 340389, 2110093, 13830234, 95475087, 691543059, 5240282987, 41432986587, 341040306207, 2916376237349, 25862097428262, 237434959190586, 2253358056942644, 22076003468637449, 222979436688500085, 2319295172178428701

Offset: 1

Andrew Howroyd, Apr 09 2017

nonn

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

Row sums of A276544.

Cf. A103293.

b[n_] := SeriesCoefficient[Exp[(Exp[2*x] - 3)/2 + Exp[x]], {x, 0, n}]*n!;
c[n_] := If[n == 0, 1, (BellB[n - 1] + If[Mod[n, 2] == 1, b[(n - 1)/2], Sum[Binomial[n/2 - 1, k]*b[k], {k, 0, n/2 - 1}]])/2];
a[n_] := DivisorSum[n, MoebiusMu[n/#] c[# + 1]&];
Array[a, 25] (* Jean-François Alcover, Jun 16 2017, using Alois P. Heinz's code for A103293 *)

a(n) = Sum_{d|n} mu(n/d) * A103293(d+1).

A056336 Number of primitive (aperiodic) reversible string structures with n beads using exactly two different colors.

Original entry on oeis.org

0, 1, 2, 4, 9, 16, 35, 66, 133, 261, 527, 1032, 2079, 4123, 8244, 16440, 32895, 65639, 131327, 262380, 524762, 1049071, 2098175, 4195230, 8390646, 16779231, 33558392, 67112892, 134225919, 268443306

Offset: 1

Marks R. Nester

nonn

A string and its reverse are considered to be equivalent. Permuting the colors will not change the structure. Identical to A056331 for n>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]

Column 2 of A276544.

Cf. A056318, A056331, A063524.

a[1] = 0;
a[n_] := DivisorSum[n, MoebiusMu[#] (2^(n/#-2) + 2^(Floor[n/#/2]-1))&];
Array[a, 30] (* Jean-François Alcover, Jun 29 2018 *)

a(n) = A056331(n) - A063524(n).

A056337 Number of primitive (aperiodic) reversible string structures with n beads using exactly three different colors.

Original entry on oeis.org

0, 0, 1, 4, 15, 49, 160, 498, 1544, 4715, 14356, 43420, 131145, 394990, 1188564, 3572400, 10732065, 32224216, 96733636, 290317660, 871200664, 2614083394, 7843255300, 23531731530, 70599259170, 211805771345

Offset: 1

Marks R. Nester

nonn

A string and its reverse are considered to be equivalent. Permuting the colors 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]

Column 3 of A276544.

Cf. A056319.

A056332(n)-A056331(n).

A056338 Number of primitive (aperiodic) reversible string structures with n beads using exactly four different colors.

Original entry on oeis.org

0, 0, 0, 1, 6, 37, 183, 876, 3930, 17179, 73095, 306323, 1267266, 5198374, 21182337, 85910040, 347187210, 1399447578, 5629911015, 22616239535, 90754854843, 363890053582, 1458172596903, 5840531328120, 23385650196084

Offset: 1

Marks R. Nester

nonn

A string and its reverse are considered to be equivalent. Permuting the colors 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]

Column 4 of A276544.

Cf. A056320.

A056333(n)-A056332(n).

A056339 Number of primitive (aperiodic) reversible string structures with n beads using exactly five different colors.

Original entry on oeis.org

0, 0, 0, 0, 1, 9, 76, 542, 3523, 21392, 123680, 690541, 3756151, 20042513, 105394295, 548123440, 2826435403, 14479201301, 73794961960, 374603863517, 1895632969275, 9568915248589, 48208452866816

Offset: 1

Marks R. Nester

nonn

A string and its reverse are considered to be equivalent. Permuting the colors 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]

Column 5 of A276544.

Cf. A056321.

A056334(n)-A056333(n).

A056340 Number of primitive (aperiodic) reversible string structures with n beads using exactly six different colors.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 12, 142, 1346, 11511, 89974, 662673, 4662574, 31724723, 210361046, 1367510184, 8752976610, 55343946628, 346541488998, 2153041576027, 13292844257186, 81652683460145, 499484958151630

Offset: 1

Marks R. Nester

nonn

A string and its reverse are considered to be equivalent. Permuting the colors 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]

Column 6 of A276544.

Cf. A056322.

A056335(n)-A056334(n).

cp's OEIS Frontend

A276543 Triangle read by rows: T(n,k) = number of primitive (period n) n-bead bracelet structures using exactly k different colored beads.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

A107424 Triangle read by rows: T(n, k) is the number of primitive (period n) n-bead necklace structures with k different colors. Only includes structures that contain all k colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

A276549 Number of primitive (aperiodic) reversible string structures with n beads using an infinite alphabet.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A056336 Number of primitive (aperiodic) reversible string structures with n beads using exactly two different colors.

Views

Author

Keywords

Comments

References

Crossrefs

Programs

Mathematica

Formula

A056337 Number of primitive (aperiodic) reversible string structures with n beads using exactly three different colors.

Views

Author

Keywords

Comments

References

Crossrefs

Formula

A056338 Number of primitive (aperiodic) reversible string structures with n beads using exactly four different colors.

Views

Author

Keywords

Comments

References

Crossrefs

Formula

A056339 Number of primitive (aperiodic) reversible string structures with n beads using exactly five different colors.

Views

Author

Keywords

Comments

References

Crossrefs

Formula