login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A143325 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) which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet. 23
1, 1, 0, 1, 1, 0, 1, 2, 3, 0, 1, 3, 8, 6, 0, 1, 4, 15, 24, 15, 0, 1, 5, 24, 60, 80, 27, 0, 1, 6, 35, 120, 255, 232, 63, 0, 1, 7, 48, 210, 624, 1005, 728, 120, 0, 1, 8, 63, 336, 1295, 3096, 4095, 2160, 252, 0, 1, 9, 80, 504, 2400, 7735, 15624, 16320, 6552, 495, 0, 1, 10, 99 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,8

COMMENTS

Column k is Dirichlet convolution of mu(n) with k^(n-1). 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+k^3.

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-1) * mu(n/d).

T(n,k) = k^(n-1) - Sum_{d<n,d|n} T(d,k).

T(n,k) = A074650(n,k) * n/k.

T(n,k) = A143324(n,k) / k.

EXAMPLE

T(4,2)=6, because 6 words of length 4 over 2-letter alphabet {a,b} are primitive and earlier than others derived by cyclic shifts of the alphabet: aaab, aaba, aabb, abaa, abba, abbb; note that aaaa and abab are not primitive and words beginning with b can be derived by shifts of the alphabet from words in the list; secondly note that the words in the list need not be Lyndon words, for example aaba can be derived from aaab by a cyclic rotation of the positions.

Table begins:

  1,   1,    1,     1,     1,      1,      1,       1, ...

  0,   1,    2,     3,     4,      5,      6,       7, ...

  0,   3,    8,    15,    24,     35,     48,      63, ...

  0,   6,   24,    60,   120,    210,    336,     504, ...

  0,  15,   80,   255,   624,   1295,   2400,    4095, ...

  0,  27,  232,  1005,  3096,   7735,  16752,   32697, ...

  0,  63,  728,  4095, 15624,  46655, 117648,  262143, ...

  0, 120, 2160, 16320, 78000, 279720, 823200, 2096640, ...

MAPLE

with(numtheory):

f1:= proc(n) option remember;

       unapply(k^(n-1)-add(f1(d)(k), d=divisors(n)minus{n}), k)

     end;

T:= (n, k)-> f1(n)(k);

seq(seq(T(n, 1+d-n), n=1..d), d=1..12);

MATHEMATICA

t[n_, k_] := Sum[k^(d-1)*MoebiusMu[n/d], {d, Divisors[n]}]; Table[t[n-k+1, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Jan 21 2014, from first formula *)

CROSSREFS

Columns k=1-10 give: A063524, A000740, A034741, A295505, A295506, A320071, A320072, A320073, A320074, A320075.

Rows n=1-5, 7 give: A000012, A001477, A005563, A007531, A123865, A123866.

Main diagonal gives A075147.

Cf. A074650, A143324, A008683, A054525.

Sequence in context: A255961 A297328 A055137 * A307910 A128888 A305401

Adjacent sequences:  A143322 A143323 A143324 * A143326 A143327 A143328

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 26 05:10 EST 2020. Contains 331273 sequences. (Running on oeis4.)