OFFSET
1,5
COMMENTS
The number of set partitions of size n length k which are 'Lyndon,' that is, since all set partitions are isomorphic to sequences of atomic set partitions (A087903), those which are smallest of all rotations of these sequences in lex order (with respect to some ordering on the atomic set partitions) are Lyndon. 1; 1, 0; 1, 2, 0; 1, 5, 3, 0; 1, 13, 16, 4, 0;
LINKS
N. Bergeron, M. Zabrocki, The Hopf algebras of symmetric functions and quasisymmetric functions in non-commutative variables are free and cofree, arXiv:math/0509265 [math.CO], 2005.
M. Rosas and B. Sagan, Symmetric Functions in Noncommuting Variables, Transactions of the American Mathematical Society, 358 (2006), no. 1, 215-232.
M. C. Wolf, Symmetric functions for non-commutative elements, Duke Math. J., 2 (1936), 626-637.
EXAMPLE
There are 6 set partitions of size 4 and length 3, {12|3|4}, {13|2|4}, {14|2|3}, {1|23|4}, {1|24|3}, {1|2|34} and the sequences the correspond to are ({12},{1},{1}), ({13|2}, {1}), ({14|2|3}), ({1},{12},{1}), ({1},{13|2}), ({1},{1},{12}). Now there are three {({12},{1},{1}), ({1},{12},{1}), ({1},{1},{12})} that are rotations of each other and ({1}, {1}, {12}) is the smallest of these, {({13|2}, {1}), ({1},{13|2})} are rotations of each other and ({1},{13|2}) is the smallest and ({14|2|3}) is atomic and all atomic s.p. are Lyndon. Hence {1|2|34}, {1|24|3}, {14|2|3} are Lyndon and a(4,3) = 3
Triangle begins:
1;
1, 0;
1, 2, 0;
1, 5, 3, 0;
1, 13, 16, 4, 0;
1, 28, 67, 34, 5, 0;
...
MAPLE
EULERitable:=proc(tbl) local ser, out, i, j, tmp; ser:=1+add(add(q^i*t^j*tbl[i][j], j=1..nops(tbl[i])), i=1..nops(tbl)); out:=[]; for i from 1 to nops(tbl) do tmp:=coeff(ser, q, i); ser:=expand(ser*mul(add((-q^i*t^j)^k*choose(abs(coeff(tmp, t, j)), k), k=0..nops(tbl)/i), j = 1..degree(tmp, t))); ser:=subs({seq(q^j=0, j=nops(tbl)+1..degree(ser, q))}, ser); out:=[op(out), [seq(abs(coeff(tmp, t, j)), j=1..degree(tmp, t))]]; end do; out; end: EULERitable([seq([seq(combinat[stirling2](n, k), k=1..n)], n=1..10)]);
MATHEMATICA
nmax = 11; b[n_, k_] /; k < 1 || k > n = 0;
coes[m_] := Product[1/(1 - q^n t^k)^b[n, k], {n, 1, m}, {k, 1, m}] - 1 - Sum[ StirlingS2[i, j] q^i t^j, {i, 1, m}, {j, 1, m}] + O[t]^m + O[q]^m // Normal // CoefficientList[#, {t, q}]&;
sol[1] = {b[1, 1] -> 1};
Do[sol[m] = Solve[Thread[(coes[m] /. sol[m - 1]) == 0]], {m, 2, nmax + 1}];
bb = Flatten[Table[sol[m], {m, 1, nmax + 1}]];
Table[b[n, k] /. bb, {n, 1, nmax}, {k, 1, n}] // Flatten (* Jean-François Alcover, Dec 11 2017 *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Mike Zabrocki, Sep 05 2005; Aug 06 2006
STATUS
approved