A056361 -id:A056361 - cp's OEIS frontend

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

1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 3, 5, 2, 1, 1, 7, 14, 11, 3, 1, 1, 8, 31, 33, 16, 3, 1, 1, 17, 82, 137, 85, 27, 4, 1, 1, 22, 202, 478, 434, 171, 37, 4, 1, 1, 43, 538, 1851, 2271, 1249, 338, 54, 5, 1, 1, 62, 1401, 6845, 11530, 8389, 3056, 590, 70, 5, 1, 1, 121, 3838, 26148

Offset: 1

Vladeta Jovovic, Nov 27 2008

Number of bracelet structures of length n using exactly k different colored beads. Turning over will not create a new bracelet. Permuting the colors of the beads will not change the structure. - Andrew Howroyd, Apr 06 2017
The number of achiral structures (A) is given in A140735 (odd n) and A293181 (even n).  The number of achiral structures plus twice the number of chiral pairs (A+2C) is given in A152175.  These can be used to determine A+C by taking half their average, as is done in the Mathematica program. - Robert A. Russell, Feb 24 2018
T(n,k)=pi_k(C_n) which is the number of non-equivalent partitions of the cycle on n vertices, with exactly 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. - Mohammad Hadi Shekarriz, Aug 21 2019

			Triangle begins:
  1;
  1,  1;
  1,  1,   1;
  1,  3,   2,    1;
  1,  3,   5,    2,    1;
  1,  7,  14,   11,    3,    1;
  1,  8,  31,   33,   16,    3,   1;
  1, 17,  82,  137,   85,   27,   4,  1;
  1, 22, 202,  478,  434,  171,  37,  4, 1;
  1, 43, 538, 1851, 2271, 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
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.
Tilman Piesk, Partition related number triangles
Marko Riedel, Bracelets with swappable colors classified by the distribution of colors, Power Group Enumeration algorithm
Marko Riedel, Maple code for the number of bracelets with some number of swappable colors by Power Group Enumeration
Mohammad Hadi Shekarriz, GAP Program

Columns 2-6 are A056357, A056358, A056359, A056360, A056361.
Row sums are A084708.
Partial row sums include A000011, A056353, A056354, A056355, A056356.
Cf. A081720, A273891, A008277 (set partitions), A284949 (up to reflection), A152175 (up to rotation).

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]];
Ach[n_, k_] := Ach[n, k] = Switch[k, 0, If[0==n, 1, 0], 1, If[n>0, 1, 0],
  (* else *) _, If[OddQ[n], Sum[Binomial[(n-1)/2, i] Ach[n-1-2i, k-1],
  {i, 0, (n-1)/2}], Sum[Binomial[n/2-1, i] (Ach[n-2-2i, k-1]
  + 2^i Ach[n-2-2i, k-2]), {i, 0, n/2-1}]]] (* achiral loops of length n, k colors *)
