zbMATH — the first resource for mathematics

The Möbius function of subword order. (English) Zbl 0706.06007
Invariant theory and tableaux, Proc. Workshop, Minneapolis/MN (USA) 1988, IMA Vol. Math. Appl. 19, 118-124 (1990).
[For the entire collection see Zbl 0694.00010.]
If \(A^*\) is the free monoid on an alphabet A, \(| A| =n\), with empty word \(\lambda\), then \(\beta <\alpha\) if the word \(\beta\) is obtainable from \(\alpha\) by deleting letters, as in \(ac<aabc\). If \(| \beta | =k\) is the length of \(\beta\) and if \(\mu\) (\(\beta\),\(\alpha\)) is the Möbius function on \((A^*,\leq)\) then it is shown that (Theorem 2):
(i) \(\sum_{\alpha \in A^*}\mu (\beta,\alpha)t^{| \alpha |}=t^ k(1-t)/(1+(n-1)t)^{k+1};\)
(ii) \(\sum_{\alpha,\beta}\mu (\beta,\alpha)t^{| \alpha |}q^{| \beta |}=(1-t)/(1-(nq-n+1)t).\)
As a consequence of the proofs and the formulas obtained, the author demonstrates (Theorem 3) that every interval [\(\beta\),\(\alpha\) ] in \(A^*\) is dual CL-shellable, whence much further information concerning various structures associated with the poset may be obtained as a consequence of this fact. Some of these are discussed in ‘remarks’ while others are promised as part of related future publications to follow this elegant paper.

06A11 Algebraic aspects of posets
68R15 Combinatorics on words
05A99 Enumerative combinatorics