login
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.
12

%I #26 Oct 05 2018 16:10:57

%S 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 7,41,149,334,347,116,1,1,8,55,251,773,1339,1075,236,1,1,9,71,391,

%U 1546,3869,5434,3235,488,1,1,10,89,575,2791,9281,19493,21754,9787,983,1,1,11

%N 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 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 Alois P. Heinz, <a href="/A143327/b143327.txt">Antidiagonals n = 1..141, flattened</a>

%H <a href="/index/Lu#Lyndon">Index entries for sequences related to Lyndon words</a>

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

%F T(n,k) = Sum_{j=1..n} A143325(j,k).

%F T(n,k) = A143326(n,k) / k.

%e 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 Table begins:

%e 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 1, 2, 3, 4, 5, 6, 7, 8, ...

%e 1, 5, 11, 19, 29, 41, 55, 71, ...

%e 1, 11, 35, 79, 149, 251, 391, 575, ...

%e 1, 26, 115, 334, 773, 1546, 2791, 4670, ...

%e 1, 53, 347, 1339, 3869, 9281, 19543, 37367, ...

%e 1, 116, 1075, 5434, 19493, 55936, 137191, 299510, ...

%e 1, 236, 3235, 21754, 97493, 335656, 960391, 2396150, ...

%p with(numtheory):

%p f1:= proc (n) option remember; unapply(k^(n-1)

%p -add(f1(d)(k), d=divisors(n) minus {n}), k)

%p end:

%p g1:= proc(n) option remember; unapply(add(f1(j)(x), j=1..n), x) end:

%p T:= (n, k)-> g1(n)(k):

%p seq(seq(T(n, 1+d-n), n=1..d), d=1..12);

%t 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 Columns k=1-10 give: A000012, A085945, A320087, A320088, A320089, A320090, A320091, A320092, A320093, A320094.

%Y Rows n=1-4 give: A000012, A000027, A028387, A003777.

%Y Main diagonal gives A320095.

%Y Cf. A143325, A143326, A134541, A008683.

%K nonn,tabl

%O 1,5

%A _Alois P. Heinz_, Aug 07 2008