A075147 -id:A075147 - cp's OEIS frontend

A074650 Table T(n,k) read by downward antidiagonals: number of Lyndon words (aperiodic necklaces) with n beads of k colors, n >= 1, k >= 1.

1, 2, 0, 3, 1, 0, 4, 3, 2, 0, 5, 6, 8, 3, 0, 6, 10, 20, 18, 6, 0, 7, 15, 40, 60, 48, 9, 0, 8, 21, 70, 150, 204, 116, 18, 0, 9, 28, 112, 315, 624, 670, 312, 30, 0, 10, 36, 168, 588, 1554, 2580, 2340, 810, 56, 0, 11, 45, 240, 1008, 3360, 7735, 11160, 8160, 2184, 99, 0

Offset: 1

Christian G. Bower, Aug 28 2002

D. E. Knuth uses the term 'prime strings' for Lyndon words because of the fundamental theorem stating the unique factorization of strings into nonincreasing prime strings (see Knuth 7.2.1.1). With this terminology T(n,k) is the number of k-ary n-tuples (a_1,...,a_n) such that the string a_1...a_n is prime. - Peter Luschny, Aug 14 2012
Also, for k a power of a prime, the number of monic irreducible polynomials of degree n over GF(k). - Andrew Howroyd, Dec 23 2017
An equivalent description: Array read by antidiagonals: T(n,k) = number of conjugacy classes of primitive words of length k >= 1 over an alphabet of size n >= 1.
There are a few incorrect values in Table 1 in the Perrin-Reutenauer paper (Christophe Reutenauer, personal communication), see A294438. - Lars Blomberg, Dec 05 2017
The fact that T(3,4) = 20 coincides with the number of the amino acids encoded by DNA made Francis Crick, John Griffith and Leslie Orgel conjecture in 1957 that the genetic code is a comma-free code, which later turned out to be false. [Hayes] - Andrey Zabolotskiy, Mar 24 2018

			T(4, 3) counts the 18 ternary prime strings of length 4 which are: 0001, 0002, 0011, 0012, 0021, 0022, 0102, 0111, 0112, 0121, 0122, 0211, 0212, 0221, 0222, 1112, 1122, 1222.
Square array starts:
  1,  2,   3,    4,     5,     6,      7, ...
  0,  1,   3,    6,    10,    15,     21, ...
  0,  2,   8,   20,    40,    70,    112, ...
  0,  3,  18,   60,   150,   315,    588, ...
  0,  6,  48,  204,   624,  1554,   3360, ...
  0,  9, 116,  670,  2580,  7735,  19544, ...
  0, 18, 312, 2340, 11160, 39990, 117648, ...
  ...
The transposed array starts:
   1  0  0     0     0      0       0        0         0          0,
   2  1  2     3     6      9      18       30        56         99,
   3  3  8    18    48    116     312      810      2184       5880,
   4  6  20   60   204    670    2340     8160     29120     104754,
   5 10  40  150   624   2580   11160    48750    217000     976248,
   6 15  70  315  1554   7735   39990   209790   1119720    6045837,
   7 21 112  588  3360  19544  117648   720300   4483696   28245840,
   8 28 168 1008  6552  43596  299592  2096640  14913024  107370900,
   9 36 240 1620 11808  88440  683280  5380020  43046640  348672528,
  10 45 330 2475 19998 166485 1428570 12498750 111111000  999989991,
  11 55 440 3630 32208 295020 2783880 26793030 261994040 2593726344,
  12 66 572 5148 49764 497354 5118828 53745120 573308736 6191711526,
  ...
The initial antidiagonals are:
   1
   2  0
   3  1   0
   4  3   2    0
   5  6   8    3    0
   6 10  20   18    6     0
   7 15  40   60   48     9     0
   8 21  70  150  204   116    18     0
   9 28 112  315  624   670   312    30     0
  10 36 168  588 1554  2580  2340   810    56    0
  11 45 240 1008 3360  7735 11160  8160  2184   99   0
  12 55 330 1620 6552 19544 39990 48750 29120 5880 186 0

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 97 (2.3.74)
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 495.
D. E. Knuth, Generating All Tuples and Permutations. The Art of Computer Programming, Vol. 4, Fascicle 2, pp. 26-27, Addison-Wesley, 2005.

