\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf John Dollhopf, Ian Goulden and Curtis Greene}
%
%
\medskip
\noindent
%
%
{\bf Words Avoiding a Reflexive Acyclic Relation}
%
%
\vskip 5mm
\noindent
%
%
%
%
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 {\it
avoid} ${\cal A}$, i.e., $(w_i,w_{i+1})\not\in {\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 {\it $\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.
\bye