%I #64 Sep 25 2020 05:10:00
%S 1,1,1,1,2,2,1,4,9,6,1,6,30,48,24,1,12,91,260,300,120,1,18,258,1200,
%T 2400,2160,720,1,34,729,5106,15750,23940,17640,5040,1,58,2018,20720,
%U 92680,211680,258720,161280,40320,1,106,5613,81876,510312,1643544,2963520,3024000,1632960,362880
%N Triangle read by rows: T(n,k) is the number of n-bead necklaces with exactly k different colored beads.
%C Equivalently, T(n,k) is the number of sequences (words) of length n on an alphabet of k letters where each letter of the alphabet occurs at least once in the sequence. Two sequences are considered equivalent if one can be obtained from the other by a cyclic shift of the letters. Cf. A054631 where the surjective restriction is removed. - _Geoffrey Critzer_, Jun 18 2013
%C _Robert A. Russell_'s g.f. for column k >= 1 (in the Formula section below) can be proved by integrating both sides of the formula Sum_{n>=1} S2(n, k)*x^(n-1) = x^(k-1)/((1 - x)* (1 - 2*x) * (1 - 3*x) * ... * (1 - k*x)) w.r.t. x. A variation of this identity (valid for |x| < 1/k) can be found in the Formula section of A008277. - _Petros Hadjicostas_, Aug 20 2019
%H Alois P. Heinz, <a href="/A087854/b087854.txt">Rows n = 1..141, flattened</a>
%F T(n,k) = Sum_{i=0..k-1} (-1)^i * C(k,i) * A075195(n,k-i); A075195 = Jablonski's table.
%F T(n,k) = (k!/n) * Sum_{d|n} phi(d) * S2(n/d, k), where S2(n,k) = Stirling numbers of 2nd kind A008277.
%F G.f. for column k: -Sum_{d>0} (phi(d)/d) * Sum_{j = 1..k} (-1)^(k-j) * C(k,j) * log(1 - j * x^d). - _Robert A. Russell_, Sep 26 2018
%F T(n,k) = Sum_{d|n} A254040(d, k) for n, k >= 1. - _Petros Hadjicostas_, Aug 19 2019
%e The triangle begins with T(1,1):
%e 1;
%e 1, 1;
%e 1, 2, 2;
%e 1, 4, 9, 6;
%e 1, 6, 30, 48, 24;
%e 1, 12, 91, 260, 300, 120;
%e 1, 18, 258, 1200, 2400, 2160, 720;
%e 1, 34, 729, 5106, 15750, 23940, 17640, 5040;
%e 1, 58, 2018, 20720, 92680, 211680, 258720, 161280, 40320;
%e 1, 106, 5613, 81876, 510312, 1643544, 2963520, 3024000, 1632960, 362880;
%e ...
%e For T(4,2) = 4, the necklaces are AAAB, AABB, ABAB, and ABBB.
%e For T(4,4) = 6, the necklaces are ABCD, ABDC, ACBD, ACDB, ADBC, and ADCB.
%p with(numtheory):
%p T:= (n, k)-> (k!/n) *add(phi(d) *Stirling2(n/d, k), d=divisors(n)):
%p seq(seq(T(n,k), k=1..n), n=1..12); # _Alois P. Heinz_, Jun 19 2013
%t Table[Table[Sum[EulerPhi[d]*StirlingS2[n/d,k]k!,{d,Divisors[n]}]/n,{k,1,n}],{n,1,10}]//Grid (* _Geoffrey Critzer_, Jun 18 2013 *)
%o (PARI) T(n, k) = (k!/n) * sumdiv(n, d, eulerphi(d) * stirling(n/d, k, 2)); \\ _Joerg Arndt_, Sep 25 2020
%Y Columns 1-6: A057427, A052823, A056283, A056284, A056285, A056286.
%Y Diagonals: A000142 and A074143.
%Y Row sums: A019536.
%Y Cf. A000010 (Euler totient phi function), A008277 (Stirling2 numbers), A075195 (table of Jablonski).
%Y Cf. A254040, A273891.
%K nonn,tabl,easy
%O 1,5
%A _Philippe Deléham_
%E Formula section edited by _Petros Hadjicostas_, Aug 20 2019