A152176 -id:A152176 - cp's OEIS frontend

A056356 Number of bracelet structures using a maximum of six different colored beads.

1, 1, 2, 3, 7, 12, 37, 92, 349, 1308, 5953, 28228, 144587, 760110, 4112548, 22571040, 125410355, 702370208, 3959139804, 22425417824, 127530813841, 727630240536, 4163114812854, 23876534534362, 137228556156385, 790200525479706, 4557943660928233, 26331300028828400

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. A056294, A152176.

Use de Bruijn's generalization of Polya's enumeration theorem as discussed in reference.

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

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

A056357 Number of bracelet structures using exactly two different colored beads.

Original entry on oeis.org

0, 1, 1, 3, 3, 7, 8, 17, 22, 43, 62, 121, 189, 361, 611, 1161, 2055, 3913, 7154, 13647, 25481, 48733, 92204, 176905, 337593, 649531, 1246862, 2405235, 4636389, 8964799, 17334800, 33588233, 65108061, 126390031, 245492243, 477353375, 928772649, 1808676325

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.

Also the number of distinct twills of period n. [Grünbaum and Shephard]

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..1000
B. Grünbaum and G. C. Shephard, Satins and twills: an introduction to the geometry of fabrics, Math. Mag., 53 (1980), 139-161. See Theorem 2. [From _N. J. A. Sloane_, Jul 13 2011]

Column 2 of A152176.

Cf. A056295.

with(numtheory);
rho:=n->(3+(-1)^n)/2;
f:=n->2^((n+rho(n))/2-2) + (1/(4*n))*(add(phi(d)*rho(d)*2^(n/d), d in divisors(n))) - 1;
# N. J. A. Sloane, Jul 13 2011

a(n) = {if(n<1, 0, 2^(n\2-1) - 1 + sumdiv(n, k, eulerphi(2*k) * 2^(n/k)) / (4*n))}; \\ Andrew Howroyd, Oct 24 2019

a(n) = A000011(n) - 1.

For an explicit formula see the Maple program.

Terms a(32) and beyond from Andrew Howroyd, Oct 24 2019

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

A209612 Triangle read by rows: T(n,k) is the number of k-block noncrossing partitions of n-set up to rotations and reflections.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 4, 2, 1, 1, 3, 8, 8, 3, 1, 1, 3, 12, 17, 12, 3, 1, 1, 4, 19, 41, 41, 19, 4, 1, 1, 4, 27, 78, 116, 78, 27, 4, 1, 1, 5, 38, 148, 298, 298, 148, 38, 5, 1, 1, 5, 50, 250, 680, 932, 680, 250, 50, 5, 1

Offset: 1

Tilman Piesk, Mar 10 2012

Like the Narayana triangle A001263 (and unlike A152176) this triangle is symmetric.

			Triangle begins:
1;
1,  1;
1,  1,  1;
1,  2,  2,  1;
1,  2,  4,  2,  1;
1,  3,  8,  8,  3,  1;
1,  3, 12, 17, 12,  3,  1;
1,  4, 19, 41, 41, 19,  4,  1;
1,  4, 27, 78,116, 78, 27,  4,  1;
1,  5, 38,148,298,298,148, 38,  5,  1

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Tilman Piesk, Partition related number triangles

Cf. A111275 (row sums)

Cf. A088855, A209805.

