|
| |
|
|
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.
|
|
12
|
|
|
|
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, 7, 41, 149, 334, 347, 116, 1, 1, 8, 55, 251, 773, 1339, 1075, 236, 1, 1, 9, 71, 391, 1546, 3869, 5434, 3235, 488, 1, 1, 10, 89, 575, 2791, 9281, 19493, 21754, 9787, 983, 1, 1, 11
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
COMMENTS
|
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.
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n,k) = Sum_{j=1..n} Sum_{d|j} k^(d-1) * mu(j/d).
T(n,k) = Sum_{j=1..n} A143325(j,k).
|
|
|
EXAMPLE
|
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.
Table begins:
1, 1, 1, 1, 1, 1, 1, 1, ...
1, 2, 3, 4, 5, 6, 7, 8, ...
1, 5, 11, 19, 29, 41, 55, 71, ...
1, 11, 35, 79, 149, 251, 391, 575, ...
1, 26, 115, 334, 773, 1546, 2791, 4670, ...
1, 53, 347, 1339, 3869, 9281, 19543, 37367, ...
1, 116, 1075, 5434, 19493, 55936, 137191, 299510, ...
1, 236, 3235, 21754, 97493, 335656, 960391, 2396150, ...
|
|
|
MAPLE
|
with(numtheory):
f1:= proc (n) option remember; unapply(k^(n-1)
-add(f1(d)(k), d=divisors(n) minus {n}), k)
end:
g1:= proc(n) option remember; unapply(add(f1(j)(x), j=1..n), x) end:
T:= (n, k)-> g1(n)(k):
seq(seq(T(n, 1+d-n), n=1..d), d=1..12);
|
|
|
MATHEMATICA
|
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 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
