|
| |
|
|
A143326
|
|
Table T(n,k) by antidiagonals. T(n,k) is the number of primitive (=aperiodic) k-ary words with length less than or equal to n (n,k >= 1).
|
|
11
|
|
|
|
1, 2, 1, 3, 4, 1, 4, 9, 10, 1, 5, 16, 33, 22, 1, 6, 25, 76, 105, 52, 1, 7, 36, 145, 316, 345, 106, 1, 8, 49, 246, 745, 1336, 1041, 232, 1, 9, 64, 385, 1506, 3865, 5356, 3225, 472, 1, 10, 81, 568, 2737, 9276, 19345, 21736, 9705, 976, 1, 11, 100, 801, 4600, 19537, 55686
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
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 -k+k^3+k^4.
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n,k) = Sum_{1<=j<=n} Sum_{d|j} k^d * mu(j/d).
T(n,k) = Sum_{1<=j<=n} A143324(j,k).
|
|
|
EXAMPLE
|
T(2,3) = 9, because there are 9 primitive words of length less than or equal to 2 over 3-letter alphabet {a,b,c}: a, b, c, ab, ac, ba, bc, ca, cb; note that the non-primitive words aa, bb and cc don't belong to the list; secondly note that the words in the list need not be Lyndon words, for example ba can be derived from ab by a cyclic rotation of the positions.
Table begins:
1, 2, 3, 4, 5, 6, 7, 8, ...
1, 4, 9, 16, 25, 36, 49, 64, ...
1, 10, 33, 76, 145, 246, 385, 568, ...
1, 22, 105, 316, 745, 1506, 2737, 4600, ...
1, 52, 345, 1336, 3865, 9276, 19537, 37360, ...
1, 106, 1041, 5356, 19345, 55686, 136801, 298936, ...
1, 232, 3225, 21736, 97465, 335616, 960337, 2396080, ...
1, 472, 9705, 87016, 487465, 2013936, 6722737, 19169200, ...
...
The triangle Tri(n,m) := T(m,n-(m-1)) begins:
n\m 1 2 3 4 5 6 7 8 9 10 ...
1: 1
2: 2 1
3: 3 4 1
4: 4 9 10 1
5: 5 16 33 22 1
6: 6 25 76 105 52 1
7: 7 36 145 316 345 106 1
8: 8 49 246 745 1336 1041 232 1
9: 9 64 385 1506 3865 5356 3225 472 1
10: 10 81 568 2737 9276 19345 21736 9705 976 1
...
|
|
|
MAPLE
|
with(numtheory):
f0:= proc(n) option remember;
unapply(k^n-add(f0(d)(k), d=divisors(n) minus {n}), k)
end:
g0:= proc(n) option remember; unapply(add(f0(j)(x), j=1..n), x) end:
T:= (n, k)-> g0(n)(k):
seq(seq(T(n, 1+d-n), n=1..d), d=1..12);
|
|
|
MATHEMATICA
|
f0[n_] := f0[n] = Function[k, k^n-Sum[f0[d][k], {d, Divisors[n] // Most}]]; g0[n_] := g0[n] = Function[x, Sum[f0[j][x], {j, 1, n}]]; T[n_, k_] := g0[n][k]; Table[T[n, 1+d-n], {d, 1, 12}, {n, 1, d}]//Flatten (* Jean-François Alcover, Feb 12 2014, translated from Maple *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
