cp's OEIS Frontend

A143327 Table T(n,k) by antidiagonals. T(n,k) is the number of primitive (=aperiodic) k-ary words (n,k >= 1) with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

%I A143327 #26 Oct 05 2018 16:10:57
%S A143327 1,1,1,1,2,1,1,3,5,1,1,4,11,11,1,1,5,19,35,26,1,1,6,29,79,115,53,1,1,
%T A143327 7,41,149,334,347,116,1,1,8,55,251,773,1339,1075,236,1,1,9,71,391,
%U A143327 1546,3869,5434,3235,488,1,1,10,89,575,2791,9281,19493,21754,9787,983,1,1,11
%N A143327 Table T(n,k) by antidiagonals. T(n,k) is the number of primitive (=aperiodic) k-ary words (n,k >= 1) with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.
%C A143327 The coefficients of the polynomial of row n are given by the n-th row of triangle A134541; for example row 4 has polynomial -1+k^2+k^3.
%H A143327 Alois P. Heinz, <a href="/A143327/b143327.txt">Antidiagonals n = 1..141, flattened</a>
%H A143327 <a href="/index/Lu#Lyndon">Index entries for sequences related to Lyndon words</a>
%F A143327 T(n,k) = Sum_{j=1..n} Sum_{d|j} k^(d-1) * mu(j/d).
%F A143327 T(n,k) = Sum_{j=1..n} A143325(j,k).
%F A143327 T(n,k) = A143326(n,k) / k.
%e A143327 T(3,3) = 11, because 11 words of length <=3 over 3-letter alphabet {a,b,c} are primitive and earlier than others derived by cyclic shifts of the alphabet: a, ab, ac, aab, aac, aba, abb, abc, aca, acb, acc.
%e A143327 Table begins:
%e A143327   1,   1,    1,     1,     1,      1,      1,       1, ...
%e A143327   1,   2,    3,     4,     5,      6,      7,       8, ...
%e A143327   1,   5,   11,    19,    29,     41,     55,      71, ...
%e A143327   1,  11,   35,    79,   149,    251,    391,     575, ...
%e A143327   1,  26,  115,   334,   773,   1546,   2791,    4670, ...
%e A143327   1,  53,  347,  1339,  3869,   9281,  19543,   37367, ...
%e A143327   1, 116, 1075,  5434, 19493,  55936, 137191,  299510, ...
%e A143327   1, 236, 3235, 21754, 97493, 335656, 960391, 2396150, ...
%p A143327 with(numtheory):
%p A143327 f1:= proc (n) option remember; unapply(k^(n-1)
%p A143327         -add(f1(d)(k), d=divisors(n) minus {n}), k)
%p A143327      end:
%p A143327 g1:= proc(n) option remember; unapply(add(f1(j)(x), j=1..n), x) end:
%p A143327 T:= (n, k)-> g1(n)(k):
%p A143327 seq(seq(T(n, 1+d-n), n=1..d), d=1..12);
%t A143327 t[n_, k_] := Sum[k^(d-1)*MoebiusMu[j/d], {j, 1, n}, {d, Divisors[j]}]; Table[t[n-k+1, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* _Jean-François Alcover_, Dec 13 2013 *)
%Y A143327 Columns k=1-10 give: A000012, A085945, A320087, A320088, A320089, A320090, A320091, A320092, A320093, A320094.
%Y A143327 Rows n=1-4 give: A000012, A000027, A028387, A003777.
%Y A143327 Main diagonal gives A320095.
%Y A143327 Cf. A143325, A143326, A134541, A008683.
%K A143327 nonn,tabl
%O A143327 1,5
%A A143327 _Alois P. Heinz_, Aug 07 2008