# 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
##### Keywords:
subword order; free monoid; Möbius function; dual CL-shellable