cp's OEIS Frontend

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.

%I A143328 #29 Oct 04 2018 20:33:08
%S A143328 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,
%T A143328 28,91,205,294,196,41,1,9,36,140,406,829,964,508,71,1,10,45,204,728,
%U A143328 1960,3409,3304,1318,127,1,11,55,285,1212,4088,9695,14569,11464,3502,226,1
%N 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.
%H A143328 Alois P. Heinz, <a href="/A143328/b143328.txt">Antidiagonals n = 1..141, flattened</a>
%H A143328 <a href="/index/Lu#Lyndon">Index entries for sequences related to Lyndon words</a>
%F A143328 T(n,k) = Sum_{1<=j<=n} (1/j) * Sum_{d|j} mu(j/d)*k^d.
%F A143328 T(n,k) = Sum_{1<=j<=n} A074650(j,k).
%e A143328 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.
%e A143328 Table begins:
%e A143328   1,  2,  3,   4,   5,  ...
%e A143328   1,  3,  6,  10,  15,  ...
%e A143328   1,  5, 14,  30,  55,  ...
%e A143328   1,  8, 32,  90, 205,  ...
%e A143328   1, 14, 80, 294, 829,  ...
%p A143328 with(numtheory):
%p A143328 f0:= proc(n) option remember; unapply(k^n-add(f0(d)(k),
%p A143328         d=divisors(n)minus{n}), k)
%p A143328      end:
%p A143328 f2:= proc(n) option remember; unapply(f0(n)(x)/n, x) end:
%p A143328 g2:= proc(n) option remember; unapply(add(f2(j)(x), j=1..n), x) end:
%p A143328 T:= (n,k)-> g2(n)(k):
%p A143328 seq(seq(T(n, 1+d-n), n=1..d), d=1..12);
%t A143328 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 *)
%Y A143328 Columns k=1-5 give: A000012, A062692, A114945, A114946, A114947.
%Y A143328 Rows n=1-4 give: A000027, A000217, A000330, A132117.
%Y A143328 Main diagonal gives A215475.
%Y A143328 Cf. A143324, A074650, A008683.
%K A143328 nonn,tabl
%O A143328 1,2
%A A143328 _Alois P. Heinz_, Aug 07 2008