Posets of shuffles
A poset of shuffles is defined as follows: Let \b{x}\(=x_ 1x_ 2...x_ m\) and \b{y}\(=y_ 1y_ 2...y_ m\) be words, where it is assumed that the letters occurring in \b{x} and \b{y} are all distinct. Let \(W_{\underline x,\underline y}\) denote the set of all words \b{w} with letters from \b{x} and \b{y} such that the restriction of \b{w} to the letters of \b{x} resp. of \b{y} is a subword of \b{x} resp. of \b{y}. \(W_{\underline x,\underline y}\) becomes a poset if one defines \b{w}\(\leq \underline w'\) if and only if \b{w}' can be obtained from \b{w} by deleting letters of \b{x} and adding letters of \b{y}. The author establishes a lot of nice properties of this poset, for example, \(W_{\underline x,\underline y}\) is a lattice with rank function, it possesses a symmetric chain decomposition and it is supersolvable. Furthermore he derives formulas and generating functions for many combinatorial invariants such as the number of elements, the rank generating function, the number of maximal chains, the Möbius function, the zeta polynomial and the characteristic polynomial. All these invariants can be expressed in a simple way using evaluations of a certain family of polynomials which are related to classical Jacobi polynomials. The key idea for the proof of many facts is a certain canonical decomposition of \(W_{\underline x,\underline y}\) into Boolean sublattices, where the words \b{w} are classified with respect to their interface, i.e. the set of all letters x, y, where \(x\in \underline x\) and \(y\in \underline y\), and x immediately follows y in \b{w}.
generating functions for combinatorial invariants
scientific article; zbMATH DE number 4077288