A276543 -id:A276543 - cp's OEIS frontend

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.

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

A276544 Triangle read by rows: T(n,k) = number of primitive (aperiodic) reversible string structures with n beads using exactly k different colors.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 4, 4, 1, 0, 9, 15, 6, 1, 0, 16, 49, 37, 9, 1, 0, 35, 160, 183, 76, 12, 1, 0, 66, 498, 876, 542, 142, 16, 1, 0, 133, 1544, 3930, 3523, 1346, 242, 20, 1, 0, 261, 4715, 17179, 21392, 11511, 2980, 390, 25, 1

Offset: 1

Andrew Howroyd, Apr 09 2017

A string and its reverse are considered to be equivalent. Permuting the colors will not change the structure.

			Triangle starts
1
0   1
0   2    1
0   4    4     1
0   9   15     6     1
0  16   49    37     9     1
0  35  160   183    76    12    1
0  66  498   876   542   142   16   1
0 133 1544  3930  3523  1346  242  20  1
0 261 4715 17179 21392 11511 2980 390 25 1
...
Primitive reversible word structures are:
n=1: a => 1
n=2: ab => 1
n=3: aab, aba; abc => 2 + 1
n=4: aaab, aaba, aabb, abba => 4 (k=2)
     aabc, abac, abbc, abca => 4 (k=3)

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 (first 50 rows)

Columns 2-6 are A056336, A056337, A056338, A056339, A056340.
Partial row sums include A056331, A056332, A056333, A056334, A056335.
Row sums are A276549.
Cf. A284871, A284949, A277504, A137651, A107424, A276543.

Ach[n_, k_] := Ach[n, k] = Switch[k, 0, If[n == 0, 1, 0], 1, If[n > 0, 1, 0], _, If[OddQ[n], Sum[Binomial[(n - 1)/2, i] Ach[n - 1 - 2 i, k - 1], {i, 0, (n - 1)/2}], Sum[Binomial[n/2 - 1, i] (Ach[n - 2 - 2 i, k - 1] + 2^i Ach[n - 2 - 2 i, k - 2]), {i, 0, n/2 - 1}]]]
T[n_, k_] := DivisorSum[n, MoebiusMu[n/#] (StirlingS2[#, k] + Ach[#, k])/2& ];
Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 29 2018, after Robert A. Russell and Andrew Howroyd *)

\\ here Ach is A304972 as matrix.
Ach(n,m=n)={my(M=matrix(n, m, i, k, i>=k)); for(i=3, n, for(k=2, m, M[i, k]=k*M[i-2, k] + M[i-2, k-1] + if(k>2, M[i-2, k-2]))); M}
T(n,m=n)={my(M=matrix(n, m, i, k, stirling(i, k, 2)) + Ach(n,m)); matrix(n, m, i, k, sumdiv(i, d, moebius(i/d)*M[d,k]))/2}
{ 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) * A284949(d, k).

A276550 Array read by antidiagonals: T(n,k) = number of primitive (period n) bracelets using a maximum of k different colored beads.

Original entry on oeis.org

1, 2, 0, 3, 1, 0, 4, 3, 2, 0, 5, 6, 7, 3, 0, 6, 10, 16, 15, 6, 0, 7, 15, 30, 45, 36, 8, 0, 8, 21, 50, 105, 132, 79, 16, 0, 9, 28, 77, 210, 372, 404, 195, 24, 0, 10, 36, 112, 378, 882, 1460, 1296, 477, 42, 0, 11, 45, 156, 630, 1848, 4220, 5890, 4380, 1209, 69, 0

Offset: 1

Andrew Howroyd, Apr 09 2017

Turning over will not create a new bracelet.

			Table starts:
  1  2   3    4     5      6      7       8 ...
  0  1   3    6    10     15     21      28 ...
  0  2   7   16    30     50     77     112 ...
  0  3  15   45   105    210    378     630 ...
  0  6  36  132   372    882   1848    3528 ...
  0  8  79  404  1460   4220  10423   22904 ...
  0 16 195 1296  5890  20640  60021  151840 ...
  0 24 477 4380 25275 107100 364854 1057392 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275
G. Melançon, C. Reutenauer, On a Class of Lyndon Words Extending Christoffel Words and Related to a Multidimensional Continued Fraction Algorithm, J. Int. Seq. 16 (2013) #13.9.7, Corollary 6.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]

Columns 2-6 are A001371, A032294, A032295, A032296, A056347.

Cf. A081720, A273891, A276543, A152176.

A276550 := proc(n,k)
    local d ;
    add( numtheory[mobius](n/d)*A081720(d,k),d=numtheory[divisors](n)) ;
end proc:
seq(seq(A276550(n,d-n),n=1..d-1),d=2..10) ; # R. J. Mathar, Jan 22 2022

t[n_, k_] := Sum[EulerPhi[d] k^(n/d), {d, Divisors[n]}]/(2n) + (k^Floor[(n+1)/2] + k^Ceiling[(n+1)/2])/4;
T[n_, k_] := Sum[MoebiusMu[d] t[n/d, k], {d, Divisors[n]}];
Table[T[n-k+1, k], {n, 1, 11}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Mar 26 2020 *)

T(n, k) = Sum_{d|n} mu(n/d) * A081720(d,k) for k<=n. Corrected Jan 22 2022

A056362 Number of primitive (period n) bracelet structures using a maximum of three different colored beads.

Original entry on oeis.org

1, 1, 1, 2, 4, 8, 18, 39, 94, 222, 572, 1463, 3934, 10584, 29211, 80808, 226430, 636320, 1800318, 5107479, 14548360, 41538874, 118927919, 341187047, 980838750, 2824561080, 8147547156, 23536592010, 68087313892, 197216119544, 571924673368, 1660419530055, 4825587979390

Offset: 0

Marks R. Nester

nonn

Turning over will not create a new bracelet. Permuting the colors of the beads 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]

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

