Words avoiding a reflexive acyclic relation (Q813446)

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