Björner, Anders 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. Reviewer: J.Neggers (Tuscaloosa) Cited in 4 ReviewsCited in 14 Documents MSC: 06A11 Algebraic aspects of posets 68R15 Combinatorics on words 05A99 Enumerative combinatorics Keywords:subword order; free monoid; Möbius function; dual CL-shellable PDF BibTeX XML