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

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, 30, 12, 3, 1, 0, 16, 104, 170, 125, 54, 16, 4, 1, 0, 28, 270, 585, 516, 259, 84, 21, 4, 1, 0, 51, 729, 2048, 2232, 1296, 480, 128, 27, 5, 1, 0, 93, 1960, 7280, 9750, 6665, 2792, 819

Offset

1,12

Comments

An invertible number triangle related to Lyndon words of trace 1.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275

F. Ruskey, Number of q-ary Lyndon words with given trace mod q

F. Ruskey, Number of monic irreducible polynomials over GF(q) with given trace

F. Ruskey, Number of Lyndon words over GF(q) with given trace

Formula

T(n, k) = Sum_{d | n-k+1, gcd(d, k)=1} mu(d)*k^((n-k+1)/d))/(k*(n-k+1)).

Example

Rows begin
  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, 30, 12, 3, 1;

Mathematica

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

Prog

(PARI)
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

Crossrefs

Columns include A000048, A046211, A054660, A054662, A054666.

Sequence in context: A108619 A091327 A327758 * A346399 A339071 A358478

Adjacent sequences: A110537 A110538 A110539 * A110541 A110542 A110543

Keyword

easy,nonn,tabl

Author

Paul Barry, Jul 25 2005

Extensions

Name clarified by Andrew Howroyd, Mar 26 2017

Status

approved