login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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.
7
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,3
COMMENTS
T(n,k) is the number of n-bead necklaces with up to k different colored beads. - Yves-Loic Martin, Sep 29 2020
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
EXAMPLE
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)
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 *)
PROG
(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
CROSSREFS
Cf. A054630, A054618, A054619, A087854. Lower triangle of A075195.
Sequence in context: A301701 A262078 A121922 * A180063 A125077 A065253
KEYWORD
nonn,tabl
AUTHOR
N. J. A. Sloane, Apr 16 2000, revised Mar 21 2007
STATUS
approved