|
%I #26 Oct 05 2018 10:14:14
%S 1,1,0,1,1,0,1,2,3,0,1,3,8,6,0,1,4,15,24,15,0,1,5,24,60,80,27,0,1,6,
%T 35,120,255,232,63,0,1,7,48,210,624,1005,728,120,0,1,8,63,336,1295,
%U 3096,4095,2160,252,0,1,9,80,504,2400,7735,15624,16320,6552,495,0,1,10,99
%N Table T(n,k) by antidiagonals. T(n,k) is the number of length n primitive (=aperiodic or period n) k-ary words (n,k >= 1) which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.
%C Column k is Dirichlet convolution of mu(n) with k^(n-1). The coefficients of the polynomial of row n are given by the n-th row of triangle A054525; for example row 4 has polynomial -k+k^3.
%H Alois P. Heinz, <a href="/A143325/b143325.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_{d|n} k^(d-1) * mu(n/d).
%F T(n,k) = k^(n-1) - Sum_{d<n,d|n} T(d,k).
%F T(n,k) = A074650(n,k) * n/k.
%F T(n,k) = A143324(n,k) / k.
%e T(4,2)=6, because 6 words of length 4 over 2-letter alphabet {a,b} are primitive and earlier than others derived by cyclic shifts of the alphabet: aaab, aaba, aabb, abaa, abba, abbb; note that aaaa and abab are not primitive and words beginning with b can be derived by shifts of the alphabet from words in the list; secondly note that the words in the list need not be Lyndon words, for example aaba can be derived from aaab by a cyclic rotation of the positions.
%e Table begins:
%e 1, 1, 1, 1, 1, 1, 1, 1, ...
%e 0, 1, 2, 3, 4, 5, 6, 7, ...
%e 0, 3, 8, 15, 24, 35, 48, 63, ...
%e 0, 6, 24, 60, 120, 210, 336, 504, ...
%e 0, 15, 80, 255, 624, 1295, 2400, 4095, ...
%e 0, 27, 232, 1005, 3096, 7735, 16752, 32697, ...
%e 0, 63, 728, 4095, 15624, 46655, 117648, 262143, ...
%e 0, 120, 2160, 16320, 78000, 279720, 823200, 2096640, ...
%p with(numtheory):
%p f1:= proc(n) option remember;
%p unapply(k^(n-1)-add(f1(d)(k), d=divisors(n)minus{n}), k)
%p end;
%p T:= (n,k)-> f1(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[n/d], {d, Divisors[n]}]; Table[t[n-k+1, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* _Jean-François Alcover_, Jan 21 2014, from first formula *)
%Y Columns k=1-10 give: A063524, A000740, A034741, A295505, A295506, A320071, A320072, A320073, A320074, A320075.
%Y Rows n=1-5, 7 give: A000012, A001477, A005563, A007531, A123865, A123866.
%Y Main diagonal gives A075147.
%Y Cf. A074650, A143324, A008683, A054525.
%K nonn,tabl
%O 1,8
%A _Alois P. Heinz_, Aug 07 2008
|
