|
| |
|
|
A124814
|
|
Triangle of number of 4-ary Lyndon words of length n containing exactly k 1s.
|
|
6
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
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.
|
|
|
LINKS
|
|
|
|
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).
|
|
|
EXAMPLE
|
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.
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)
|
|
|
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 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
