cp's OEIS Frontend

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

%I A143324 #48 Nov 05 2024 10:47:32
%S A143324 1,2,0,3,2,0,4,6,6,0,5,12,24,12,0,6,20,60,72,30,0,7,30,120,240,240,54,
%T A143324 0,8,42,210,600,1020,696,126,0,9,56,336,1260,3120,4020,2184,240,0,10,
%U A143324 72,504,2352,7770,15480,16380,6480,504,0,11,90,720,4032,16800,46410,78120,65280,19656,990,0
%N A143324 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).
%C A143324 Column k is Dirichlet convolution of mu(n) with k^n.
%C A143324 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^2+k^4.
%H A143324 Alois P. Heinz, <a href="/A143324/b143324.txt">Antidiagonals n = 1..141, flattened</a>
%H A143324 C. J. Smyth, <a href="http://www.math.stonybrook.edu/~moira/mat331-spr10/papers/1986%20SmythA%20Coloring%20Proof%20of%20a.pdf">A coloring proof of a generalisation of Fermat's little theorem</a>, Amer. Math. Monthly 93, No. 6 (1986), pp. 469-471.
%H A143324 Lucas Vieira Barbosa, <a href="https://doi.org/10.25365/thesis.76733">Nonclassical Temporal Correlations Under Finite-Memory Constraints</a>, Doctoral Thesis, Univ. Wien (Austria 2024). See p. 35.
%H A143324 <a href="/index/Lu#Lyndon">Index entries for sequences related to Lyndon words</a>
%F A143324 T(n,k) = Sum_{d|n} k^d * mu(n/d).
%F A143324 T(n,k) = k^n - Sum_{d<n,d|n} T(d,k).
%F A143324 T(n,k) = A143325(n,k) * k.
%F A143324 T(n,k) = A074650(n,k) * n.
%F A143324 So Sum_{d|n} k^d * mu(n/d) == 0 (mod n), this is a generalization of Fermat's little theorem k^p - k == 0 (mod p) for primes p to an arbitrary modulus n (see the Smyth link). - _Franz Vrabec_, Feb 09 2021
%e A143324 T(2,3)=6, because there are 6 primitive words of length 2 over 3-letter alphabet {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 A143324 Table begins:
%e A143324   1,  2,   3,    4,    5, ...
%e A143324   0,  2,   6,   12,   20, ...
%e A143324   0,  6,  24,   60,  120, ...
%e A143324   0, 12,  72,  240,  600, ...
%e A143324   0, 30, 240, 1020, 3120, ...
%p A143324 with(numtheory): f0:= proc(n) option remember; unapply(k^n-add(f0(d)(k), d=divisors(n)minus{n}), k) end; T:= (n,k)-> f0(n)(k); seq(seq(T(n, 1+d-n), n=1..d), d=1..12);
%t A143324 f0[n_] := f0[n] = Function [k, k^n - Sum[f0[d][k], {d, Complement[Divisors[n], {n}]}]]; t[n_, k_] := f0[n][k]; Table[Table[t[n, 1 + d - n], {n, 1, d}], {d, 1, 12}] // Flatten (* _Jean-François Alcover_, Dec 12 2013, translated from Maple *)
%Y A143324 Columns k=1-10 give: A000007(n-1), A027375, A054718, A054719, A054720, A054721, A218124, A218125, A218126, A218127.
%Y A143324 Rows n=1-10 give: A000027, A002378(k-1), A007531(k+1), A047928(k+1), A061167, A218130, A133499, A218131, A218132, A218133.
%Y A143324 Main diagonal gives A252764.
%Y A143324 Cf. A074650, A143325, A008683, A054525.
%K A143324 nonn,tabl
%O A143324 1,2
%A A143324 _Alois P. Heinz_, Aug 07 2008