A143326 Table T(n,k) by antidiagonals. T(n,k) is the number of primitive (=aperiodic) k-ary words with length less than or equal to n (n,k >= 1).

1, 2, 1, 3, 4, 1, 4, 9, 10, 1, 5, 16, 33, 22, 1, 6, 25, 76, 105, 52, 1, 7, 36, 145, 316, 345, 106, 1, 8, 49, 246, 745, 1336, 1041, 232, 1, 9, 64, 385, 1506, 3865, 5356, 3225, 472, 1, 10, 81, 568, 2737, 9276, 19345, 21736, 9705, 976, 1, 11, 100, 801, 4600, 19537, 55686

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 -k+k^3+k^4.

Examples

			T(2,3) = 9, because there are 9 primitive words of length less than or equal to 2 over 3-letter alphabet {a,b,c}: 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,       6,       7,        8, ...
  1,   4,    9,    16,     25,      36,      49,       64, ...
  1,  10,   33,    76,    145,     246,     385,      568, ...
  1,  22,  105,   316,    745,    1506,    2737,     4600, ...
  1,  52,  345,  1336,   3865,    9276,   19537,    37360, ...
  1, 106, 1041,  5356,  19345,   55686,  136801,   298936, ...
  1, 232, 3225, 21736,  97465,  335616,  960337,  2396080, ...
  1, 472, 9705, 87016, 487465, 2013936, 6722737, 19169200, ...
  ...
From _Wolfdieter Lang_, Feb 01 2014: (Start)
The triangle Tri(n,m) := T(m,n-(m-1)) begins:
n\m  1   2    3     4     5      6      7     8    9  10 ...
1:   1
2:   2   1
3:   3   4    1
4:   4   9   10     1
5:   5  16   33    22     1
6:   6  25   76   105    52      1
7:   7  36  145   316   345    106      1
8:   8  49  246   745  1336   1041    232     1
9:   9  64  385  1506  3865   5356   3225   472    1
10: 10  81  568  2737  9276  19345  21736  9705  976   1
...
For the columns see A000027, A000290, A081437, ... (End)
		

Links

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

Crossrefs

Column 1: A000012. Rows 1-3: A000027, A000290, A081437 and A085490. See also A143324, A143327, A134541, A008683.

Programs

Maple

with(numtheory):
f0:= proc(n) option remember;
       unapply(k^n-add(f0(d)(k), d=divisors(n) minus {n}), k)
     end:
g0:= proc(n) option remember; unapply(add(f0(j)(x), j=1..n), x) end:
T:= (n, k)-> g0(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, Divisors[n] // Most}]]; g0[n_] := g0[n] = Function[x, Sum[f0[j][x], {j, 1, n}]]; T[n_, k_] := g0[n][k]; Table[T[n, 1+d-n], {d, 1, 12}, {n, 1, d}]//Flatten (* Jean-François Alcover, Feb 12 2014, translated from Maple *)

Formula

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

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

T(n,k) = A143327(n,k) * k.