Mathematics – Combinatorics
Scientific paper
2008-06-09
Mathematics
Combinatorics
16 pages, 3 figures, minor edits, to appear in Ars Combinatoria
Scientific paper
We study a poset of compositions restricted by part size under a partial ordering introduced by Bj\"{o}rner and Stanley. We show that our composition poset $C_{d+1}$ is isomorphic to the poset of words $A_d^*$. This allows us to use techniques developed by Bj\"{o}rner to study the M\"{o}bius function of $C_{d+1}$. We use counting arguments and shellability as avenues for proving that the M\"{o}bius function is $\mu(u,w)=(-1)^{|u|+|w|}{w\choose u}_{dn}$, where ${w\choose 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\"{o}bius functions are both rational. Following in the footsteps of Bj\"{o}rner and Reutenauer and Bj\"{o}rner and Sagan, we rely on definitions to prove rationality in one case, and in another case we use finite-state automata.
No associations
LandOfFree
The Möbius Function of a Restricted Composition Poset does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Möbius Function of a Restricted Composition Poset, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Möbius Function of a Restricted Composition Poset will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-401497