b[n_, k_] := Binomial[n - 1, n - k]*Binomial[n, n - k];
T[n_, k_] := (n*Binomial[Quotient[n - 1, 2], Quotient[k - 1, 2]]*Binomial[ Quotient[n, 2], Quotient[k, 2]] + DivisorSum[GCD[n, k], EulerPhi[#]* b[n/#, k/#]&] + DivisorSum[GCD[n, k - 1], EulerPhi[#]*b[n/#, (n + 1 - k)/#]&] - k*Binomial[n, k]^2/(n - k + 1))/(2*n);
Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 30 2018, after Andrew Howroyd *)

b(n,k)=binomial(n-1,n-k)*binomial(n,n-k);
T(n,k)=(n*binomial((n-1)\2, (k-1)\2)*binomial(n\2, k\2) + sumdiv(gcd(n,k), d, eulerphi(d)*b(n/d,k/d)) + sumdiv(gcd(n,k-1), d, eulerphi(d)*b(n/d,(n+1-k)/d)) - k*binomial(n,k)^2/(n-k+1))/(2*n); \\ Andrew Howroyd, Nov 15 2017

T(n,k) = (A088855(n,k) + A209805(n,k))/2. - Andrew Howroyd, Nov 15 2017

A320748 Array read by antidiagonals: T(n,k) is the number of color patterns (set partitions) in an unoriented cycle of length n using k or fewer colors (subsets).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 3, 4, 1, 1, 2, 3, 6, 4, 1, 1, 2, 3, 7, 9, 8, 1, 1, 2, 3, 7, 11, 22, 9, 1, 1, 2, 3, 7, 12, 33, 40, 18, 1, 1, 2, 3, 7, 12, 36, 73, 100, 23, 1, 1, 2, 3, 7, 12, 37, 89, 237, 225, 44, 1, 1, 2, 3, 7, 12, 37, 92, 322, 703, 582, 63, 1, 1, 2, 3, 7, 12, 37, 93, 349, 1137, 2433, 1464, 122, 1, 1, 2, 3, 7, 12, 37, 93, 353, 1308, 4704, 8309, 3960, 190, 1, 1, 2, 3, 7, 12, 37, 93, 354, 1345, 5953, 19839, 30108, 10585, 362, 1

Offset: 1

Robert A. Russell, Oct 21 2018

Two color patterns are equivalent if the colors are permuted. An unoriented cycle counts each chiral pair as one, i.e., they are equivalent.
Adnk[d,n,k] in Mathematica program is coefficient of x^k in A(d,n)(x) in Gilbert and Riordan reference.
T(n,k)=Pi_k(C_n) which is the number of non-equivalent partitions of the cycle on n vertices, with at most k parts. Two partitions P1 and P2 of a graph G are said to be equivalent if there is a nontrivial automorphism of G which maps P1 onto P2. - Bahman Ahmadi, Aug 21 2019
In other words, the number of n-bead bracelet structures using a maximum of k different colored beads. - Andrew Howroyd, Oct 30 2019

			Array begins with T(1,1):
1   1    1     1     1      1      1      1      1      1      1      1 ...
1   2    2     2     2      2      2      2      2      2      2      2 ...
1   2    3     3     3      3      3      3      3      3      3      3 ...
1   4    6     7     7      7      7      7      7      7      7      7 ...
1   4    9    11    12     12     12     12     12     12     12     12 ...
1   8   22    33    36     37     37     37     37     37     37     37 ...
1   9   40    73    89     92     93     93     93     93     93     93 ...
1  18  100   237   322    349    353    354    354    354    354    354 ...
1  23  225   703  1137   1308   1345   1349   1350   1350   1350   1350 ...
1  44  582  2433  4704   5953   6291   6345   6350   6351   6351   6351 ...
1  63 1464  8309 19839  28228  31284  31874  31944  31949  31950  31950 ...
1 122 3960 30108 88508 144587 171283 178190 179204 179300 179306 179307 ...
For T(7,2)=9, the patterns are AAAAAAB, AAAAABB, AAAABAB, AAAABBB, AAABAAB, AAABABB, AABAABB, AABABAB, and AAABABB; only the last is chiral, paired with AAABBAB.

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
B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

Partial row sums of A152176.
Columns 1-6 are A057427, A000011, A056353, A056354, A056355, A056356
For increasing k, columns converge to A084708.
Cf. A320747 (oriented), A320742 (chiral), A305749 (achiral).

Adnk[d_,n_,k_] := Adnk[d,n,k] = If[n>0 && k>0, Adnk[d,n-1,k]k + DivisorSum[d, Adnk[d,n-1,k-#]&], Boole[n == 0 && k == 0]]
Ach[n_,k_] := Ach[n,k] = If[n<2, Boole[n==k && n>=0], k Ach[n-2,k] + Ach[n-2,k-1] + Ach[n-2,k-2]] (* A304972 *)
Table[Sum[(DivisorSum[n, EulerPhi[#] Adnk[#,n/#,j]&]/n + Ach[n,j])/2, {j,k-n+1}], {k,15}, {n,k}] // Flatten

\\ 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); for(i=2, n, M[,i] += M[,i-1]); M}
{ my(A=T(12)); for(n=1, #A, print(A[n, ])) } \\ Andrew Howroyd, Nov 03 2019

T(n,k) = Sum_{j=1..k} Ach(n,j)/2 + (1/2n)*Sum_{d|n} phi(d)*A(d,n/d,j), where Ach(n,k) = [n>=0 & n<2 & n==k] + [n>1]*(k*Ach(n-2,k)+Ach(n-2,k-1)+Ach(n-2,k-2)) and A(d,n,k) = [n==0 & k==0] + [n>0 & k>0]*(k*A(d,n-1,k) + Sum_{j|d} A(d,n-1,k-j)).

T(n,k) = (A320747(n,k) + A305749(n,k)) / 2 = A320747(n,k) - A320742(n,k) = A320742(n,k) + A305749(n,k).

A056358 Number of bracelet structures using exactly three different colored beads.

Original entry on oeis.org

0, 0, 1, 2, 5, 14, 31, 82, 202, 538, 1401, 3838, 10395, 28890, 80207, 225368, 634265, 1796648, 5100325, 14535298, 41513434, 118880650, 341094843, 980665898, 2824223495, 8146908210, 23535345372, 68084937912, 197211483155, 571915789978, 1660402195255, 4825554617686

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]

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

Column 3 of A152176.

Cf. A000011, A056296, A056353, A214307.

a(n) = A056353(n) - A000011(n).

Terms a(28) and beyond from Andrew Howroyd, Oct 24 2019

A056359 Number of bracelet structures using exactly four different colored beads.

Original entry on oeis.org

0, 0, 0, 1, 2, 11, 33, 137, 478, 1851, 6845, 26148, 98406, 374010, 1416251, 5380907, 20440250, 77795428, 296384565, 1131011633, 4321964768, 16541275068, 63400061153, 243358803904, 935431121462, 3600520831215, 13876485252323, 53546253055179, 206864927506166, 800068244639812

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]

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

Column 4 of A152176.

Cf. A056297, A056353, A056354, A214309.

a(n) = A056354(n) - A056353(n).

Terms a(27) and beyond from Andrew Howroyd, Oct 24 2019

A056360 Number of bracelet structures using exactly five different colored beads.

Original entry on oeis.org

0, 0, 0, 0, 1, 3, 16, 85, 434, 2271, 11530, 58400, 290689, 1436685, 7036418, 34286464, 166316979, 804557406, 3884248150, 18731033958, 90269841924, 434955114981, 2096028083116, 10104206901987, 48733744753173, 235196202817401, 1135892957109815, 5490007141743186

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]

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

Column 5 of A152176.

Cf. A056298, A056354, A056355, A214311.

a(n) = A056355(n) - A056354(n).

Terms a(25) and beyond from Andrew Howroyd, Oct 24 2019

A056361 Number of bracelet structures using exactly six different colored beads.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 3, 27, 171, 1249, 8389, 56079, 360430, 2272601, 14037552, 85516454, 514976658, 3074986408, 18239677629, 107654219304, 632996894928, 3711499493421, 21716765203045, 126880009607690, 740528525043982, 4319138789721875, 25181507049874027, 146788327084831744

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]

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

Column 6 of A152176.

Cf. A056299, A056355, A056356.

a(n) = A056356(n) - A056355(n).

Terms a(25) and beyond from Andrew Howroyd, Oct 24 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

cp's OEIS Frontend

A056356 Number of bracelet structures using a maximum of six different colored beads.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A056357 Number of bracelet structures using exactly two different colored beads.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

PARI

Formula

Extensions

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

A209612 Triangle read by rows: T(n,k) is the number of k-block noncrossing partitions of n-set up to rotations and reflections.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A320748 Array read by antidiagonals: T(n,k) is the number of color patterns (set partitions) in an unoriented cycle of length n using k or fewer colors (subsets).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A056358 Number of bracelet structures using exactly three different colored beads.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A056359 Number of bracelet structures using exactly four different colored beads.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula