cp's OEIS Frontend

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

%I A143326 #34 Oct 04 2018 20:35:57
%S A143326 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,
%T A143326 106,1,8,49,246,745,1336,1041,232,1,9,64,385,1506,3865,5356,3225,472,
%U A143326 1,10,81,568,2737,9276,19345,21736,9705,976,1,11,100,801,4600,19537,55686
%N 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).
%C A143326 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.
%H A143326 Alois P. Heinz, <a href="/A143326/b143326.txt">Antidiagonals n = 1..141, flattened</a>
%H A143326 <a href="/index/Lu#Lyndon">Index entries for sequences related to Lyndon words</a>
%F A143326 T(n,k) = Sum_{1<=j<=n} Sum_{d|j} k^d * mu(j/d).
%F A143326 T(n,k) = Sum_{1<=j<=n} A143324(j,k).
%F A143326 T(n,k) = A143327(n,k) * k.
%e A143326 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.
%e A143326 Table begins:
%e A143326   1,   2,    3,     4,      5,       6,       7,        8, ...
%e A143326   1,   4,    9,    16,     25,      36,      49,       64, ...
%e A143326   1,  10,   33,    76,    145,     246,     385,      568, ...
%e A143326   1,  22,  105,   316,    745,    1506,    2737,     4600, ...
%e A143326   1,  52,  345,  1336,   3865,    9276,   19537,    37360, ...
%e A143326   1, 106, 1041,  5356,  19345,   55686,  136801,   298936, ...
%e A143326   1, 232, 3225, 21736,  97465,  335616,  960337,  2396080, ...
%e A143326   1, 472, 9705, 87016, 487465, 2013936, 6722737, 19169200, ...
%e A143326   ...
%e A143326 From _Wolfdieter Lang_, Feb 01 2014: (Start)
%e A143326 The triangle Tri(n,m) := T(m,n-(m-1)) begins:
%e A143326 n\m  1   2    3     4     5      6      7     8    9  10 ...
%e A143326 1:   1
%e A143326 2:   2   1
%e A143326 3:   3   4    1
%e A143326 4:   4   9   10     1
%e A143326 5:   5  16   33    22     1
%e A143326 6:   6  25   76   105    52      1
%e A143326 7:   7  36  145   316   345    106      1
%e A143326 8:   8  49  246   745  1336   1041    232     1
%e A143326 9:   9  64  385  1506  3865   5356   3225   472    1
%e A143326 10: 10  81  568  2737  9276  19345  21736  9705  976   1
%e A143326 ...
%e A143326 For the columns see A000027, A000290, A081437, ... (End)
%p A143326 with(numtheory):
%p A143326 f0:= proc(n) option remember;
%p A143326        unapply(k^n-add(f0(d)(k), d=divisors(n) minus {n}), k)
%p A143326      end:
%p A143326 g0:= proc(n) option remember; unapply(add(f0(j)(x), j=1..n), x) end:
%p A143326 T:= (n, k)-> g0(n)(k):
%p A143326 seq(seq(T(n, 1+d-n), n=1..d), d=1..12);
%t A143326 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 *)
%Y A143326 Column 1: A000012. Rows 1-3: A000027, A000290, A081437 and A085490. See also A143324, A143327, A134541, A008683.
%K A143326 nonn,tabl
%O A143326 1,2
%A A143326 _Alois P. Heinz_, Aug 07 2008