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.

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

Offset: 1

Author

Alois P. Heinz, Aug 07 2008

Keywords

• nonn
• tabl

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.

Examples

			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, ...
		

Links

• Alois P. Heinz, Antidiagonals n = 1..141, flattened
• Index entries for sequences related to Lyndon words

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.

Programs

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 *)

Formula

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

T(n,k) = k^(n-1) - Sum_{d

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

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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

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