login
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.
7
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
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.
Sequence in context: A285548 A130305 A323346 * A192001 A122176 A159881
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Aug 07 2008
STATUS
approved