Alois P. Heinz, Antidiagonals n = 1..141, flattened
B. Hayes, The invention of the genetic code, American Scientist, Vol. 86, No. 1 (January-February 1998), pp. 8-14.
Veronika Irvine, Lace Tessellations: A mathematical model for bobbin lace and an exhaustive combinatorial search for patterns, PhD Dissertation, University of Victoria, 2016.
Irem Kucukoglu and Yilmaz Simsek, On k-ary Lyndon words and their generating functions, AIP Conference Proceedings 1863, 300004 (2017).
R. C. Lyndon, On Burnside's problem, Transactions of the American Mathematical Society 77, (1954) 202-215.
Dominique Perrin and Christophe Reutenauer, Hall sets, Lazard sets and comma-free codes, arXiv preprint arXiv:1609.05438 [math.CO] (2016).
Dominique Perrin and Christophe Reutenauer, Hall sets, Lazard sets and comma-free codes, Discrete Math., 341 (2018), 232-243.
Dominique Perrin and Christophe Reutenauer, Hall sets, Lazard sets and comma-free codes, Discrete Math., 341 (2018), 232-243. [Annotated scanned copy of page 236 only.]
Wikipedia, Lyndon word
Index entries for sequences related to Lyndon words

Columns k: A001037 (k=2), A027376 (k=3), A027377 (k=4), A001692 (k=5), A032164 (k=6), A001693 (k=7), A027380 (k=8), A027381 (k=9), A032165 (k=10), A032166 (k=11), A032167 (k=12), A060216 (k=13), A060217 (k=14), A060218 (k=15), A060219 (k=16), A060220 (k=17), A060221 (k=18), A060222 (k=19).
Rows n: A000027 (n=1), A000217(k-1) (n=2), A007290(k+1) (n=3), A006011 (n=4), A208536(k+1) (n=5), A292350 (n=6), A208537(k+1) (n=7).
Cf. A000010, A008683, A075147 (main diagonal), A102659, A215474 (preprime strings), A383011.

t:= func< n,k | (&+[MoebiusMu(Floor(n/d))*k^d: d in Divisors(n)])/n >; // array
A074650:= func< n,k | t(k, n-k+1) >; // downward diagonals
[A074650(n,k): k in [1..n], n in [1..15]]; // G. C. Greubel, Aug 01 2024

with(numtheory):
T:= proc(n, k) add(mobius(n/d)*k^d, d=divisors(n))/n end:
seq(seq(T(i, 1+d-i), i=1..d), d=1..11);  # Alois P. Heinz, Mar 28 2008

