|
| |
|
|
A143325
|
|
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.
|
|
24
|
|
|
|
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, 35, 120, 255, 232, 63, 0, 1, 7, 48, 210, 624, 1005, 728, 120, 0, 1, 8, 63, 336, 1295, 3096, 4095, 2160, 252, 0, 1, 9, 80, 504, 2400, 7735, 15624, 16320, 6552, 495, 0, 1, 10, 99
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,8
|
|
|
COMMENTS
|
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.
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n,k) = Sum_{d|n} k^(d-1) * mu(n/d).
T(n,k) = k^(n-1) - Sum_{d<n,d|n} T(d,k).
|
|
|
EXAMPLE
|
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.
Table begins:
1, 1, 1, 1, 1, 1, 1, 1, ...
0, 1, 2, 3, 4, 5, 6, 7, ...
0, 3, 8, 15, 24, 35, 48, 63, ...
0, 6, 24, 60, 120, 210, 336, 504, ...
0, 15, 80, 255, 624, 1295, 2400, 4095, ...
0, 27, 232, 1005, 3096, 7735, 16752, 32697, ...
0, 63, 728, 4095, 15624, 46655, 117648, 262143, ...
0, 120, 2160, 16320, 78000, 279720, 823200, 2096640, ...
|
|
|
MAPLE
|
with(numtheory):
f1:= proc(n) option remember;
unapply(k^(n-1)-add(f1(d)(k), d=divisors(n)minus{n}), k)
end;
T:= (n, k)-> f1(n)(k);
seq(seq(T(n, 1+d-n), n=1..d), d=1..12);
|
|
|
MATHEMATICA
|
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 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
