The Möbius function of a restricted composition poset.

Publication date 26 October 2016

Published in Ars Combinatoria (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0806.1500

automaton composition generating function Möbius function shellability subword order

Combinatorics of partially ordered sets (06A07) Shellability for polytopes and polyhedra (52B22) Formal languages and automata (68Q45) Combinatorics on words (68R15)

Abstract: 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

m u (u, w) = (- 1)^{| u | + | w |} {w c h o o s e u}_{d n}

, where

{w c h o o s e u}_{d n}

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.

Recommendations

Cited in

(7)

This page was built for publication: The Möbius function of a restricted composition poset.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2828990)