cp's OEIS Frontend

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

%I A054631 #52 Mar 10 2021 11:23:02
%S A054631 1,1,3,1,4,11,1,6,24,70,1,8,51,208,629,1,14,130,700,2635,7826,1,20,
%T A054631 315,2344,11165,39996,117655,1,36,834,8230,48915,210126,720916,
%U A054631 2097684,1,60,2195,29144,217045,1119796,4483815,14913200,43046889
%N A054631 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 A054631 T(n,k) is the number of n-bead necklaces with up to k different colored beads. - _Yves-Loic Martin_, Sep 29 2020
%H A054631 Seiichi Manyama, <a href="/A054631/b054631.txt">Rows n = 1..140, flattened</a>
%H A054631 Wikipedia, <a href="https://en.wikipedia.org/wiki/Necklace_(combinatorics)">Necklace (combinatorics)</a>
%H A054631 <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%F A054631 T(n,k) = Sum_{j=1..k} binomial(k,j) * A087854(n, j). - _Yves-Loic Martin_, Sep 29 2020
%F A054631 T(n,k) = (1/n) * Sum_{j=1..n} k^gcd(j, n). - _Seiichi Manyama_, Mar 10 2021
%e A054631 1;
%e A054631 1,  3;                                   (A000217)
%e A054631 1,  4,  11;                              (A006527)
%e A054631 1,  6,  24,   70;                        (A006528)
%e A054631 1,  8,  51,  208,   629;                 (A054620)
%e A054631 1, 14, 130,  700,  2635,  7826;          (A006565)
%e A054631 1, 20, 315, 2344, 11165, 39996, 117655;  (A054621)
%p A054631 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 A054631 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 A054631 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 A054631 (PARI) T(n, k) = sumdiv(n, d, eulerphi(d)*k^(n/d))/n; \\ _Seiichi Manyama_, Mar 10 2021
%o A054631 (PARI) T(n, k) = sum(j=1, n, k^gcd(j, n))/n; \\ _Seiichi Manyama_, Mar 10 2021
%Y A054631 Cf. A054630, A054618, A054619, A087854. Lower triangle of A075195.
%K A054631 nonn,tabl
%O A054631 1,3
%A A054631 _N. J. A. Sloane_, Apr 16 2000, revised Mar 21 2007