Words Avoiding a Reflexive Acyclic Relation

Abstract

Let ${\cal A}\subseteq {\bf [n]}\times{\bf [n]}$ be a set of pairs containing the diagonal ${\cal D} = \{(i,i)\,|\, i=1,\ldots,n\}$, and such that $a\leq b$ for all $(a,b) \in {\cal A}$. We study formulae for the generating series $F_{\cal A} ({\bf x}) = \sum_w {\bf x}^w$ where the sum is over all words $w \in {\bf [n]}^*$ that avoid ${\cal A}$, i.e., $(w_i,w_{i+1})\notin {\cal A}$ for $i=1,\ldots,|w|-1$. This series is a rational function, with denominator of the form $1-\sum_{T}\mu_{{\cal A}}(T){\bf x}^T$, where the sum is over all nonempty subsets $T$ of $[n]$. Our principal focus is the case where the relation ${\cal A}$ is $\mu$-positive, i.e., $\mu_{\cal A}(T)\ge 0$ for all $T\subseteq {\bf [n]}$, in which case the form of the generating function suggests a cancellation-free combinatorial encoding of words avoiding ${\cal A}$. We supply such an interpretation for several classes of examples, including the interesting class of cycle-free (or crown-free) posets.