A056297 -id:A056297 - cp's OEIS frontend

A152175 Triangle read by rows: T(n,k) is the number of k-block partitions of an n-set up to rotations.

1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 3, 5, 2, 1, 1, 7, 18, 13, 3, 1, 1, 9, 43, 50, 20, 3, 1, 1, 19, 126, 221, 136, 36, 4, 1, 1, 29, 339, 866, 773, 296, 52, 4, 1, 1, 55, 946, 3437, 4281, 2303, 596, 78, 5, 1, 1, 93, 2591, 13250, 22430, 16317, 5817, 1080, 105, 5, 1, 1, 179, 7254, 51075, 115100, 110462, 52376, 13299, 1873, 147, 6, 1

Offset: 1

Vladeta Jovovic, Nov 27 2008

Number of n-bead necklace structures using exactly k different colored beads. Turning over the necklace is not allowed. Permuting the colors does not change the structure. - Andrew Howroyd, Apr 06 2017

			Triangle begins with T(1,1):
  1;
  1,   1;
  1,   1,     1;
  1,   3,     2,      1;
  1,   3,     5,      2,      1;
  1,   7,    18,     13,      3,      1;
  1,   9,    43,     50,     20,      3,      1;
  1,  19,   126,    221,    136,     36,      4,      1;
  1,  29,   339,    866,    773,    296,     52,      4,     1;
  1,  55,   946,   3437,   4281,   2303,    596,     78,     5,    1;
  1,  93,  2591,  13250,  22430,  16317,   5817,   1080,   105   , 5,   1;
  1, 179,  7254,  51075, 115100, 110462,  52376,  13299,  1873,  147,   6, 1;
  1, 315, 20125, 194810, 577577, 717024, 439648, 146124, 27654, 3025, 187, 6, 1;
  ...
For T(4,2)=3, the set partitions are AAAB, AABB, and ABAB.
For T(4,3)=2, the set partitions are AABC and ABAC.

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
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
Tilman Piesk, Partition related number triangles

Columns 2-6 are A056295, A056296, A056297, A056298, A056299.
Row sums are A084423.
Partial row sums include A000013, A002076, A056292, A056293, A056294.
Cf. A075195, A087854, A008277 (set partitions), A284949 (up to reflection), A152176 (up to rotation and reflection).
A(1,n,k) in formula is the Stirling subset number A008277.
A(2,n,k) in formula is A293181; A(3,n,k) in formula is A294201.

(* Using recursion formula from Gilbert and Riordan:*)
Adn[d_, n_] := Adn[d, n] = Which[0==n, 1, 1==n, DivisorSum[d, x^# &],
  1==d, Sum[StirlingS2[n, k] x^k, {k, 0, n}],
  True, Expand[Adn[d, 1] Adn[d, n-1] + D[Adn[d, n - 1], x] x]];
Table[CoefficientList[DivisorSum[n, EulerPhi[#] Adn[#, n/#] &]/(x n), x],
   {n, 1, 10}] // Flatten (* Robert A. Russell, Feb 23 2018 *)
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]]
Table[DivisorSum[n,EulerPhi[#]Adnk[#,n/#,k]&]/n,{n,1,12},{k,1,n}] // Flatten (* Robert A. Russell, Oct 16 2018 *)

\\ see A056391 for Polya enumeration functions
T(n,k) = NonequivalentStructsExactly(CyclicPerms(n), k); \\ Andrew Howroyd, Oct 14 2017

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))]))}
{ my(A=R(12)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Sep 20 2019

T(n,k) = (1/n)*Sum_{d|n} phi(d)*A(d,n/d,k), where 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)). - Robert A. Russell, Oct 16 2018

A294793 Triangle read by rows, 1 <= k <= n: T(n,k) = non-isomorphic colorings of a toroidal n X k grid using exactly four colors under translational symmetry and swappable colors.

Original entry on oeis.org

0, 0, 1, 0, 13, 874, 1, 235, 51075, 10741819, 2, 3437, 2823766, 2261625725, 1870851589562, 13, 51275, 155495153, 486711524815, 1600136051453135, 5465007068038102643, 50, 742651, 8643289534, 107092397450897, 1405227969932349726, 19188864521773558375127, 269482732023591671431784330, 221, 10741763, 486710971595, 24009547064476683

Offset: 1

Marko Riedel, Nov 08 2017

Two colorings are equivalent if there is a permutation of the colors that takes one to the other in addition to translational symmetries on the torus. (Power Group Enumeration.)

F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973.

Marko Riedel et al., Burnside lemma and translational symmetries of the torus.

Cf. A294684, A294685, A294686, A294687, A294791, A294792, A294794, A295197. T(n,1) is A056297.

