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

Author

Vladeta Jovovic, Nov 27 2008

Keywords

• nonn
• tabl

Comments

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

Examples

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

References

• 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]

Links

• 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

Crossrefs

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

Programs

Mathematica

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

PARI

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

PARI

\\ 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