|
| |
|
|
A143324
|
|
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).
|
|
4
| |
|
|
1, 2, 0, 3, 2, 0, 4, 6, 6, 0, 5, 12, 24, 12, 0, 6, 20, 60, 72, 30, 0, 7, 30, 120, 240, 240, 54, 0, 8, 42, 210, 600, 1020, 696, 126, 0, 9, 56, 336, 1260, 3120, 4020, 2184, 240, 0, 10, 72, 504, 2352, 7770, 15480, 16380, 6480, 504, 0, 11, 90, 720, 4032, 16800, 46410, 78120
(list; table; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
COMMENTS
| Column k is Dirichlet convolution of mu(n) with k^n.
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^2+k^4.
|
|
|
LINKS
| Index entries for sequences related to Lyndon words
|
|
|
FORMULA
| T(n,k) = Sum_{d|n} k^d * mu(n/d).
T(n,k) = k^n - Sum_{d<n,d|n} T(d,k).
T(n,k) = A143325(n,k) * k.
T(n,k) = A074650(n,k) * n.
|
|
|
EXAMPLE
| T(2,3)=6, because there are 6 primitive words of length 2 over 3-letter alphabet {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 ...
0, 2, 6, 12, 20 ...
0, 6, 24, 60, 120 ...
0, 12, 72, 240, 600 ...
0, 30, 240, 1020, 3120 ...
|
|
|
MAPLE
| with (numtheory): f0 := proc (n) option remember; unapply (k^n-add(f0(d)(k), d=divisors(n)minus{n}), k) end; T := (n, k)-> f0(n)(k); seq (seq(T(i, d-i), i=1..d-1), d=2..13);
|
|
|
CROSSREFS
| Columns 1-6: A000007, A027375, A054718, A054719, A054720, A054721. Rows 1-5, 7: A000027, A002378, A007531, A047928, A061167, A133499. See also A074650, A143325, A008683, A054525.
Sequence in context: A141432 A115241 A154559 * A097418 A154752 A194354
Adjacent sequences: A143321 A143322 A143323 * A143325 A143326 A143327
|
|
|
KEYWORD
| nonn,tabl
|
|
|
AUTHOR
| Alois P. Heinz (heinz(AT)hs-heilbronn.de), Aug 07 2008
|
| |
|
|
