The Mobius Function ofa Restricted Composition Poset

Abstract

We study a poset of compositions restricted by part size under a partial ordering introduced by Björner and Stanley. We show that our composition poset \(C_{n, k}\) is isomorphic to the poset of words \(A_{d}^{*}\). This allows us to use techniques developed by Björner to study the Möbius function of \(C_{d+1}\). We use counting arguments and shellability as avenues for proving that the Möbius function is \(\mu(u, w) = (-1)^{|u|+|w|}{\binom{w}{u}}_{dn}\), where \({\binom{w}{u}}_{dn}\) is the number of \(d\)-normal embeddings of \(u\) in \(w\). We then prove that the formal power series whose coefficients are given by the zeta and the Möbius functions are both rational. Following in the footsteps of Björner and Reutenauer and Björner and Sagan, we rely on definitions to prove rationality in one case, and in another case we use finite-state automata.