%I #52 Mar 10 2021 11:23:02

%S 1,1,3,1,4,11,1,6,24,70,1,8,51,208,629,1,14,130,700,2635,7826,1,20,

%T 315,2344,11165,39996,117655,1,36,834,8230,48915,210126,720916,

%U 2097684,1,60,2195,29144,217045,1119796,4483815,14913200,43046889

%N Triangle read by rows: row n (n >= 1) contains the numbers T(n,k) = Sum_{d|n} phi(d)*k^(n/d)/n, for k=1..n.

%C T(n,k) is the number of n-bead necklaces with up to k different colored beads. - _Yves-Loic Martin_, Sep 29 2020

%H Seiichi Manyama, <a href="/A054631/b054631.txt">Rows n = 1..140, flattened</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Necklace_(combinatorics)">Necklace (combinatorics)</a>

%H <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>

%F T(n,k) = Sum_{j=1..k} binomial(k,j) * A087854(n, j). - _Yves-Loic Martin_, Sep 29 2020

%F T(n,k) = (1/n) * Sum_{j=1..n} k^gcd(j, n). - _Seiichi Manyama_, Mar 10 2021

%e 1;

%e 1, 3; (A000217)

%e 1, 4, 11; (A006527)

%e 1, 6, 24, 70; (A006528)

%e 1, 8, 51, 208, 629; (A054620)

%e 1, 14, 130, 700, 2635, 7826; (A006565)

%e 1, 20, 315, 2344, 11165, 39996, 117655; (A054621)

%p A054631 := proc(n,k) add( numtheory[phi](d)*k^(n/d),d=numtheory[divisors](n) ) ; %/n ; end proc: # _R. J. Mathar_, Aug 30 2011

%t Needs["Combinatorica`"]; Table[Table[NumberOfNecklaces[n, k, Cyclic], {k, 1, n}], {n, 1, 8}] //Grid (* _Geoffrey Critzer_, Oct 07 2012, after code by _T. D. Noe_ in A027671 *)

%t t[n_, k_] := Sum[EulerPhi[d]*k^(n/d)/n, {d, Divisors[n]}]; Table[t[n, k], {n, 1, 9}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Jan 20 2014 *)

%o (PARI) T(n, k) = sumdiv(n, d, eulerphi(d)*k^(n/d))/n; \\ _Seiichi Manyama_, Mar 10 2021

%o (PARI) T(n, k) = sum(j=1, n, k^gcd(j, n))/n; \\ _Seiichi Manyama_, Mar 10 2021

%Y Cf. A054630, A054618, A054619, A087854. Lower triangle of A075195.

%K nonn,tabl

%O 1,3

%A _N. J. A. Sloane_, Apr 16 2000, revised Mar 21 2007