cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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.

This page as a plain text file.
%I A143325 #26 Oct 05 2018 10:14:14
%S A143325 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,
%T A143325 35,120,255,232,63,0,1,7,48,210,624,1005,728,120,0,1,8,63,336,1295,
%U A143325 3096,4095,2160,252,0,1,9,80,504,2400,7735,15624,16320,6552,495,0,1,10,99
%N 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.
%C A143325 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.
%H A143325 Alois P. Heinz, <a href="/A143325/b143325.txt">Antidiagonals n = 1..141, flattened</a>
%H A143325 <a href="/index/Lu#Lyndon">Index entries for sequences related to Lyndon words</a>
%F A143325 T(n,k) = Sum_{d|n} k^(d-1) * mu(n/d).
%F A143325 T(n,k) = k^(n-1) - Sum_{d<n,d|n} T(d,k).
%F A143325 T(n,k) = A074650(n,k) * n/k.
%F A143325 T(n,k) = A143324(n,k) / k.
%e A143325 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.
%e A143325 Table begins:
%e A143325   1,   1,    1,     1,     1,      1,      1,       1, ...
%e A143325   0,   1,    2,     3,     4,      5,      6,       7, ...
%e A143325   0,   3,    8,    15,    24,     35,     48,      63, ...
%e A143325   0,   6,   24,    60,   120,    210,    336,     504, ...
%e A143325   0,  15,   80,   255,   624,   1295,   2400,    4095, ...
%e A143325   0,  27,  232,  1005,  3096,   7735,  16752,   32697, ...
%e A143325   0,  63,  728,  4095, 15624,  46655, 117648,  262143, ...
%e A143325   0, 120, 2160, 16320, 78000, 279720, 823200, 2096640, ...
%p A143325 with(numtheory):
%p A143325 f1:= proc(n) option remember;
%p A143325        unapply(k^(n-1)-add(f1(d)(k), d=divisors(n)minus{n}), k)
%p A143325      end;
%p A143325 T:= (n,k)-> f1(n)(k);
%p A143325 seq(seq(T(n, 1+d-n), n=1..d), d=1..12);
%t A143325 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 *)
%Y A143325 Columns k=1-10 give: A063524, A000740, A034741, A295505, A295506, A320071, A320072, A320073, A320074, A320075.
%Y A143325 Rows n=1-5, 7 give: A000012, A001477, A005563, A007531, A123865, A123866.
%Y A143325 Main diagonal gives A075147.
%Y A143325 Cf. A074650, A143324, A008683, A054525.
%K A143325 nonn,tabl
%O A143325 1,8
%A A143325 _Alois P. Heinz_, Aug 07 2008