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

 

Logo

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

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). 19
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, 65280, 19656, 990, 0 (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.

Main diagonal gives A252764.

Cf. A074650, A143325, A008683, A054525.

Sequence in context: A115241 A154559 A269133 * A097418 A154752 A271868

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 | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 10 21:23 EST 2016. Contains 279011 sequences.