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.

1, 1, 3, 1, 4, 11, 1, 6, 24, 70, 1, 8, 51, 208, 629, 1, 14, 130, 700, 2635, 7826, 1, 20, 315, 2344, 11165, 39996, 117655, 1, 36, 834, 8230, 48915, 210126, 720916, 2097684, 1, 60, 2195, 29144, 217045, 1119796, 4483815, 14913200, 43046889

Offset: 1

Author

N. J. A. Sloane, Apr 16 2000, revised Mar 21 2007

Keywords

• nonn
• tabl

Comments

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

Examples

			1;
1,  3;                                   (A000217)
1,  4,  11;                              (A006527)
1,  6,  24,   70;                        (A006528)
1,  8,  51,  208,   629;                 (A054620)
1, 14, 130,  700,  2635,  7826;          (A006565)
1, 20, 315, 2344, 11165, 39996, 117655;  (A054621)
		

Links

• Seiichi Manyama, Rows n = 1..140, flattened
• Wikipedia, Necklace (combinatorics)
• Index entries for sequences related to necklaces

Crossrefs

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

Programs

Maple

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

Mathematica

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

PARI

T(n, k) = sumdiv(n, d, eulerphi(d)*k^(n/d))/n; \\ Seiichi Manyama, Mar 10 2021

PARI

T(n, k) = sum(j=1, n, k^gcd(j, n))/n; \\ Seiichi Manyama, Mar 10 2021

Formula

T(n,k) = Sum_{j=1..k} binomial(k,j) * A087854(n, j). - Yves-Loic Martin, Sep 29 2020

T(n,k) = (1/n) * Sum_{j=1..n} k^gcd(j, n). - Seiichi Manyama, Mar 10 2021