A107424 -id:A107424 - 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).

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

A056303 Number of primitive (period n) n-bead necklace structures using exactly two different colored beads.

Original entry on oeis.org

0, 1, 1, 2, 3, 5, 9, 16, 28, 51, 93, 170, 315, 585, 1091, 2048, 3855, 7280, 13797, 26214, 49929, 95325, 182361, 349520, 671088, 1290555, 2485504, 4793490, 9256395, 17895679, 34636833, 67108864, 130150493, 252645135, 490853403, 954437120, 1857283155

Offset: 1

Marks R. Nester

nonn

Turning over the necklace is not allowed. Colors may be permuted without changing the necklace structure.
Identical to A000048 for n>1.
Number of binary Lyndon words of length n with an odd number of zeros. - Joerg Arndt, Oct 26 2015

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

Cf. A000007, A000048, A001037, A056295.

vector(100, n, sumdiv(n, d, (d%2)*(moebius(d)*2^(n/d)))/(2*n)-!(n-1)) \\ Altug Alkan, Oct 26 2015

from sympy import divisors, mobius
def a000048(n): return 1 if n<1 else sum([mobius(d)*2**(n/d) for d in divisors(n) if d%2 == 1])/(2*n)
def a(n): return a000048(n) - 0**(n - 1) # Indranil Ghosh, Apr 28 2017

a(n) = Sum mu(d)*A056295(n/d) where d divides n.

a(n) = A000048(n) - A000007(n-1).

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.

Original entry on oeis.org

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])) }

A056304 Number of primitive (period n) n-bead necklace structures using exactly three different colored beads.

Original entry on oeis.org

0, 0, 1, 2, 5, 17, 43, 124, 338, 941, 2591, 7234, 20125, 56407, 158349, 446492, 1262225, 3580330, 10181479, 29031306, 82968799, 237642659, 682014587, 1960974220, 5647919640, 16292741605, 47069104274, 136166647110, 394418199725, 1143821887473, 3320790074371

Offset: 1

Marks R. Nester

nonn

Turning over the necklace is not allowed. Colors may be permuted without changing the necklace 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 A107424.

Cf. A000048, A002075, A008683, A056288, A056296.

a(n) = Sum_{d|n} mu(d)*A056296(n/d), where mu = A008683 is the Möbius function.

a(n) = A002075(n) - A000048(n).

a(28)-a(31) from Pontus von Brömssen, Aug 04 2024

A056302 Number of primitive (period n) n-bead necklace structures using a maximum of six different colored beads.

Original entry on oeis.org

1, 1, 2, 5, 11, 39, 125, 532, 2301, 11010, 54681, 284023, 1509851, 8194902, 45080652, 250641356, 1404374247, 7917209005, 44848645457, 255055220735, 1455247360000, 8326191235902, 47752990403133

Offset: 1

Marks R. Nester

nonn

Turning over the necklace is not allowed. Colors may be permuted without changing the necklace structure.

a(n) = A107424(n, 1)+A107424(n, 2)+...+A107424(n, 6). - David Wasserman, May 31 2005

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]

Cf. A032164.

sum mu(d)*A056294(n/d) where d|n and n>0.

A056305 Number of primitive (period n) n-bead necklace structures using exactly four different colored beads.

Original entry on oeis.org

0, 0, 0, 1, 2, 13, 50, 220, 866, 3435, 13250, 51061, 194810, 742601, 2823764, 10738660, 40843370, 155493872, 592614050, 2261622287, 8643289484, 33080907357, 126797503250, 486710920300, 1870851589552

Offset: 1

Marks R. Nester

nonn

Turning over the necklace is not allowed. Colors may be permuted without changing the necklace 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 A107424.

Cf. A056289.

Sum mu(d)*A056297(n/d) where d|n. Alternatively, A056300(n)-A002075(n)..

A276547 Number of primitive (period n) n-bead necklace structures using an infinite alphabet.

Original entry on oeis.org

1, 1, 2, 5, 11, 39, 126, 537, 2358, 11690, 61689, 351725, 2126496, 13639244, 92197509, 655035225, 4874404107, 37893368072, 306986431846, 2586209738004, 22612848403442, 204850732418594, 1919652428481929, 18581619724011091, 185543613289200937, 1908894098864372104

Offset: 1

Andrew Howroyd, Apr 09 2017

nonn

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

Row sums of A107424.

Cf. A084423.

u[0, ] = 1; u[k, j_] := u[k, j] = Sum[Binomial[k - 1, i - 1]*DivisorSum[j, u[k - i, j]*#^(i - 1)&], {i, 1, k}];
b[0] = 1; b[n_] := DivisorSum[n, EulerPhi[#]*u[n/#, #]&]/n;
a[1] = 1; a[n_] := DivisorSum[n, MoebiusMu[n/#]*b[#]&];
Array[a, 26] (* Jean-François Alcover, Jun 16 2017, using Franklin T. Adams-Watters' code for A084423 *)

a(n) = Sum_{d|n} mu(n/d) * A084423(d).

A056306 Number of primitive (period n) n-bead necklace structures using exactly five different colored beads.

Original entry on oeis.org

0, 0, 0, 0, 1, 3, 20, 136, 773, 4280, 22430, 115097, 577577, 2863207, 14051163, 68515378, 332514803, 1608799915, 7767857090, 37460384315, 180536313527, 869901375049, 4192038616700, 20208367780744

Offset: 1

Marks R. Nester

nonn

Turning over the necklace is not allowed. Colors may be permuted without changing the necklace 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 A107424.

Cf. A056290.

Sum mu(d)*A056298(n/d) where d|n. Alternatively, A056301(n)-A056300(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

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

A056303 Number of primitive (period n) n-bead necklace structures using exactly two different colored beads.

Views

Author

Keywords

Comments

References

Crossrefs

Programs

PARI

Python

Formula

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

A056304 Number of primitive (period n) n-bead necklace structures using exactly three different colored beads.

Views

Author

Keywords

Comments

References

Crossrefs

Formula

Extensions

A056302 Number of primitive (period n) n-bead necklace structures using a maximum of six different colored beads.

Views

Author

Keywords

Comments

References

Crossrefs

Formula

A056305 Number of primitive (period n) n-bead necklace structures using exactly four different colored beads.

Views

Author

Keywords