The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 49
 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 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS 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 REFERENCES 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. LINKS 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 FORMULA T(n,k) = (1/n) * Sum_{d|n} mu(n/d)*k^d. T(n,k) = (k^n - Sum_{d= 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 CROSSREFS Columns k=2..19 are A001037, A027376, A027377, A001692, A032164, A001693, A027380, A027381, A032165, A032166, A032167, A060216, A060217, A060218, A060219, A060220, A060221, A060222. Rows n=1..7: A000027, A000217(k-1), A007290(k+1), A006011, A208536(k+1), A292350, A208537(k+1). Diagonal: A075147. See also A102659, A215474 (preprime strings). Sequence in context: A284856 A276550 A294438 * A284871 A202064 A144955 Adjacent sequences:  A074647 A074648 A074649 * A074651 A074652 A074653 KEYWORD nonn,tabl AUTHOR Christian G. Bower, Aug 28 2002 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 23 04:54 EDT 2020. Contains 337295 sequences. (Running on oeis4.)