cp's OEIS Frontend

A110540 Invertible triangle: T(n,k) = number of k-ary Lyndon words of length n-k+1 with trace 1 modulo k.

%I A110540 #52 Sep 05 2024 08:09:04
%S A110540 1,0,1,0,1,1,0,1,1,1,0,2,3,2,1,0,3,6,5,2,1,0,5,16,16,8,3,1,0,9,39,51,
%T A110540 30,12,3,1,0,16,104,170,125,54,16,4,1,0,28,270,585,516,259,84,21,4,1,
%U A110540 0,51,729,2048,2232,1296,480,128,27,5,1,0,93,1960,7280,9750,6665,2792,819,180,33,5,1
%N A110540 Invertible triangle: T(n,k) = number of k-ary Lyndon words of length n-k+1 with trace 1 modulo k.
%C A110540 An invertible number triangle related to Lyndon words of trace 1.
%H A110540 Andrew Howroyd, <a href="/A110540/b110540.txt">Table of n, a(n) for n = 1..1275</a>
%H A110540 Frank Ruskey, <a href="http://combos.org/TSlyndon">Number of q-ary Lyndon words with given trace mod q</a>
%H A110540 Frank Ruskey, <a href="http://combos.org/Tpoly">Number of monic irreducible polynomials over GF(q) with given trace</a>
%H A110540 Frank Ruskey, <a href="http://combos.org/TlyndonFk">Number of Lyndon words over GF(q) with given trace</a>
%F A110540 T(n, k) = (Sum_{d | n-k+1, gcd(d, k)=1} mu(d)*k^((n-k+1)/d))/(k*(n-k+1)).
%e A110540 Rows begin
%e A110540   1;
%e A110540   0,  1;
%e A110540   0,  1,   1;
%e A110540   0,  1,   1,    1;
%e A110540   0,  2,   3,    2,    1;
%e A110540   0,  3,   6,    5,    2,    1;
%e A110540   0,  5,  16,   16,    8,    3,   1;
%e A110540   0,  9,  39,   51,   30,   12,   3,   1;
%e A110540   0, 16, 104,  170,  125,   54,  16,   4,  1;
%e A110540   0, 28, 270,  585,  516,  259,  84,  21,  4, 1;
%e A110540   0, 51, 729, 2048, 2232, 1296, 480, 128, 27, 5, 1;
%t A110540 T[n_, k_]:=Sum[Boole[GCD[d, k] == 1]  MoebiusMu[d] k^((n - k + 1)/d), {d, Divisors[n - k + 1]}] /(k(n - k + 1)); Flatten[Table[T[n, k], {n, 12}, {k, n}]] (* _Indranil Ghosh_, Mar 27 2017 *)
%o A110540 (PARI)
%o A110540 for(n=1, 11, for(k=1, n, print1( sum(d=1,n-k+1, if(Mod(n-k+1, d)==0 && gcd(d, k)==1, moebius(d)*k^((n-k+1)/d), 0)/(k*(n-k+1)) ),", ");); print();) \\ _Andrew Howroyd_, Mar 26 2017
%Y A110540 Columns include A000048, A046211, A054660, A054662, A054666, A373277, A300674, A300675.
%K A110540 easy,nonn,tabl
%O A110540 1,12
%A A110540 _Paul Barry_, Jul 25 2005
%E A110540 Name clarified by _Andrew Howroyd_, Mar 26 2017