×

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.

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