login
This site is supported by donations to The OEIS Foundation.

 

Logo


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. 48
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)

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

Index entries for sequences related to Lyndon words

FORMULA

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

T(n,k) = (k^n - Sum_{d<n,d|n} d*T(d,k)) / n. - Alois P. Heinz, Mar 28 2008

EXAMPLE

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

  0, 1,  3,   6,  10, ...

  0, 2,  8,  20,  40, ...

  0, 3, 18,  60, 150, ...

  0, 6, 48, 204, 624, ...

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

MAPLE

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

MATHEMATICA

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

PROG

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

(Sage)

# 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

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

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 14 23:27 EST 2018. Contains 317221 sequences. (Running on oeis4.)