max = 12; t[n_, k_] := Total[ MoebiusMu[n/#]*k^# & /@ Divisors[n]]/n; Flatten[ Table[ t[n-k+1, k], {n, 1, max}, {k, n, 1, -1}]] (* Jean-François Alcover, Oct 18 2011, after Maple *)

T(n,k)=sumdiv(n,d,moebius(n/d)*k^d)/n \\ Charles R Greathouse IV, Oct 18 2011

# This algorithm generates and counts all k-ary n-tuples (a_1,..,a_n) such
# that the string a_1...a_n is prime. It is algorithm F in Knuth 7.2.1.1.
def A074650(n, k):
    a = [0]*(n+1); a[0]=-1
    j = 1; count = 0
    while(j != 0) :
        if j == n : count += 1; # print("".join(map(str,a[1:])))
        else: j = n
        while a[j] >= k-1 : j -= 1
        a[j] += 1
        for i in (j+1..n): a[i] = a[i-j]
    return count   # Peter Luschny, Aug 14 2012

T(n,k) = (1/n) * Sum_{d|n} mu(n/d)*k^d.
T(n,k) = (k^n - Sum_{dAlois P. Heinz, Mar 28 2008
From Richard L. Ollerton, May 10 2021: (Start)
T(n,k) = (1/n)*Sum_{i=1..n} mu(gcd(n,i))*k^(n/gcd(n,i))/phi(n/gcd(n,i)).
T(n,k) = (1/n)*Sum_{i=1..n} mu(n/gcd(n,i))*k^gcd(n,i)/phi(n/gcd(n,i)). (End)
From Seiichi Manyama, Apr 12 2025: (Start)
G.f. of column k: -Sum_{j>=1} mu(j) * log(1 - k*x^j) / j.
Product_{n>=1} 1/(1 - x^n)^T(n,k) = 1/(1 - k*x). (End)

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)

A143325 Table T(n,k) by antidiagonals. T(n,k) is the number of length n primitive (=aperiodic or period n) k-ary words (n,k >= 1) which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 3, 0, 1, 3, 8, 6, 0, 1, 4, 15, 24, 15, 0, 1, 5, 24, 60, 80, 27, 0, 1, 6, 35, 120, 255, 232, 63, 0, 1, 7, 48, 210, 624, 1005, 728, 120, 0, 1, 8, 63, 336, 1295, 3096, 4095, 2160, 252, 0, 1, 9, 80, 504, 2400, 7735, 15624, 16320, 6552, 495, 0, 1, 10, 99

Offset: 1

Alois P. Heinz, Aug 07 2008

Column k is Dirichlet convolution of mu(n) with k^(n-1). The coefficients of the polynomial of row n are given by the n-th row of triangle A054525; for example row 4 has polynomial -k+k^3.

			T(4,2)=6, because 6 words of length 4 over 2-letter alphabet {a,b} are primitive and earlier than others derived by cyclic shifts of the alphabet: aaab, aaba, aabb, abaa, abba, abbb; note that aaaa and abab are not primitive and words beginning with b can be derived by shifts of the alphabet from words in the list; secondly note that the words in the list need not be Lyndon words, for example aaba can be derived from aaab by a cyclic rotation of the positions.
Table begins:
  1,   1,    1,     1,     1,      1,      1,       1, ...
  0,   1,    2,     3,     4,      5,      6,       7, ...
  0,   3,    8,    15,    24,     35,     48,      63, ...
  0,   6,   24,    60,   120,    210,    336,     504, ...
  0,  15,   80,   255,   624,   1295,   2400,    4095, ...
  0,  27,  232,  1005,  3096,   7735,  16752,   32697, ...
  0,  63,  728,  4095, 15624,  46655, 117648,  262143, ...
  0, 120, 2160, 16320, 78000, 279720, 823200, 2096640, ...

Alois P. Heinz, Antidiagonals n = 1..141, flattened
Index entries for sequences related to Lyndon words

Columns k=1-10 give: A063524, A000740, A034741, A295505, A295506, A320071, A320072, A320073, A320074, A320075.
Rows n=1-5, 7 give: A000012, A001477, A005563, A007531, A123865, A123866.
Main diagonal gives A075147.
Cf. A074650, A143324, A008683, A054525.

with(numtheory):
f1:= proc(n) option remember;
       unapply(k^(n-1)-add(f1(d)(k), d=divisors(n)minus{n}), k)
     end;
T:= (n,k)-> f1(n)(k);
seq(seq(T(n, 1+d-n), n=1..d), d=1..12);

t[n_, k_] := Sum[k^(d-1)*MoebiusMu[n/d], {d, Divisors[n]}]; Table[t[n-k+1, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Jan 21 2014, from first formula *)

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

T(n,k) = k^(n-1) - Sum_{d

T(n,k) = A074650(n,k) * n/k.

T(n,k) = A143324(n,k) / k.

A306173 a(n) is the n-th term of the inverse Euler transform of j-> n^(j-1).

Original entry on oeis.org

1, 1, 6, 42, 420, 5155, 77658, 1376340, 28133616, 651317463, 16846515510, 481472570920, 15067838554860, 512473599799551, 18821719654854998, 742395982266536520, 31299550394528466960, 1404629090174946183156, 66851805805525048040334, 3363381327122496643643628

Offset: 1

Alois P. Heinz, Jun 23 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..200

Main diagonal of A065177.

Cf. A075147, A316073.

b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(g(i, k)+j-1, j)*b(n-i*j, i-1,k), j=0..n/i)))
    end:
g:= proc(n, k) option remember; k^(n-1)-b(n, n-1, k) end:
a:= n-> g(n$2):
seq(a(n), n=1..21);

b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[g[i, k] + j - 1, j]*b[n - i*j, i - 1, k], {j, 0, n/i}]]];
g[n_, k_] := g[n, k] = k^(n - 1) - b[n, n - 1, k];
a[n_] := g[n, n];
a /@ Range[21] (* Jean-François Alcover, Jan 06 2020, after Alois P. Heinz *)

