A143328 Table T(n,k) read by antidiagonals. T(n,k) is the number of primitive (=aperiodic) k-ary Lyndon words (n,k >= 1) with length less than or equal to n.

1, 2, 1, 3, 3, 1, 4, 6, 5, 1, 5, 10, 14, 8, 1, 6, 15, 30, 32, 14, 1, 7, 21, 55, 90, 80, 23, 1, 8, 28, 91, 205, 294, 196, 41, 1, 9, 36, 140, 406, 829, 964, 508, 71, 1, 10, 45, 204, 728, 1960, 3409, 3304, 1318, 127, 1, 11, 55, 285, 1212, 4088, 9695, 14569, 11464, 3502, 226, 1

Offset

1,2

Links

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

Index entries for sequences related to Lyndon words

Formula

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

T(n,k) = Sum_{1<=j<=n} A074650(j,k).

Example

T(3,2) = 5, because 5 words of length <=3 over 2-letter alphabet {a,b} are primitive Lyndon words: a, b, ab, aab, abb.
Table begins:
  1,  2,  3,   4,   5,  ...
  1,  3,  6,  10,  15,  ...
  1,  5, 14,  30,  55,  ...
  1,  8, 32,  90, 205,  ...
  1, 14, 80, 294, 829,  ...

Maple

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

Mathematica

f0[n_] := f0[n] = Function[k, k^n-Sum[f0[d][k], {d, Divisors[n]//Most}]]; f2[n_] := f2[n] = Function[x, f0[n][x]/n]; g2[n_] := g2[n] = Function[x, Sum[f2[j][x], {j, 1, n}]]; T[n_, k_] := g2[n][k]; Table[T[n, 1+d-n], {d, 1, 12}, {n, 1, d}]//Flatten (* Jean-François Alcover, Feb 12 2014, translated from Maple *)

Crossrefs

Columns k=1-5 give: A000012, A062692, A114945, A114946, A114947.

Rows n=1-4 give: A000027, A000217, A000330, A132117.

Main diagonal gives A215475.

Cf. A143324, A074650, A008683.

Sequence in context: A285548 A130305 A323346 * A192001 A122176 A159881

Adjacent sequences: A143325 A143326 A143327 * A143329 A143330 A143331

Keyword

nonn,tabl

Author

Alois P. Heinz, Aug 07 2008

Status

approved