T(n,k) = (1/(n*k*Q!))*(Sum_{sigma in S_Q} Sum_{d|n} Sum_{f|k} phi(d) phi(f) [[forall j_l(sigma) > 0 : l|lcm(d,f) ]] P(gcd(d,f)*(n/d)*(k/f), sigma)) where P(F, sigma) = F! [z^F] Product_{l=1..Q} (exp(lz)-1)^j_l(sigma) with Q=4. The notation j_l(sigma) is from the Harary text and gives the number of cycles of length l in the permutation sigma. [[.]] is an Iverson bracket.

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

A320644 Number of chiral pairs of color patterns (set partitions) in a cycle of length n using exactly 4 colors (subsets).

Original entry on oeis.org

0, 0, 0, 0, 0, 2, 17, 84, 388, 1586, 6405, 24927, 96404, 368641, 1407515, 5357974, 20403120, 77699323, 296229485, 1130614092, 4321324766, 16539645539, 63397442097, 243352167691, 935420468092, 3600493932070, 13876442107403, 53546144395718, 206864753332164, 800067806813323, 3097590602034137, 12004772596768984, 46568647645538594, 180809553280920680

Offset: 1

Robert A. Russell, Oct 18 2018

Two color patterns are the same if the colors are permuted. A chiral cycle is different from its reverse.
Adnk[d,n,k] in Mathematica program is coefficient of x^k in A(d,n)(x) in Gilbert and Riordan reference.
There are nonrecursive formulas, generating functions, and computer programs for A056297 and A304974, which can be used in conjunction with the first formula.

			For a(6)=2, the chiral pairs are AABACD-AABCAD and AABCBD-AABCDC.

Andrew Howroyd, Table of n, a(n) for n = 1..200
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

Column 4 of A320647.

Cf. A056297 (oriented), A056359 (unoriented), A304974 (achiral).

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 *)
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]]
k=4; Table[DivisorSum[n,EulerPhi[#]Adnk[#,n/#,k]&]/(2n) - Ach[n,k]/2,{n,40}]

a(n) = (A056297(n) - A304974(n)) / 2 = A056297(n) - A056359(n) = A056359(n) - A304974(n).

a(n) = -Ach(n,k)/2 + (1/2n)*Sum_{d|n} phi(d)*A(d,n/d,k), where k=4 is number of colors or sets, 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)).

A328130 Number of n-bead necklace structures with beads of exactly four colors and no adjacent beads having the same color.

Original entry on oeis.org

0, 0, 0, 1, 1, 5, 10, 33, 83, 237, 640, 1817, 5005, 14099, 39504, 111585, 315235, 894845, 2544220, 7256607, 20738097, 59405343, 170488450, 490221899, 1411923987, 4073098085, 11767069378, 34041318969, 98603778565, 285954140473, 830194632190, 2412764894021, 7018972487319

Offset: 1

Andrew Howroyd, Oct 04 2019

nonn

Colors may be permuted without changing the necklace structure.

			Necklace structures for n=4..7 are:
a(4) = 1: ABCD;
a(5) = 1: ABACD;
a(6) = 5: ABABCD, ABACAD, ABACBD, ABACDC, ABCABD;
a(7) = 10: ABABACD, ABABCAD, ABABCBD, ABABCDC, ABACABD, ABACADC, ABACBCD, ABACBDC, ABACDBC, ABCABCD.

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

Column k=4 of A327396.

Cf. A056297, A309673, A327397.

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

A328741 Number of n-bead necklace structures which are not self-equivalent under a nonzero rotation using exactly four different colored beads.

Original entry on oeis.org

0, 0, 0, 0, 2, 9, 50, 206, 862, 3384, 13250, 50852, 194810, 741884, 2823712, 10735998, 40843370, 155483873, 592614050, 2261585918, 8643288808, 33080772468, 126797503250, 486710415710, 1870851589552, 7201012694120, 27752927349880, 107092389688830, 413729680838330

Offset: 1

Andrew Howroyd, Oct 26 2019

nonn

Permuting the colors does not change the structure.

			For n=6, the 9 necklace structures are: aaabcd, aabacd, aabcad, aabbcd, aabcbd, aabcdb, aacbdb, ababcd, abacbd.

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

Column 4 of A327693.

Cf. A056297, A056305, A328740, A328743.

a(p) = A056297(p) = A056305(p) for prime p.

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

cp's OEIS Frontend

A152175 Triangle read by rows: T(n,k) is the number of k-block partitions of an n-set up to rotations.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A294793 Triangle read by rows, 1 <= k <= n: T(n,k) = non-isomorphic colorings of a toroidal n X k grid using exactly four colors under translational symmetry and swappable colors.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A320644 Number of chiral pairs of color patterns (set partitions) in a cycle of length n using exactly 4 colors (subsets).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A328130 Number of n-bead necklace structures with beads of exactly four colors and no adjacent beads having the same color.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A328741 Number of n-bead necklace structures which are not self-equivalent under a nonzero rotation using exactly four different colored beads.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

References

Crossrefs

Formula