A124814 Triangle of number of 4-ary Lyndon words of length n containing exactly k 1s.

1, 3, 1, 3, 3, 0, 8, 9, 3, 0, 18, 27, 12, 3, 0, 48, 81, 54, 18, 3, 0, 116, 243, 198, 89, 21, 3, 0, 312, 729, 729, 405, 135, 27, 3, 0, 810, 2187, 2538, 1701, 702, 189, 30, 3, 0, 2184, 6561, 8748, 6801, 3402, 1134, 251, 36, 3, 0, 5880, 19683, 29484, 26244, 15282, 6123, 1692

Offset: 0

Author

Mike Zabrocki, Nov 08 2006

Keywords

• nonn
• tabl

Comments

Row sums given by A027377, first column given by A027376, second column given by A000244, third through sixth columns (k=2,3,4,5) given by A124810, A124811, A124812, A124813, third diagonal given by 3*A032766.

Examples

			T(4,2) = 12 because the words 11ab, 11ba, 1a1b for ab=23, 24, 34 and 11aa for a=2,3,4 are all Lyndon and of length 4 with exactly two 1s.
From _Andrew Howroyd_, Mar 26 2017: (Start)
Triangle starts
*   1
*   3    1
*   3    3    0
*   8    9    3    0
*  18   27   12    3   0
*  48   81   54   18   3   0
* 116  243  198   89  21   3  0
* 312  729  729  405 135  27  3 0
* 810 2187 2538 1701 702 189 30 3 0
(End)
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1274

Crossrefs

Cf. A051168, A123223, A027377, A124810, A124811, A124812, A124813.

Programs

Maple

C:=combinat[numbcomb]:mu:=numtheory[mobius]:divs:=numtheory[divisors]: T:=proc(n,k) local d; if k>0 then add(mu(d)*C(n/d-1,(n-k)/d)*3^((n-k)/d),d=divs(n) intersect divs(k))/k; elif n>0 then 1/n*add(mu(d)*3^(n/d),d=divs(n)); else 1; fi; end; [seq([seq(T(n,k),k=0..n)],n=0..10)];

Mathematica

nmax = 10; col[0] = Table[If[n == 0, 1, 1/n* DivisorSum[n, MoebiusMu[#]* 3^(n/#)&]], {n, 0, nmax}]; col[k_] := x^k/k * DivisorSum[k, MoebiusMu[#] / (1 - 3*x^#)^(k/#)&] + O[x]^(nmax+2) // CoefficientList[#, x]&; Table[ col[k][[n+1]], {n, 0, nmax}, {k, 0, n}] // Flatten (* Jean-François Alcover, Sep 19 2017 *)

Formula

T(n,0) = 1/n*Sum_{d|n} mu(d)*3^(n/d) = A027376(n).

T(n,n-1) = 3 for k>0.

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

O.g.f. of columns: Sum_n T(n,k) x^n = x^k/k*Sum_{d|k} mu(d)*1/(1-3*x^d)^(k/d).

O.g.f. of diagonals: Sum_n T(n,n-k) x^n = x^k/k*Sum_{d|k} mu(d)*(3/(1-x^d))^(k/d).