This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A074650 #121 Apr 12 2025 17:52:30
%S A074650 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,
%T A074650 70,150,204,116,18,0,9,28,112,315,624,670,312,30,0,10,36,168,588,1554,
%U A074650 2580,2340,810,56,0,11,45,240,1008,3360,7735,11160,8160,2184,99,0
%N 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.
%C A074650 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
%C A074650 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
%C A074650 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.
%C A074650 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
%C A074650 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
%D A074650 F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 97 (2.3.74)
%D A074650 Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 495.
%D A074650 D. E. Knuth, Generating All Tuples and Permutations. The Art of Computer Programming, Vol. 4, Fascicle 2, pp. 26-27, Addison-Wesley, 2005.
%H A074650 Alois P. Heinz, <a href="/A074650/b074650.txt">Antidiagonals n = 1..141, flattened</a>
%H A074650 B. Hayes, <a href="http://bit-player.org/wp-content/extras/bph-publications/AmSci-1998-01-Hayes-genetic-code.pdf">The invention of the genetic code</a>, American Scientist, Vol. 86, No. 1 (January-February 1998), pp. 8-14.
%H A074650 Veronika Irvine, <a href="http://hdl.handle.net/1828/7495">Lace Tessellations: A mathematical model for bobbin lace and an exhaustive combinatorial search for patterns</a>, PhD Dissertation, University of Victoria, 2016.
%H A074650 Irem Kucukoglu and Yilmaz Simsek, <a href="https://dx.doi.org/10.1063/1.4992453">On k-ary Lyndon words and their generating functions</a>, AIP Conference Proceedings 1863, 300004 (2017).
%H A074650 R. C. Lyndon, <a href="https://doi.org/10.1090/S0002-9947-1954-0064049-X">On Burnside's problem</a>, Transactions of the American Mathematical Society 77, (1954) 202-215.
%H A074650 Dominique Perrin and Christophe Reutenauer, <a href="https://arxiv.org/abs/1609.05438">Hall sets, Lazard sets and comma-free codes</a>, arXiv preprint arXiv:1609.05438 [math.CO] (2016).
%H A074650 Dominique Perrin and Christophe Reutenauer, <a href="https://doi.org/10.1016/j.disc.2017.08.034">Hall sets, Lazard sets and comma-free codes</a>, Discrete Math., 341 (2018), 232-243.
%H A074650 Dominique Perrin and Christophe Reutenauer, <a href="/A294438/a294438.jpg">Hall sets, Lazard sets and comma-free codes</a>, Discrete Math., 341 (2018), 232-243. [Annotated scanned copy of page 236 only.]
%H A074650 Wikipedia, <a href="https://en.wikipedia.org/wiki/Lyndon_word">Lyndon word</a>
%H A074650 <a href="/index/Lu#Lyndon">Index entries for sequences related to Lyndon words</a>
%F A074650 T(n,k) = (1/n) * Sum_{d|n} mu(n/d)*k^d.
%F A074650 T(n,k) = (k^n - Sum_{d<n,d|n} d*T(d,k)) / n. - _Alois P. Heinz_, Mar 28 2008
%F A074650 From _Richard L. Ollerton_, May 10 2021: (Start)
%F A074650 T(n,k) = (1/n)*Sum_{i=1..n} mu(gcd(n,i))*k^(n/gcd(n,i))/phi(n/gcd(n,i)).
%F A074650 T(n,k) = (1/n)*Sum_{i=1..n} mu(n/gcd(n,i))*k^gcd(n,i)/phi(n/gcd(n,i)). (End)
%F A074650 From _Seiichi Manyama_, Apr 12 2025: (Start)
%F A074650 G.f. of column k: -Sum_{j>=1} mu(j) * log(1 - k*x^j) / j.
%F A074650 Product_{n>=1} 1/(1 - x^n)^T(n,k) = 1/(1 - k*x). (End)
%e A074650 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.
%e A074650 Square array starts:
%e A074650 1, 2, 3, 4, 5, 6, 7, ...
%e A074650 0, 1, 3, 6, 10, 15, 21, ...
%e A074650 0, 2, 8, 20, 40, 70, 112, ...
%e A074650 0, 3, 18, 60, 150, 315, 588, ...
%e A074650 0, 6, 48, 204, 624, 1554, 3360, ...
%e A074650 0, 9, 116, 670, 2580, 7735, 19544, ...
%e A074650 0, 18, 312, 2340, 11160, 39990, 117648, ...
%e A074650 ...
%e A074650 The transposed array starts:
%e A074650 1 0 0 0 0 0 0 0 0 0,
%e A074650 2 1 2 3 6 9 18 30 56 99,
%e A074650 3 3 8 18 48 116 312 810 2184 5880,
%e A074650 4 6 20 60 204 670 2340 8160 29120 104754,
%e A074650 5 10 40 150 624 2580 11160 48750 217000 976248,
%e A074650 6 15 70 315 1554 7735 39990 209790 1119720 6045837,
%e A074650 7 21 112 588 3360 19544 117648 720300 4483696 28245840,
%e A074650 8 28 168 1008 6552 43596 299592 2096640 14913024 107370900,
%e A074650 9 36 240 1620 11808 88440 683280 5380020 43046640 348672528,
%e A074650 10 45 330 2475 19998 166485 1428570 12498750 111111000 999989991,
%e A074650 11 55 440 3630 32208 295020 2783880 26793030 261994040 2593726344,
%e A074650 12 66 572 5148 49764 497354 5118828 53745120 573308736 6191711526,
%e A074650 ...
%e A074650 The initial antidiagonals are:
%e A074650 1
%e A074650 2 0
%e A074650 3 1 0
%e A074650 4 3 2 0
%e A074650 5 6 8 3 0
%e A074650 6 10 20 18 6 0
%e A074650 7 15 40 60 48 9 0
%e A074650 8 21 70 150 204 116 18 0
%e A074650 9 28 112 315 624 670 312 30 0
%e A074650 10 36 168 588 1554 2580 2340 810 56 0
%e A074650 11 45 240 1008 3360 7735 11160 8160 2184 99 0
%e A074650 12 55 330 1620 6552 19544 39990 48750 29120 5880 186 0
%p A074650 with(numtheory):
%p A074650 T:= proc(n, k) add(mobius(n/d)*k^d, d=divisors(n))/n end:
%p A074650 seq(seq(T(i, 1+d-i), i=1..d), d=1..11); # _Alois P. Heinz_, Mar 28 2008
%t A074650 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 *)
%o A074650 (PARI) T(n,k)=sumdiv(n,d,moebius(n/d)*k^d)/n \\ _Charles R Greathouse IV_, Oct 18 2011
%o A074650 (Sage)
%o A074650 # This algorithm generates and counts all k-ary n-tuples (a_1,..,a_n) such
%o A074650 # that the string a_1...a_n is prime. It is algorithm F in Knuth 7.2.1.1.
%o A074650 def A074650(n, k):
%o A074650 a = [0]*(n+1); a[0]=-1
%o A074650 j = 1; count = 0
%o A074650 while(j != 0) :
%o A074650 if j == n : count += 1; # print("".join(map(str,a[1:])))
%o A074650 else: j = n
%o A074650 while a[j] >= k-1 : j -= 1
%o A074650 a[j] += 1
%o A074650 for i in (j+1..n): a[i] = a[i-j]
%o A074650 return count # _Peter Luschny_, Aug 14 2012
%o A074650 (Magma)
%o A074650 t:= func< n,k | (&+[MoebiusMu(Floor(n/d))*k^d: d in Divisors(n)])/n >; // array
%o A074650 A074650:= func< n,k | t(k, n-k+1) >; // downward diagonals
%o A074650 [A074650(n,k): k in [1..n], n in [1..15]]; // _G. C. Greubel_, Aug 01 2024
%Y A074650 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).
%Y A074650 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).
%Y A074650 Cf. A000010, A008683, A075147 (main diagonal), A102659, A215474 (preprime strings), A383011.
%K A074650 nonn,tabl
%O A074650 1,2
%A A074650 _Christian G. Bower_, Aug 28 2002