The Möbius function of generalized factor order

We use discrete Morse theory to determine the Möbius function of generalized factor order. Ordinary factor order on the Kleene closure A∗ of a set A is the partial order defined by letting u≤w if w contains u as a subsequence of consecutive letters. Generalized factor order takes into account a partial order PA on the alphabet A, that is, u≤w whenever w contains a subsequence w(i+1)⋯w(i+|u|) such that for each j, u(j)≤w(i+j) in A. Using Babson and Hersh's application of Robin Forman's discrete Morse theory to poset order complexes, we are able to give a recursive formula for the Möbius function in the case where each element of A covers a unique letter in PA.