a(n) ~ (1 - exp(-1)) * n^(n-1). - Vaclav Kotesovec, Oct 08 2019

A252764 Number of length n primitive (=aperiodic or period n) n-ary words.

Original entry on oeis.org

1, 2, 24, 240, 3120, 46410, 823536, 16773120, 387419760, 9999899910, 285311670600, 8916097441680, 302875106592240, 11112006720144330, 437893890380096640, 18446744069414584320, 827240261886336764160, 39346408075098144278664, 1978419655660313589123960

Offset: 1

Alois P. Heinz, Dec 21 2014

nonn

			a(3) = 24 because there are 24 primitive words of length 3 over 3-letter alphabet {a,b,c}: aab, aac, aba, abb, abc, aca, acb, acc, baa, bab, bac, bba, bbc, bca, bcb, bcc, caa, cab, cac, cba, cbb, cbc, cca, ccb.

Alois P. Heinz, Table of n, a(n) for n = 1..350

Main diagonal of A143324.

Cf. A008683, A074650, A075147, A143324, A143325.

with(numtheory):
a:= n-> add(n^d *mobius(n/d), d=divisors(n)):
seq(a(n), n=1..25);

a[n_] := DivisorSum[n, n^# * MoebiusMu[n/#]& ];
Array[a, 25] (* Jean-François Alcover, Mar 24 2017, translated from Maple *)

a(n) = Sum_{d|n} n^d * mu(n/d), mu = A008683.
a(n) = A075147(n)*n.
a(n) = A074650(n,n) * n.
a(n) = A143325(n,n) * n.
a(n) = A143324(n,n).

A383012 a(n) = Sum_{d|n} mu(n/d) * (-n)^(d-1).

Original entry on oeis.org

1, -3, 8, -60, 624, -7805, 117648, -2096640, 43046640, -1000009989, 25937424600, -743008120140, 23298085122480, -793714780783665, 29192926025339776, -1152921504338411520, 48661191875666868480, -2185911559749714602652, 104127350297911241532840

Offset: 1

Seiichi Manyama, Apr 12 2025

sign

Main diagonal of A383011.

Cf. A008683, A075147, A382998, A383003.

a(n) = sumdiv(n, d, moebius(n/d)*(-n)^(d-1));

a(n) = [x^n] Sum_{k>=1} mu(k) * log(1 + n*x^k) / k.

a(n) = [x^n] Sum_{k>=1} mu(k) * x^k / (1 + n*x^k).

Showing 1-6 of 6 results.

cp's OEIS Frontend

A074650 Table T(n,k) read by downward antidiagonals: number of Lyndon words (aperiodic necklaces) with n beads of k colors, n >= 1, k >= 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

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

A143325 Table T(n,k) by antidiagonals. T(n,k) is the number of length n primitive (=aperiodic or period n) k-ary words (n,k >= 1) which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A306173 a(n) is the n-th term of the inverse Euler transform of j-> n^(j-1).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A252764 Number of length n primitive (=aperiodic or period n) n-ary words.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A383012 a(n) = Sum_{d|n} mu(n/d) * (-n)^(d-1).

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula