login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 18
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; text; 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

Alois P. Heinz, Antidiagonals n = 1..141, flattened

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(n, 1+d-n), n=1..d), d=1..12);

MATHEMATICA

f0[n_] := f0[n] = Function [k, k^n - Sum[f0[d][k], {d, Complement[Divisors[n], {n}]}]]; t[n_, k_] := f0[n][k]; Table[Table[t[n, 1 + d - n], {n, 1, d}], {d, 1, 12}] // Flatten (* Jean-Fran├žois Alcover, Dec 12 2013, translated from Maple *)

CROSSREFS

Columns k=1-10 give: A000007(n-1), A027375, A054718, A054719, A054720, A054721, A218124, A218125, A218126, A218127.

Rows n=1-10 give: A000027, A002378(k-1), A007531(k+1), A047928(k+1), A061167, A218130, A133499, A218131, A218132, A218133.

Cf. 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, Aug 07 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified April 19 08:09 EDT 2014. Contains 240739 sequences.