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, 180, 33, 5, 1
Offset: 1
Examples
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; 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;
Links
- Andrew Howroyd, Table of n, a(n) for n = 1..1275
- Frank Ruskey, Number of q-ary Lyndon words with given trace mod q
- Frank Ruskey, Number of monic irreducible polynomials over GF(q) with given trace
- Frank Ruskey, Number of Lyndon words over GF(q) with given trace
Programs
-
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 *) -
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
Formula
T(n, k) = (Sum_{d | n-k+1, gcd(d, k)=1} mu(d)*k^((n-k+1)/d))/(k*(n-k+1)).
Extensions
Name clarified by Andrew Howroyd, Mar 26 2017
Comments