A124814 - OEIS

%I #14 Sep 19 2017 10:23:50

%S 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,

%T 0,312,729,729,405,135,27,3,0,810,2187,2538,1701,702,189,30,3,0,2184,

%U 6561,8748,6801,3402,1134,251,36,3,0,5880,19683,29484,26244,15282,6123,1692

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

%C 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.

%H Andrew Howroyd, <a href="/A124814/b124814.txt">Table of n, a(n) for n = 0..1274</a>

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

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

%F 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).

%F 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).

%F 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).

%e 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.

%e From _Andrew Howroyd_, Mar 26 2017: (Start)

%e Triangle starts

%e *   1

%e *   3    1

%e *   3    3    0

%e *   8    9    3    0

%e *  18   27   12    3   0

%e *  48   81   54   18   3   0

%e * 116  243  198   89  21   3  0

%e * 312  729  729  405 135  27  3 0

%e * 810 2187 2538 1701 702 189 30 3 0

%e (End)

%p 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)];

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

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

%K nonn,tabl

%O 0,2

%A _Mike Zabrocki_, Nov 08 2006