login
A319082
A(n, k) = (1/k)*Sum_{d|k} EulerPhi(d)*n^(k/d) for n >= 0 and k > 0, A(n, 0) = 0, square array read by ascending antidiagonals.
2
0, 0, 0, 0, 1, 0, 0, 2, 1, 0, 0, 3, 3, 1, 0, 0, 4, 6, 4, 1, 0, 0, 5, 10, 11, 6, 1, 0, 0, 6, 15, 24, 24, 8, 1, 0, 0, 7, 21, 45, 70, 51, 14, 1, 0, 0, 8, 28, 76, 165, 208, 130, 20, 1, 0, 0, 9, 36, 119, 336, 629, 700, 315, 36, 1, 0, 0, 10, 45, 176, 616, 1560, 2635, 2344, 834, 60, 1, 0, 0, 11, 55, 249, 1044, 3367, 7826, 11165, 8230, 2195, 108, 1, 0
OFFSET
0,8
REFERENCES
D. E. Knuth, Generating All Tuples and Permutations. The Art of Computer Programming, Vol. 4, Fascicle 2, Addison-Wesley, 2005.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals)
H. Fredricksen and I. J. Kessler, An algorithm for generating necklaces of beads in two colors, Discrete Math. 61 (1986), 181-188.
H. Fredricksen and J. Maiorana, Necklaces of beads in k colors and k-ary de Bruijn sequences, Discrete Math. 23(3) (1978), 207-210. Reviewed in MR0523071 (80e:05007).
F. Ruskey, C. Savage, and T. M. Y. Wang, Generating necklaces, Journal of Algorithms, 13(3), 1992, 414-430.
FORMULA
A(n, k) = (1/k)*Sum_{i=1..k} n^gcd(i, k) for k > 0.
EXAMPLE
Array starts:
[n\k][0 1 2 3 4 5 6 7 8 9 ...]
[0] 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
[1] 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
[2] 0, 2, 3, 4, 6, 8, 14, 20, 36, 60, ...
[3] 0, 3, 6, 11, 24, 51, 130, 315, 834, 2195, ...
[4] 0, 4, 10, 24, 70, 208, 700, 2344, 8230, 29144, ...
[5] 0, 5, 15, 45, 165, 629, 2635, 11165, 48915, 217045, ...
[6] 0, 6, 21, 76, 336, 1560, 7826, 39996, 210126, 1119796, ...
[7] 0, 7, 28, 119, 616, 3367, 19684, 117655, 720916, 4483815, ...
MAPLE
with(numtheory):
A := (n, k) -> `if`(k=0, 0, (1/k)*add(phi(d)*n^(k/d), d=divisors(k))):
seq(seq(A(n-k, k), k=0..n), n=0..12);
# Alternatively, row-wise printed as a table:
T := (n, k) -> `if`(k=0, 0, add(n^igcd(i, k), i=1..k)/k):
seq(lprint(seq(T(n, k), k=0..9)), n=0..7);
PROG
(Sage)
def A319082(n, k):
return 0 if k == 0 else (1/k)*sum(euler_phi(d)*n^(k//d) for d in divisors(k))
for n in (0..7):
print([n], [A319082(n, k) for k in (0..9)])
(PARI) A(n, k)=if(k==0, 0, sumdiv(k, d, eulerphi(d)*n^(k/d))/k) \\ Andrew Howroyd, Jan 05 2024
CROSSREFS
Essentially the same table as A075195.
A185651(n, k) = n*A(k, n).
Main diagonal gives A056665.
A054630(n,k) is a subtriangle for n >= 1 and 1 <= k <= n.
Sequence in context: A106237 A071675 A221833 * A034365 A103778 A099423
KEYWORD
nonn,tabl
AUTHOR
Peter Luschny, Sep 10 2018
STATUS
approved