login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A110540 Invertible triangle: T(n,k) = number of k-ary Lyndon words of length n-k+1 with trace 1 modulo k. 1
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 (list; table; graph; refs; listen; history; text; internal format)
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 * A339071 A083475 A211994

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 30 07:58 EDT 2021. Contains 346348 sequences. (Running on oeis4.)