|
%I #48 Sep 20 2019 19:35:01
%S 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,
%T 126,221,136,36,4,1,1,29,339,866,773,296,52,4,1,1,55,946,3437,4281,
%U 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
%N Triangle read by rows: T(n,k) is the number of k-block partitions of an n-set up to rotations.
%C 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
%D 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]
%H Andrew Howroyd, <a href="/A152175/b152175.txt">Table of n, a(n) for n = 1..1275</a>
%H E. N. Gilbert and J. Riordan, <a href="http://projecteuclid.org/euclid.ijm/1255631587">Symmetry types of periodic sequences</a>, Illinois J. Math., 5 (1961), 657-665.
%H Tilman Piesk, <a href="http://en.wikiversity.org/wiki/Partition_related_number_triangles#rot">Partition related number triangles</a>
%F 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
%e Triangle begins with T(1,1):
%e 1;
%e 1, 1;
%e 1, 1, 1;
%e 1, 3, 2, 1;
%e 1, 3, 5, 2, 1;
%e 1, 7, 18, 13, 3, 1;
%e 1, 9, 43, 50, 20, 3, 1;
%e 1, 19, 126, 221, 136, 36, 4, 1;
%e 1, 29, 339, 866, 773, 296, 52, 4, 1;
%e 1, 55, 946, 3437, 4281, 2303, 596, 78, 5, 1;
%e 1, 93, 2591, 13250, 22430, 16317, 5817, 1080, 105 , 5, 1;
%e 1, 179, 7254, 51075, 115100, 110462, 52376, 13299, 1873, 147, 6, 1;
%e 1, 315, 20125, 194810, 577577, 717024, 439648, 146124, 27654, 3025, 187, 6, 1;
%e ...
%e For T(4,2)=3, the set partitions are AAAB, AABB, and ABAB.
%e For T(4,3)=2, the set partitions are AABC and ABAC.
%t (* Using recursion formula from Gilbert and Riordan:*)
%t Adn[d_, n_] := Adn[d, n] = Which[0==n, 1, 1==n, DivisorSum[d, x^# &],
%t 1==d, Sum[StirlingS2[n, k] x^k, {k, 0, n}],
%t True, Expand[Adn[d, 1] Adn[d, n-1] + D[Adn[d, n - 1], x] x]];
%t Table[CoefficientList[DivisorSum[n, EulerPhi[#] Adn[#, n/#] &]/(x n), x],
%t {n, 1, 10}] // Flatten (* _Robert A. Russell_, Feb 23 2018 *)
%t 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]]
%t Table[DivisorSum[n,EulerPhi[#]Adnk[#,n/#,k]&]/n,{n,1,12},{k,1,n}] // Flatten (* _Robert A. Russell_, Oct 16 2018 *)
%o (PARI) \\ see A056391 for Polya enumeration functions
%o T(n,k) = NonequivalentStructsExactly(CyclicPerms(n), k); \\ _Andrew Howroyd_, Oct 14 2017
%o (PARI)
%o 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))]))}
%o { my(A=R(12)); for(n=1, #A, print(A[n, 1..n])) } \\ _Andrew Howroyd_, Sep 20 2019
%Y Columns 2-6 are A056295, A056296, A056297, A056298, A056299.
%Y Row sums are A084423.
%Y Partial row sums include A000013, A002076, A056292, A056293, A056294.
%Y Cf. A075195, A087854, A008277 (set partitions), A284949 (up to reflection), A152176 (up to rotation and reflection).
%Y A(1,n,k) in formula is the Stirling subset number A008277.
%Y A(2,n,k) in formula is A293181; A(3,n,k) in formula is A294201.
%K nonn,tabl,easy
%O 1,8
%A _Vladeta Jovovic_, Nov 27 2008
|
