A342908 Irregular triangular array of coefficients of the cd-index of the symmetric group S_n (or Boolean algebra B_n), n>=1.

1, 1, 1, 1, 1, 2, 2, 1, 3, 5, 3, 4, 1, 4, 9, 9, 4, 12, 10, 12, 1, 5, 14, 19, 14, 5, 25, 35, 42, 18, 35, 25, 34, 1, 6, 20, 34, 34, 20, 6, 44, 84, 100, 72, 140, 100, 28, 72, 84, 44, 136, 112, 112, 136, 1, 7, 27, 55, 69, 55, 27, 7, 70, 168, 198, 196, 378, 268, 126, 324, 378, 198, 40, 126, 196, 168, 70, 364, 504, 504, 612, 256, 420, 504, 256, 504, 364, 496

Offset

1,6

Comments

Equivalently, the cd-index of the face lattice of the (n-1)-dimensional simplex.

These polynomials encode the numbers given in A335845. The row lengths are A000045(n). The row sums are A000111(n).

References

R. P. Stanley, Enumerative Combinatorics, Vol I, second edition, page 54 and section 3.17.

Links

Table of n, a(n) for n=1..88.

Margaret M. Bayer, The cd-Index: A Survey, arXiv:1901.04939 [math.CO], 2019.

Example

  1,
  1,
  1, 1,
  1, 2,  2,
  1, 3,  5,  3,  4,
  1, 4,  9,  9,  4, 12, 10, 12,
  1, 5, 14, 19, 14,  5, 25, 35, 42, 18, 35, 25, 34
The terms of the polynomials are ordered lexicographically.  For example, row 5 represents the polynomial: c^4 + 3c^2d + 5cdc + 3dc^2 + 4d^2.

Mathematica

Join[{{1}}, Table[h[list_]:=(-1)^(Length[list]+1)Apply[Multinomial, list]; g[S_]:=Abs[Total[Map[h, Map[Differences, Map[Prepend[#, 0]&, Map[Append[#, nn]&, Subsets[S]]]]]]]; rhs=Drop[Map[g, Subsets[Range[nn-1]]], -2^(nn-2)]; Clear[c, d]; fib=Reverse[Map[#/.{2->d, 1->c}&, Level[Map[Permutations, IntegerPartitions[nn-1, nn-1, {1, 2}]], {2}]]]; c:={{a}, {b}}; d:={{a, b}, {b, a}}; f[list1_, list2_]:=Level[Table[Table[Join[list1[[i]], list2[[k]]], {i, 1, Length[list1]}], {k, 1, Length[list2]}], {2}]; rr=Table[Map[Fold[f, #[[1]], Rest[#]]&, fib][[i]]->Subscript[x, i], {i, 1, Fibonacci[nn]}]; eqn[list_]:=Total[Select[Map[Fold[f, #[[1]], Rest[#]]&, fib], MemberQ[#, list]&]/.rr]==FromDigits[Part[rhs, Flatten[Position[charmon=Drop[Map[Table[If[MemberQ[#, i], b, a], {i, 1, nn-1}]&, Subsets[Range[nn-1]]], -2^(nn-2)], list]]]]; charmon=Drop[Map[Table[If[MemberQ[#, i], b, a], {i, 1, nn-1}]&, Subsets[Range[nn-1]]], -2^(nn-2)]; Table[Subscript[x, i], {i, 1, Fibonacci[nn]}]/.Flatten[Solve[Map[eqn[#]&, charmon]]], {nn, 2, 10}]]//Flatten

Crossrefs

Cf. A000045, A000111, A335845.

Sequence in context: A106198 A202847 A054336 * A284644 A079956 A140717

Adjacent sequences: A342905 A342906 A342907 * A342909 A342910 A342911

Keyword

nonn,tabf

Author

Geoffrey Critzer, Mar 28 2021

Status

approved