Table[(CoefficientList[DivisorSum[n, EulerPhi[#] Adn[#, n/#] &]/(x n), x]
+ Table[Ach[n, k],{k,1,n}])/2, {n, 1, 20}] // Flatten (* Robert A. Russell, Feb 24 2018 *)

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

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

A084708 Number of set partitions up to rotations and reflections.

Original entry on oeis.org

1, 2, 3, 7, 12, 37, 93, 354, 1350, 6351, 31950, 179307, 1071265, 6845581, 46162583, 327731950, 2437753740, 18948599220, 153498350745, 1293123243928, 11306475314467, 102425554299516, 959826755336242, 9290811905391501

Offset: 1

Wouter Meeussen, Jul 02 2003

nonn

Combines the symmetry operations of A080107 and A084423.

Equivalently, number of n-bead bracelets using any number of unlabeled (interchangable) colors. - Andrew Howroyd, Sep 25 2017

			SetPartitions[6] is the first to decompose differently from A084423: 4 cycles of length 1, 2 of 2, 9 of 3, 16 of 6, 6 of 12.
a(7) = 1 + A056357(7) + A056358(7) + A056359(7) + A056360(7) + A056361(7) + 1 = 1 + 8 + 31 + 33 + 16 + 3 + 1 = 93.

Michael De Vlieger, Table of n, a(n) for n = 1..577
Colin Adams, Chaim Even-Zohar, Jonah Greenberg, Reuben Kaufman, David Lee, Darin Li, Dustin Ping, Theodore Sandstrom, and Xiwen Wang, Virtual Multicrossings and Petal Diagrams for Virtual Knots and Links, arXiv:2103.08314 [math.GT], 2021.
Tilman Piesk, Partition related number triangles
N. J. A. Sloane, Generating functions [From _Wouter Meeussen_, Dec 06 2008]

Cf. A080107, A084423, A080510, A002872, A002874, A141003, A036075, A141004, A036077, A152176.

<A080107 *); Table[{Length[ # ], First[ # ]}&/@ Split[Sort[Length/@Split[Sort[First[Sort[Flatten[ {#, Map[Sort, (#/. i_Integer:>w+1-i), 2]}& @(NestList[Sort[Sort/@(#/. i_Integer :> Mod[i+1, w, 1])]&, #, w]), 1]]]&/@SetPartitions[w]]]]], {w, 1, 10}]
u[0,j_]:=1;u[k_,j_]:=u[k,j]=Sum[Binomial[k-1,i-1]Plus@@(u[k-i,j]#^(i-1)&/@Divisors[j]),{i,k}]; a[n_]:=1/n*Plus@@(EulerPhi[ # ]u[Quotient[n,# ],# ]&/@Divisors[n]); Table[a[n]/2+If[EvenQ[n],u[n/2,2],Sum[Binomial[n/2-1/2,k] u[k,2], {k,0,n/2-1/2}]]/2,{n,40}] (* Wouter Meeussen, Dec 06 2008 *)

a(n) = (A080107(n)+A084423(n))/2. - Wouter Meeussen and Vladeta Jovovic, Nov 28 2008

a(12) from Vladeta Jovovic, Jul 15 2007

More terms from Vladeta Jovovic's formula given in Mathematica line. - Wouter Meeussen, Dec 06 2008

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

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 9, 125, 1054, 7928, 54383, 356594, 2259504, 14008733, 85422360, 514773336, 3074341497, 18238301412, 107649939612, 632987843336, 3711471738408, 21716706883190, 126879832615600, 740528154956264, 4319137675225128, 25181504728152534, 146788320134425736, 855660631677225738, 4988501691655508510, 29089896998939710698

Offset: 1

Robert A. Russell, Oct 19 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 A056299 and A304976, which can be used in conjunction with the first formula.

			For a(8)=9, the chiral pairs are AABACDEF-AABCDEAF, AABCADEF-AABCDAEF, AABCBDEF-AABCDEFE, AABCDBEF-AABCDEFD, AABCDEBF-AABCDEFC, AABCDCEF-AABCDEDF, ABACDEBF-ABACDEBF, ABCADBEF-ABCADECF, and ABCDAEBF-ABCADBEF.

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

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

a(n) = (A056299(n) - A304976(n)) / 2 = A056299(n) - A056361(n) = A056361(n) - A304976(n).

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

A292223 a(n) is the number of representative six-color bracelets (necklaces with turning over allowed; D_6 symmetry) with n beads, for n >= 6.

Original entry on oeis.org

60, 180, 1050, 5040, 29244, 161340, 1046250, 4825800, 27790266, 145126548, 843333015, 4466836920, 26967624184, 137243187108, 789854179074, 4306147750200, 24711052977222, 134216193832908, 797987818325009, 4240082199867228

Offset: 6

Wolfdieter Lang, Sep 30 2017

nonn

This is the sixth column (m = 6) of triangle A213940.
The relevant p(n,6)= A008284(n, 6) representative color multinomials have exponents (signatures) from the six-part partitions of n, written with nonincreasing parts. E.g., n = 8: [3,1,1,1,1,1] and [2,2,1,1,1,1] (p(8,6)=2). The corresponding representative bracelets have the six-color multinomials c[1]^3*c[2]*c[3]*c[4]*c[5]*c[6] and c[1]^2*c[2]^2*c[3]*c[4]*c[5]*c[6].
See A056361 for the numbers if also color permutations for D_6 inequivalent bracelets are allowed. (Andrew Howroyd induced me to look at these bracelets.)

			a(6) = A213940(6,6) = A213939(6, 11) = 60 from the representative bracelets (with colors j for c(j), j=1..6) permutations of (1, 2, 3, 4, 5, 6) modulo D_6 (dihedral group) symmetry, i.e., modulo cyclic or anti-cyclic operations. E.g., (1, 2, 3, 4, 6, 5) == (2, 3, 4, 6, 5, 1) == (6, 4, 3, 2, 1, 5) == ..., but (1, 2, 3, 4, 6, 5) is not equivalent to (1, 2, 3, 4, 5, 6). If color permutation is also allowed, then there is only one possibility (see A056361(6) = 1).

Cf. A008284, A036036, A056361, A213940, A214311, A214314.

a(n) = A213940(n, 6), n >= 6.

a(n) = Sum_{k=b(n, 6)..b(n, 7)-1} A213939(n, k), for n >= 7, with b(n, m) = A214314(n, m) the position where the first m-part partition of n appears in the Abramowitz-Stegun ordering of partitions (see A036036 for the reference and a historical comment), and a(6) = A213939(6, b(6,6)) = A213939(6, 11) = 60.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

A084708 Number of set partitions up to rotations and reflections.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A292223 a(n) is the number of representative six-color bracelets (necklaces with turning over allowed; D_6 symmetry) with n beads, for n >= 6.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula