A056296 -id:A056296 - 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

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

Original entry on oeis.org

0, 0, 3, 1, 18, 345, 2, 136, 7254, 447156, 5, 946, 158355, 29032254, 5647919665, 18, 7324, 3580802, 1961010826, 1143822046786, 694881637942816, 43, 56450, 82968843, 136166703562, 238244961999013, 434202285631866206, 813943290958393433377, 126, 447138, 1960981598, 9651082393912, 50656925726930746, 276966813318877426118, 1557582240509759704455566

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, A294793, A294794, A295197. T(n,1) is A056296.

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=3. 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.

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

Original entry on oeis.org

0, 0, 0, 0, 0, 4, 12, 44, 137, 408, 1190, 3416, 9730, 27560, 78148, 221250, 627960, 1784038, 5081154, 14496956, 41455409, 118764600, 340919744, 980315700, 2823696150, 8145853520, 23533759241, 68081765650, 197206716570, 571906256808, 1660387879116, 4825525985408, 14037945170525, 40875277302720, 119122416494961, 347440682773324, 1014151818975190, 2962391932326680, 8659301777595196, 25328461701728194

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 A056296 and A304973, which can be used in conjunction with the first formula.

			For a(6)=4, the chiral pairs are AAABBC-AAABCC, AABABC-AABCAC, AABACB-AABCAB, and AABACC-AABBAC.

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 3 of A320647.

Cf. A056296 (oriented), A056358 (unoriented), A304973 (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=3; Table[DivisorSum[n,EulerPhi[#]Adnk[#,n/#,k]&]/(2n) - Ach[n,k]/2,{n,40}]

a(n) = (A056296(n) - A304973(n)) / 2 = A056296(n) - A056358(n) = A056358(n) - A304973(n).

a(n) = -Ach(n,k)/2 + (1/2n)*Sum_{d|n} phi(d)*A(d,n/d,k), where k=3 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)).

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

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

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

Original entry on oeis.org

0, 0, 1, 1, 1, 3, 3, 7, 11, 19, 31, 63, 105, 201, 367, 695, 1285, 2451, 4599, 8775, 16651, 31837, 60787, 116639, 223697, 430395, 828525, 1598227, 3085465, 5965999, 11545611, 22370999, 43383571, 84217615, 163617805, 318150719, 619094385, 1205614053, 2349384031

Offset: 1

Andrew Howroyd, Oct 04 2019

nonn

Colors may be permuted without changing the necklace structure.

			Necklace structures for n=3..8 are:
  a(3) = 1: ABC;
  a(4) = 1: ABAC;
  a(5) = 1: ABABC;
  a(6) = 3: ABABAC, ABACBC, ABCABC;
  a(7) = 3: ABABABC, ABABCAC, ABACABC;
  a(8) = 7: ABABABAC, ABABACAC, ABABACBC, ABABCABC, ABABCBAC, ABACABAC, ABACBABC.

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

Column k=3 of A327396.

Cf. A056296, A306888, A328130.

a(n) = A306888(n) - A000035(n-1). - Yuchun Ji, Mar 13 2020

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

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

Original entry on oeis.org

0, 0, 0, 1, 5, 13, 43, 116, 335, 920, 2591, 7173, 20125, 56260, 158333, 446098, 1262225, 3579227, 10181479, 29028405, 82968695, 237634700, 682014587, 1960951980, 5647919640, 16292680600, 47069103545, 136166476875, 394418199725, 1143821408316, 3320790074371

Offset: 1

Andrew Howroyd, Oct 26 2019

nonn

Permuting the colors does not change the structure.

			For n=5, the 5 necklace structures are: aaabc, aabac, aabbc, aabcb, ababc.

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

Column 3 of A327693.

Cf. A056296, A056304, A328741, A328742.

a(p) = A056296(p) = A056304(p) for prime p >= 5.

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

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

References

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula