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

Author

Alois P. Heinz, Aug 07 2008

Keywords

• nonn
• tabl

Examples

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

Links

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

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.

Programs

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

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