A143327 Table T(n,k) by antidiagonals. T(n,k) is the number of primitive (=aperiodic) k-ary words (n,k >= 1) with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

1, 1, 1, 1, 2, 1, 1, 3, 5, 1, 1, 4, 11, 11, 1, 1, 5, 19, 35, 26, 1, 1, 6, 29, 79, 115, 53, 1, 1, 7, 41, 149, 334, 347, 116, 1, 1, 8, 55, 251, 773, 1339, 1075, 236, 1, 1, 9, 71, 391, 1546, 3869, 5434, 3235, 488, 1, 1, 10, 89, 575, 2791, 9281, 19493, 21754, 9787, 983, 1, 1, 11

Offset: 1

Author

Alois P. Heinz, Aug 07 2008

Keywords

• nonn
• tabl

Comments

The coefficients of the polynomial of row n are given by the n-th row of triangle A134541; for example row 4 has polynomial -1+k^2+k^3.

Examples

			T(3,3) = 11, because 11 words of length <=3 over 3-letter alphabet {a,b,c} are primitive and earlier than others derived by cyclic shifts of the alphabet: a, ab, ac, aab, aac, aba, abb, abc, aca, acb, acc.
Table begins:
  1,   1,    1,     1,     1,      1,      1,       1, ...
  1,   2,    3,     4,     5,      6,      7,       8, ...
  1,   5,   11,    19,    29,     41,     55,      71, ...
  1,  11,   35,    79,   149,    251,    391,     575, ...
  1,  26,  115,   334,   773,   1546,   2791,    4670, ...
  1,  53,  347,  1339,  3869,   9281,  19543,   37367, ...
  1, 116, 1075,  5434, 19493,  55936, 137191,  299510, ...
  1, 236, 3235, 21754, 97493, 335656, 960391, 2396150, ...
		

Links

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

Crossrefs

Columns k=1-10 give: A000012, A085945, A320087, A320088, A320089, A320090, A320091, A320092, A320093, A320094.

Rows n=1-4 give: A000012, A000027, A028387, A003777.

Main diagonal gives A320095.

Cf. A143325, A143326, A134541, A008683.

Programs

Maple

with(numtheory):
f1:= proc (n) option remember; unapply(k^(n-1)
        -add(f1(d)(k), d=divisors(n) minus {n}), k)
     end:
g1:= proc(n) option remember; unapply(add(f1(j)(x), j=1..n), x) end:
T:= (n, k)-> g1(n)(k):
seq(seq(T(n, 1+d-n), n=1..d), d=1..12);

Mathematica

t[n_, k_] := Sum[k^(d-1)*MoebiusMu[j/d], {j, 1, n}, {d, Divisors[j]}]; Table[t[n-k+1, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Dec 13 2013 *)

Formula

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

T(n,k) = Sum_{j=1..n} A143325(j,k).

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