A054631 -id:A054631 - 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)

A087854 Triangle read by rows: T(n,k) is the number of n-bead necklaces with exactly k different colored beads.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 4, 9, 6, 1, 6, 30, 48, 24, 1, 12, 91, 260, 300, 120, 1, 18, 258, 1200, 2400, 2160, 720, 1, 34, 729, 5106, 15750, 23940, 17640, 5040, 1, 58, 2018, 20720, 92680, 211680, 258720, 161280, 40320, 1, 106, 5613, 81876, 510312, 1643544, 2963520, 3024000, 1632960, 362880

Offset: 1

Philippe Deléham

Equivalently, T(n,k) is the number of sequences (words) of length n on an alphabet of k letters where each letter of the alphabet occurs at least once in the sequence. Two sequences are considered equivalent if one can be obtained from the other by a cyclic shift of the letters. Cf. A054631 where the surjective restriction is removed. - Geoffrey Critzer, Jun 18 2013

Robert A. Russell's g.f. for column k >= 1 (in the Formula section below) can be proved by integrating both sides of the formula Sum_{n>=1} S2(n, k)*x^(n-1) = x^(k-1)/((1 - x)* (1 - 2*x) * (1 - 3*x) * ... * (1 - k*x)) w.r.t. x. A variation of this identity (valid for |x| < 1/k) can be found in the Formula section of A008277. - Petros Hadjicostas, Aug 20 2019

			The triangle begins with T(1,1):
  1;
  1,   1;
  1,   2,    2;
  1,   4,    9,     6;
  1,   6,   30,    48,     24;
  1,  12,   91,   260,    300,     120;
  1,  18,  258,  1200,   2400,    2160,     720;
  1,  34,  729,  5106,  15750,   23940,   17640,    5040;
  1,  58, 2018, 20720,  92680,  211680,  258720,  161280,   40320;
  1, 106, 5613, 81876, 510312, 1643544, 2963520, 3024000, 1632960, 362880;
  ...
For T(4,2) = 4, the necklaces are AAAB, AABB, ABAB, and ABBB.
For T(4,4) = 6, the necklaces are ABCD, ABDC, ACBD, ACDB, ADBC, and ADCB.

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

Columns 1-6: A057427, A052823, A056283, A056284, A056285, A056286.
Diagonals: A000142 and A074143.
Row sums: A019536.
Cf. A000010 (Euler totient phi function), A008277 (Stirling2 numbers), A075195 (table of Jablonski).
Cf. A254040, A273891.

with(numtheory):
T:= (n, k)-> (k!/n) *add(phi(d) *Stirling2(n/d, k), d=divisors(n)):
seq(seq(T(n,k), k=1..n), n=1..12);  # Alois P. Heinz, Jun 19 2013

Table[Table[Sum[EulerPhi[d]*StirlingS2[n/d,k]k!,{d,Divisors[n]}]/n,{k,1,n}],{n,1,10}]//Grid (* Geoffrey Critzer, Jun 18 2013 *)

T(n, k) = (k!/n) * sumdiv(n, d, eulerphi(d) * stirling(n/d, k, 2)); \\ Joerg Arndt, Sep 25 2020

T(n,k) = Sum_{i=0..k-1} (-1)^i * C(k,i) * A075195(n,k-i); A075195 = Jablonski's table.
T(n,k) = (k!/n) * Sum_{d|n} phi(d) * S2(n/d, k), where S2(n,k) = Stirling numbers of 2nd kind A008277.
G.f. for column k: -Sum_{d>0} (phi(d)/d) * Sum_{j = 1..k} (-1)^(k-j) * C(k,j) * log(1 - j * x^d). - Robert A. Russell, Sep 26 2018
T(n,k) = Sum_{d|n} A254040(d, k) for n, k >= 1. - Petros Hadjicostas, Aug 19 2019

Formula section edited by Petros Hadjicostas, Aug 20 2019

A054630 T(n,k) = Sum_{d|k} phi(d)*n^(k/d)/k, triangle read by rows, T(n,k) for n >= 1 and 1 <= k <= n.

Original entry on oeis.org

1, 2, 3, 3, 6, 11, 4, 10, 24, 70, 5, 15, 45, 165, 629, 6, 21, 76, 336, 1560, 7826, 7, 28, 119, 616, 3367, 19684, 117655, 8, 36, 176, 1044, 6560, 43800, 299600, 2097684, 9, 45, 249, 1665, 11817, 88725, 683289, 5381685, 43046889, 10, 55, 340, 2530, 20008, 166870, 1428580, 12501280, 111111340, 1000010044

Offset: 1

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

T(n, k) is the number of n-ary necklaces of length k (see Ruskey, Savage and Wang). - Peter Luschny, Aug 12 2012, comment corrected at the suggestion of Petros Hadjicostas, Peter Luschny, Sep 10 2018
From Petros Hadjicostas, Sep 12 2018: (Start)
The programs by Peter Luschny below can generate all n-ary necklaces of length k (and all k-ary necklaces of length n) for any positive integer values of n and k, not just for 1 <= k <= n.
From the examples below, we see that the number of 4-ary necklaces of length 3 equals the number of 3-ary necklaces of length 4. The question is whether there are other pairs (n, k) of distinct positive integers such that the number of n-ary necklaces of length k equals the number of k-ary necklaces of length n.
(End)

			Triangle starts:
  1;
  2,  3;
  3,  6, 11;
  4, 10, 24, 70;
  5, 15, 45, 165,  629;
  6, 21, 76, 336, 1560, 7826;
The 24 necklaces over {0,1,2} of length 4 are:
  0000,0001,0002,0011,0012,0021,0022,0101,0102,0111,0112,0121,
  0122,0202,0211,0212,0221,0222,1111,1112,1122,1212,1222,2222.
The 24 necklaces over {0,1,2,3} of length 3 are:
  000,001,002,003,011,012,013,021,022,023,031,032,
  033,111,112,113,122,123,132,133,222,223,233,333.

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

Peter Luschny, Rows 1..45, flattened
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

Cf. A054631, A054618, A054619, A056665, A215474. Upper triangle of A075195.

A054630(n::Int, k::Int) = div(sum(n^gcd(i,k) for i in 1:k), k)
for n in 1:6
    println([A054630(n, k) for k in 1:n])
end # Peter Luschny, Sep 10 2018

T := (n,k) -> add(n^igcd(i,k), i=1..k)/k:
seq(seq(T(n,k), k=1..n), n=1..10); # Peter Luschny, Sep 10 2018

T[n_, k_] := 1/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, Jul 30 2018 *)

def A054630(n,k): return (1/k)*add(euler_phi(d)*n^(k/d) for d in divisors(k))
for n in (1..9):
    print([A054630(n,k) for k in (1..n)]) # Peter Luschny, Aug 12 2012

T(n,n) = A056665(n). - Peter Luschny, Aug 12 2012

T(n,k) = (1/k)*Sum_{i=1..k} n^gcd(i, k). - Peter Luschny, Sep 10 2018

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

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

A087854 Triangle read by rows: T(n,k) is the number of n-bead necklaces with exactly k different colored beads.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A054630 T(n,k) = Sum_{d|k} phi(d)*n^(k/d)/k, triangle read by rows, T(n,k) for n >= 1 and 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Julia

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