A054630 -id:A054630 - cp's OEIS frontend

A075195 Jablonski table T(n,k) read by antidiagonals: T(n,k) = number of necklaces with n beads of k colors.

1, 2, 1, 3, 3, 1, 4, 6, 4, 1, 5, 10, 11, 6, 1, 6, 15, 24, 24, 8, 1, 7, 21, 45, 70, 51, 14, 1, 8, 28, 76, 165, 208, 130, 20, 1, 9, 36, 119, 336, 629, 700, 315, 36, 1, 10, 45, 176, 616, 1560, 2635, 2344, 834, 60, 1, 11, 55, 249, 1044, 3367, 7826, 11165, 8230, 2195, 108, 1

Offset: 1

Christian G. Bower, Sep 07 2002

From Richard L. Ollerton, May 07 2021: (Start)
Here, as in A000031, turning over is not allowed.
(1/n) * Dirichlet convolution of phi(n) and k^n. (End)

			The array T(n,k) for n >= 1, k >= 1 begins:
  1,  2,   3,    4,     5,     6,      7, ...
  1,  3,   6,   10,    15,    21,     28, ...
  1,  4,  11,   24,    45,    76,    119, ...
  1,  6,  24,   70,   165,   336,    616, ...
  1,  8,  51,  208,   629,  1560,   3367, ...
  1, 14, 130,  700,  2635,  7826,  19684, ...
  1, 20, 315, 2344, 11165, 39996, 117655, ...
From _Indranil Ghosh_, Mar 25 2017: (Start)
Triangle formed when the array is read by antidiagonals:
   1;
   2,  1;
   3,  3,   1;
   4,  6,   4,   1;
   5, 10,  11,   6,    1;
   6, 15,  24,  24,    8,    1;
   7, 21,  45,  70,   51,   14,    1;
   8, 28,  76, 165,  208,  130,   20,   1;
   9, 36, 119, 336,  629,  700,  315,  36,  1;
  10, 45, 176, 616, 1560, 2635, 2344, 834, 60, 1;
  ... (End)

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 86 (2.2.23).
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 496.
Louis Comtet, Analyse combinatoire, Tome 2, p. 104 #17, P.U.F., 1970.

Andrew Howroyd, Table of n, a(n) for n = 1..1275
E. Jablonski, Théorie des permutations et des arrangements complets, Journal de Liouville, 8 (1892), pp. 331-49.
E. Jablonski, Sur l'analyse combinatoire circulaire, Comptes-rendus de l'Académie des Sciences, April 11 1892, Paris.
E. Lucas, Sur les permutations circulaires avec répétition, Théorie des Nombres, Annexe VII, Gauthier-Villars, Paris, 1891. Mentions Moreau.
P. A. MacMahon, Application of a theory of permutations in circular procession to the theory of numbers, Proc. Lond. Math. Soc., 23 (1892), pp. 305-313. Mentions Jablonski, Lucas and Moreau.
Index entries for sequences related to necklaces

Columns 1-10: A000012, A000031, A001867, A001868, A001869, A054625-A054629.
Rows 1-10: A000027, A000217, A006527, A006528, A054620, A006565, A054621-A054624.
Main Diagonal: A056665. A054630 and A054631 are the upper and lower triangles.
Cf. A000010, A185651, A246935.

t[n_, k_] := (1/n)*Sum[EulerPhi[d]*k^(n/d), {d, Divisors[n]}]; Table[t[n-k+1, k], {n, 1, 11}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Jan 20 2014, after Philippe Deléham *)

T(n, k) = (1/n) * sumdiv(n, d, eulerphi(d)*k^(n/d));
for(n=1, 15, for(k=1, n, print1(T(k, n - k + 1),", ");); print();) \\ Indranil Ghosh, Mar 25 2017