Cf. A002075, A056353, A056367, A276543.

a(n) = Sum_{d|n} mu(d)*A056353(n/d) for n > 0.

a(n) = Sum_{k=1..3} A276543(n, k) for n > 0. - Andrew Howroyd, Oct 26 2019

a(0)=1 prepended and terms a(28) and beyond from Andrew Howroyd, Oct 26 2019

A056363 Number of primitive (period n) bracelet structures using a maximum of four different colored beads.

Original entry on oeis.org

1, 1, 1, 2, 5, 10, 29, 72, 230, 700, 2421, 8308, 30070, 108990, 403188, 1497057, 5607200, 21076570, 79595257, 301492044, 1145558141, 4363503609, 16660196142, 63741248200, 244339616370, 938255682540, 3608668279965, 13900021843855, 53614339995060, 207062143625710

Offset: 0

Marks R. Nester

nonn

Turning over will not create a new bracelet. Permuting the colors of the beads 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]

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

Cf. A056300, A056354, A056368, A276543.

a(n) = Sum_{d|n} mu(d)*A056354(n/d) for n > 0.

a(n) = Sum_{k=1..4} A276543(n, k) for n > 0. - Andrew Howroyd, Oct 26 2019

a(0)=1 prepended and terms a(26) and beyond from Andrew Howroyd, Oct 26 2019

A056364 Number of primitive (period n) bracelet structures using a maximum of five different colored beads.

Original entry on oeis.org

1, 1, 1, 2, 5, 11, 32, 88, 315, 1134, 4691, 19838, 88467, 399679, 1839857, 8533474, 39893579, 187393549, 884152226, 4185740194, 19876589828, 94633345517, 451615299593, 2159769331316, 10348546459872, 49672000435712, 238804870806677, 1149792978953236, 5543621480301561

Offset: 0

Marks R. Nester

nonn

Turning over will not create a new bracelet. Permuting the colors of the beads 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]

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

Cf. A056301, A056355, A056369, A276543.

a(n) = Sum_{d|n} mu(d)*A056355(n/d) for n > 0.

a(n) = Sum_{k=1..5} A276543(n, k) for n > 0. - Andrew Howroyd, Oct 26 2019

a(0)=1 prepended and terms a(25) and beyond from Andrew Howroyd, Oct 26 2019

A056365 Number of primitive (period n) bracelet structures using a maximum of six different colored beads.

Original entry on oeis.org

1, 1, 1, 2, 5, 11, 33, 91, 342, 1305, 5940, 28227, 144545, 760109, 4112455, 22571026, 125410006, 702370207, 3959138462, 22425417823, 127530807883, 727630240442, 4163114784625, 23876534534361, 137228556011456, 790200525479694, 4557943660168122, 26331300028827092

Offset: 0

Marks R. Nester

nonn

Turning over will not create a new bracelet. Permuting the colors of the beads 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]

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

Cf. A056302, A056356, A056370, A276543.

a(n) = Sum_{d|n} mu(d)*A056356(n/d) for n > 0.

a(n) = Sum_{k=1..6} A276543(n, k) for n > 0. - Andrew Howroyd, Oct 26 2019

a(0)=1 prepended and terms a(25) and beyond from Andrew Howroyd, Oct 26 2019

A056367 Number of primitive (period n) bracelet structures using exactly three different colored beads.

Original entry on oeis.org

0, 0, 1, 2, 5, 13, 31, 80, 201, 533, 1401, 3822, 10395, 28859, 80201, 225286, 634265, 1796433, 5100325, 14534758, 41513402, 118879249, 341094843, 980661980, 2824223490, 8146897815, 23535345170

Offset: 1

Marks R. Nester

nonn

Turning over will not create a new bracelet. Permuting the colors of the beads 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 A276543.

Cf. A056304.

A056362(n)-A000046(n).

A056368 Number of primitive (period n) bracelet structures using exactly four different colored beads.

Original entry on oeis.org

0, 0, 0, 1, 2, 11, 33, 136, 478, 1849, 6845, 26136, 98406, 373977, 1416249, 5380770, 20440250, 77794939, 296384565, 1131009781, 4321964735, 16541268223, 63400061153, 243358777620, 935431121460, 3600520732809

Offset: 1

Marks R. Nester

nonn

Turning over will not create a new bracelet. Permuting the colors of the beads 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 A276543.

Cf. A056305.

A056363(n)-A056362(n).

cp's OEIS Frontend

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

A276544 Triangle read by rows: T(n,k) = number of primitive (aperiodic) reversible string structures with n beads using exactly k different colors.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A276550 Array read by antidiagonals: T(n,k) = number of primitive (period n) bracelets using a maximum of k different colored beads.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A056362 Number of primitive (period n) bracelet structures using a maximum of three different colored beads.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A056363 Number of primitive (period n) bracelet structures using a maximum of four different colored beads.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A056364 Number of primitive (period n) bracelet structures using a maximum of five different colored beads.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions