A289978 Triangle read by rows: the multiset transform of the balanced binary Lyndon words (A022553).
1, 0, 1, 0, 1, 1, 0, 3, 1, 1, 0, 8, 4, 1, 1, 0, 25, 11, 4, 1, 1, 0, 75, 39, 12, 4, 1, 1, 0, 245, 124, 42, 12, 4, 1, 1, 0, 800, 431, 138, 43, 12, 4, 1, 1, 0, 2700, 1470, 490, 141, 43, 12, 4, 1, 1, 0, 9225, 5160, 1704, 504, 142, 43, 12, 4, 1, 1, 0, 32065, 18160, 6088, 1763, 507, 142, 43, 12, 4, 1, 1
Offset: 0
Examples
The triangle begins in row 0 and column 0 as: 1; 0 1; 0 1 1; 0 3 1 1; 0 8 4 1 1; 0 25 11 4 1 1; 0 75 39 12 4 1 1; 0 245 124 42 12 4 1 1; 0 800 431 138 43 12 4 1 1; 0 2700 1470 490 141 43 12 4 1 1; 0 9225 5160 1704 504 142 43 12 4 1 1; 0 32065 18160 6088 1763 507 142 43 12 4 1 1; 0 112632 64765 21790 6337 1777 508 142 43 12 4 1 1; 0 400023 232347 78845 22798 6396 1780 508 142 43 12 4 1 1; 0 1432613 840285 286652 82941 23047 6410 1781 508 142 43 12 4 1 1;
Links
- Alois P. Heinz, Rows n = 0..140, flattened
- K. T. Chen, R. T. Fox and R. C. Lyndon, Free differential calculus IV. The quotient groups of the lower central series, Ann. Math. 68 (1) (1958) 81-95.
- J.-P. Duval, Factorizing words over an ordered Alphabet, J. Algorithms 4 (4) (1983) 363.
- R. J. Mathar, A bijection of Dyck Paths and multisets of Balanced Binary Lyndon Words (2021)
- Index entries for sequences related to Lyndon words
- Index entries for triangles generated by the Multiset Transformation
Programs
-
Maple
with(numtheory): g:= proc(n) option remember; `if`(n=0, 1, add( mobius(n/d)*binomial(2*d, d), d=divisors(n))/(2*n)) end: b:= proc(n, i, p) option remember; `if`(p>n, 0, `if`(n=0, 1, `if`(min(i, p)<1, 0, add(binomial(g(i)+j-1, j)* b(n-i*j, i-1, p-j), j=0..min(n/i, p))))) end: T:= (n, k)-> b(n$2, k): seq(seq(T(n, k), k=0..n), n=0..14); # Alois P. Heinz, Jul 25 2017 -
Mathematica
g[n_]:=g[n]=If[n==0, 1, Sum[MoebiusMu[n/d] Binomial[2d, d], {d, Divisors[n]}]/(2n)]; b[n_, i_, p_]:=b[n, i, p]=If[p>n, 0, If[n==0, 1, If[Min[i, p]<1, 0, Sum[Binomial[g[i] + j - 1, j] b[n - i*j, i - 1, p - j], {j, 0, Min[n/i, p]}]]]]; Table[b[n, n, k], {n, 0, 14}, {k, 0, n}]//Flatten (* Indranil Ghosh, Aug 05 2017, after Maple code *) nn = 14; b[n_] := If[n==0, 1, Sum[MoebiusMu[n/d] Binomial[2d, d], {d, Divisors[n]}]/ (2n)]; CoefficientList[#, y]& /@ (Series[Product[1/(1 - y x^i)^b[i], {i, 1, nn}], {x, 0, nn}] // CoefficientList[#, x]&) // Flatten (* Jean-François Alcover, Oct 29 2021 *)
Formula
G.f.: Product_{j>=1} 1/(1-y*x^j)^A022553(j). - Alois P. Heinz, Jul 25 2017