from sympy.ntheory import totient, divisors
def T(n,k): return sum(totient(d)*k**(n//d) for d in divisors(n))//n
for n in range(1, 16):
    print([T(k, n - k + 1) for k in range(1, n + 1)]) # Indranil Ghosh, Mar 25 2017

T(n,k) = (1/n)*Sum_{d | n} phi(d)*k^(n/d), where phi = Euler totient function A000010. - Philippe Deléham, Oct 08 2003
From Petros Hadjicostas, Feb 08 2021: (Start)
O.g.f. for column k >= 1: Sum_{n>=1} T(n,k)*x^n = -Sum_{j >= 1} (phi(j)/j) * log(1 - k*x^j).
Linear recurrence for row n >= 1: T(n,k) = Sum_{j=0..n} -binomial(j-n-1,j+1) * T(n,k-1-j) for k >= n + 2. (This recurrence is essentially due to Robert A. Russell, who contributed it in A321791.) (End)
From Richard L. Ollerton, May 07 2021: (Start)
T(n,k) = (1/n)*Sum_{i=1..n} k^gcd(n,i).
T(n,k) = (1/n)*Sum_{i=1..n} k^(n/gcd(n,i))*phi(gcd(n,i))/phi(n/gcd(n,i)).
T(n,k) = (1/n)*A185651(n,k) for n >= 1, k >= 1. (End)
Product_{n>=1} 1/(1 - x^n)^T(n,k) = Product_{n>=1} 1/(1 - k*x^n). - Seiichi Manyama, Apr 12 2025

Additional references from Philippe Deléham, Oct 08 2003

A056665 Number of equivalence classes of n-valued Post functions of 1 variable under action of complementing group C(1,n).

Original entry on oeis.org

1, 3, 11, 70, 629, 7826, 117655, 2097684, 43046889, 1000010044, 25937424611, 743008623292, 23298085122493, 793714780783770, 29192926025492783, 1152921504875290696, 48661191875666868497, 2185911559749720272442, 104127350297911241532859

Offset: 1

Vladeta Jovovic, Aug 09 2000

Diagonal of arrays defined in A054630 and A054631.
Given n colors, a(n) = number of necklaces with n beads and 1 up to n colors effectively assigned to them (super_labeled: which also generates n different monochrome necklaces). - Wouter Meeussen, Aug 09 2002
Number of endofunctions on a set with n objects up to cyclic permutation (rotation). E.g., for n = 3, the 11 endofunctions are 1,1,1; 2,2,2; 3,3,3; 1,1,2; 1,2,2; 1,1,3; 1,3,3; 2,2,3; 2,3,3; 1,2,3; and 1,3,2. - Franklin T. Adams-Watters, Jan 17 2007
Also number of pre-necklaces in Sigma(n,n) (see Ruskey and others). - Peter Luschny, Aug 12 2012
From Olivier Gérard, Aug 01 2016: (Start)
Decomposition of the endofunctions by class size.
.
  n |  1   2   3   4    5     6       7
  --+----------------------------------
  1 |  1
  2 |  2   1
  3 |  3   0   8
  4 |  4   6   0  60
  5 |  5   0   0   0  624
  6 |  6  15  70   0    0  7735
  7 |  7   0   0   0    0     0  117648
.
The right diagonal gives the number of Lyndon Words or aperiodic necklaces, A075147. By multiplying each column by the corresponding size and summing, one gets A000312.
(End)

			The 11 necklaces for n=3 are (grouped by partition of 3): (RRR,GGG,BBB),(RRG,RGG, RRB,RBB, GGB,GBB), (RGB,RBG).

D. E. Knuth. Generating All Tuples and Permutations. The Art of Computer Programming, Vol. 4, Fascicle 2, 7.2.1.1. Addison-Wesley, 2005.

Alois P. Heinz, Table of n, a(n) for n = 1..200
M. A. Harrison and R. G. High, On the cycle index of a product of permutation groups, J. Combin. Theory, 4 (1968), 277-299.
F. Ruskey, C. Savage, and T. M. Y. Wang, Generating necklaces, Journal of Algorithms, 13(3), 414 - 430, 1992.
Index entries for sequences related to groups

Cf. A001323, A001324, A001372, A000312.
Diagonal of arrays defined in A054630, A054631 and A075195.
Cf. A075147 Aperiodic necklaces, a subset of this sequence.
Cf. A000169 Classes under translation mod n
Cf. A168658 Classes under complement to n+1
Cf. A130293 Classes under translation and rotation
Cf. A081721 Classes under rotation and reversal
Cf. A275549 Classes under reversal
Cf. A275550 Classes under reversal and complement
Cf. A275551 Classes under translation and reversal
Cf. A275552 Classes under translation and complement
Cf. A275553 Classes under translation, complement and reversal
Cf. A275554 Classes under translation, rotation and complement
Cf. A275555 Classes under translation, rotation and reversal
Cf. A275556 Classes under translation, rotation, complement and reversal
Cf. A275557 Classes under rotation and complement
Cf. A275558 Classes under rotation, complement and reversal
Cf. A228640.

with(numtheory):
a:= n-> add(phi(d)*n^(n/d), d=divisors(n))/n:
seq(a(n), n=1..25);  # Alois P. Heinz, Jun 18 2013

Table[Fold[ #1+EulerPhi[ #2] n^(n/#2)&, 0, Divisors[n]]/n, {n, 7}]

a(n) = sum(k=1,n,n^gcd(k,n)) / n; \\ Joerg Arndt, Mar 19 2017

# This algorithm counts all n-ary n-tuples (a_1,..,a_n) such that the string a_1...a_n is preprime. It is algorithm F in Knuth 7.2.1.1.
def A056665_list(n):
    C = []
    for m in (1..n):
        a = [0]*(n+1); a[0]=-1;
        j = 1; count = 0
        while(true):
            if m%j == 0 : count += 1;
            j = n
            while a[j] >= m-1 : j -= 1
            if j == 0 : break
            a[j] += 1
            for k in (j+1..n): a[k] = a[k-j]
        C.append(count)
    return C

def A056665(n): return sum(euler_phi(d)*n^(n//d)//n for d in divisors(n))
[A056665(n) for n in (1..18)] # Peter Luschny, Aug 12 2012

a(n) = Sum_{d|n} phi(d)*n^(n/d)/n.
a(n) ~ n^(n-1). - Vaclav Kotesovec, Sep 11 2014
a(n) = (1/n) * Sum_{k=1..n} n^gcd(k,n). - Joerg Arndt, Mar 19 2017
a(n) = [x^n] -Sum_{k>=1} phi(k)*log(1 - n*x^k)/k. - Ilya Gutkovskiy, Mar 21 2018
From Richard L. Ollerton, May 07 2021: (Start)
a(n) = (1/n)*Sum_{k=1..n} n^(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)).
a(n) = (1/n)*A228640(n). (End)

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.

Original entry on oeis.org

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

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

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

			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)

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

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

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

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

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

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

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

A215474 Triangle read by rows: number of k-ary n-tuples (a_1,..,a_n) such that the string a_1...a_n is preprime.

Original entry on oeis.org

1, 1, 3, 1, 5, 14, 1, 8, 32, 90, 1, 14, 80, 294, 829, 1, 23, 196, 964, 3409, 9695, 1, 41, 508, 3304, 14569, 49685, 141280, 1, 71, 1318, 11464, 63319, 259475, 861580, 2447592, 1, 127, 3502, 40584, 280319, 1379195, 5345276, 17360616, 49212093, 1, 226, 9382

Offset: 1

Peter Luschny, Aug 12 2012

A string is prime if it is nonempty and lexicographically less than all of its proper suffixes. A string is preprime if it is a nonempty prefix of a prime, on some alphabet. See the Knuth reference, section 7.2.1.1.

			T(4, 3) counts the 32 ternary preprimes of length 4 which are:
0000,0001,0002,0010,0011,0012,0020,0021,0022,0101,0102,
0110,0111,0112,0120,0121,0122,0202,0210,0211,0212,0220,
0221,0222,1111,1112,1121,1122,1212,1221,1222,2222.
Triangle starts (compare the table A143328 as a square array):
[1]
[1,  3]
[1,  5,  14]
[1,  8,  32,   90]
[1, 14,  80,  294,   829]
[1, 23, 196,  964,  3409,  9695]
[1, 41, 508, 3304, 14569, 49685, 141280]

D. E. Knuth. Generating All Tuples and Permutations. The Art of Computer Programming, Vol. 4, Fascicle 2, Addison-Wesley, 2005.

Alois P. Heinz, Rows n = 1..141, flattened

Cf. A056665, A054630, A143328, A215475.

# From Alois P. Heinz A143328.
with(numtheory):
f0 := proc(n) option remember; unapply(k^n-add(f0(d)(k),d=divisors(n) minus{n}),k) end;
f2 := proc(n) option remember; unapply(f0(n)(x)/n,x) end;
g2 := proc(n) option remember; unapply(add(f2(j)(x),j=1..n),x) end;
A215474 := (n, k) -> g2(n)(k);
seq(print(seq(A215474(n,d),d=1..n)),n=1..8);

t[n_, k_] := Sum[(1/j)*MoebiusMu[j/d]*k^d, {j, 1, n}, {d, Divisors[j]}]; Table[t[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jul 26 2013 *)

# This algorithm generates and counts all k-ary n-tuples
# (a_1,..,a_n) such that the string a_1...a_n is preprime.
# It is algorithm F in Knuth 7.2.1.1.
def A215474_count(n, k):
    a = [0]*(n+1); a[0]=-1
    j = 1; count = 0
    while True:
        count += 1;
        j = n
        while a[j] >= k-1 : j -= 1
        if j == 0 : break
        a[j] += 1
        for i in (j+1..n): a[i] = a[i-j]
    return count
def A215474(n,k):
     return add((1/j)*add(moebius(j/d)*k^d for d in divisors(j))  for j in (1..n))
for n in (1..9): print([A215474(n,k) for k in (1..n)])

T(n,k) = Sum_{1<=j<=n} (1/j)*Sum_{d|j} mu(j/d)*k^d.

T(n,n) = A143328(n,n).

A054618 Triangle T(n,k) = Sum_{d|n} phi(d)*k^(n/d).

Original entry on oeis.org

1, 2, 6, 3, 12, 33, 4, 24, 96, 280, 5, 40, 255, 1040, 3145, 6, 84, 780, 4200, 15810, 46956, 7, 140, 2205, 16408, 78155, 279972, 823585, 8, 288, 6672, 65840, 391320, 1681008, 5767328, 16781472, 9, 540, 19755, 262296, 1953405, 10078164, 40354335, 134218800, 387422001

Offset: 1

N. J. A. Sloane, Apr 16 2000

Dirichlet convolution of A000010(n) and k^n. - Richard L. Ollerton, May 10 2021

			1;
2, 6;
3, 12, 33;
4, 24, 96,  280;
5, 40, 255, 1040, 3145;
6, 84, 780, 4200, 15810, 46956;
...

Alois P. Heinz, Rows n = 1..141, flattened

Cf. A054619, A054630, A054631.
Main diagonal gives: A228640.
Cf. A000010.

with(numtheory):
T:= (n, k)-> add(phi(d)*k^(n/d), d=divisors(n)):
seq(seq(T(n, k), k=1..n), n=1..10); # Alois P. Heinz, Aug 28 2013
A054618 := proc(n, k)
    add( numtheory[phi](d)*k^(n/d),d=numtheory[divisors](n)) ;
end proc:
seq(seq(A054618(n,k),k=1..n),n=1..10) ; # R. J. Mathar, Jan 23 2022

T[n_, k_] := Sum[EulerPhi[d]*k^(n/d), {d, Divisors[n]}]; Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Feb 25 2015 *)

T(n, k) = sumdiv(n, d, eulerphi(d)*k^(n/d)); \\ Michel Marcus, Feb 25 2015

From Richard L. Ollerton, May 10 2021: (Start)
T(n,k) = Sum_{i=1..n} k^gcd(n,i).
T(n,k) = Sum_{i=1..n} k^(n/gcd(n,i))*phi(gcd(n,i))/phi(n/gcd(n,i)). (End)

A054619 Triangle T(n,k) = Sum_{d|k} phi(d)*n^(k/d).

Original entry on oeis.org

1, 2, 6, 3, 12, 33, 4, 20, 72, 280, 5, 30, 135, 660, 3145, 6, 42, 228, 1344, 7800, 46956, 7, 56, 357, 2464, 16835, 118104, 823585, 8, 72, 528, 4176, 32800, 262800, 2097200, 16781472, 9, 90, 747, 6660, 59085, 532350, 4783023, 43053480, 387422001

Offset: 1

N. J. A. Sloane, Apr 16 2000

			1;
2, 6;
3, 12, 33;
4, 20, 72,  280;
5, 30, 135, 660,  3145;
6, 42, 228, 1344, 7800, 46956;
...

Alois P. Heinz, Rows n = 1..141, flattened

Cf. A054618, A054630, A054631, A185651 (transpose).

Main diagonal gives: A228640.

with(numtheory):
T:= (n, k)-> add(phi(d)*n^(k/d), d=divisors(k)):
seq(seq(T(n,k), k=1..n), n=1..10);  # Alois P. Heinz, Aug 28 2013

T[n_, k_] := Sum[EulerPhi[d]*n^(k/d), {d, Divisors[k]}]; Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Feb 25 2015 *)

T(n, k) = sumdiv(k, d, eulerphi(d)*n^(k/d)); \\ Michel Marcus, Feb 25 2015

A121775 T(n, k) = Sum_{d|n} phi(n/d)*binomial(d,k) for n>0, T(0, 0) = 1. Triangle read by rows, for 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 2, 3, 1, 3, 5, 3, 1, 4, 8, 7, 4, 1, 5, 9, 10, 10, 5, 1, 6, 15, 20, 21, 15, 6, 1, 7, 13, 21, 35, 35, 21, 7, 1, 8, 20, 36, 60, 71, 56, 28, 8, 1, 9, 21, 42, 86, 126, 126, 84, 36, 9, 1, 10, 27, 59, 130, 215, 253, 210, 120, 45, 10, 1, 11, 21, 55, 165, 330, 462, 462, 330, 165, 55

Offset: 0

Paul D. Hanna, Aug 23 2006

For n>0, (1/n)*Sum_{k=0..n} T(n,k)*(c-1)^k is the number of n-bead necklaces with c colors. See the cross references.

			Triangle begins:
[ 0]  1;
[ 1]  1,  1;
[ 2]  2,  3,  1;
[ 3]  3,  5,  3,   1;
[ 4]  4,  8,  7,   4,   1;
[ 5]  5,  9, 10,  10,   5,   1;
[ 6]  6, 15, 20,  21,  15,   6,   1;
[ 7]  7, 13, 21,  35,  35,  21,   7,   1;
[ 8]  8, 20, 36,  60,  71,  56,  28,   8,  1;
[ 9]  9, 21, 42,  86, 126, 126,  84,  36,  9,  1;
[10] 10, 27, 59, 130, 215, 253, 210, 120, 45, 10, 1;

Cf. A053635 (row sums), A121776 (antidiagonal sums), A054630, A327029.

Cf. A000031 (c=2), A001867 (c=3), A001868 (c=4), A001869 (c=5), A054625 (c=6), A054626 (c=7), A054627 (c=8), A054628 (c=9), A054629 (c=10).

PARI
```
T(n,k)=if(n
				
```

# uses[DivisorTriangle from A327029]
DivisorTriangle(euler_phi, binomial, 13) # Peter Luschny, Aug 24 2019

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.

Original entry on oeis.org

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

Peter Luschny, Sep 10 2018

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

D. E. Knuth, Generating All Tuples and Permutations. The Art of Computer Programming, Vol. 4, Fascicle 2, Addison-Wesley, 2005.

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).
Peter Luschny, Implementation of the FKM algorithm in SageMath and Julia
F. Ruskey, C. Savage, and T. M. Y. Wang, Generating necklaces, Journal of Algorithms, 13(3), 1992, 414-430.
Index entries for sequences related to necklaces

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.

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);

A(n,k)=if(k==0, 0, sumdiv(k,d, eulerphi(d)*n^(k/d))/k) \\ Andrew Howroyd, Jan 05 2024

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)])

A(n, k) = (1/k)*Sum_{i=1..k} n^gcd(i, k) for k > 0.

cp's OEIS Frontend

A075195 Jablonski table T(n,k) read by antidiagonals: T(n,k) = number of necklaces with n beads of k colors.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A056665 Number of equivalence classes of n-valued Post functions of 1 variable under action of complementing group C(1,n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Sage

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A215474 Triangle read by rows: number of k-ary n-tuples (a_1,..,a_n) such that the string a_1...a_n is preprime.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

A054618 Triangle T(n,k) = Sum_{d|n} phi(d)*k^(n/d).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A054619 Triangle T(n,k) = Sum_{d|k} phi(d)*n^(k/d).

Views

Author

Keywords

Examples

Links

Crossrefs

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.