Rationality, irrationality, and Wilf equivalence in generalized factor order

Abstract

Let $P$ be a partially ordered set and consider the free monoid $P^{\ast }$ of all words over $P$. If $w,w^{\prime }\in P^{\ast }$ then $w^{\prime }$ is a factor of $w$ if there are words $u,v$ with $w=u{w}^{\prime }v$. Define generalized factor order on $P^{\ast }$ by letting $u\le w$ if there is a factor $w^{\prime }$ of $w$ having the same length as $u$ such that $u\le w^{\prime }$, where the comparison of $u$ and $w^{\prime }$ is done componentwise using the partial order in $P$. One obtains ordinary factor order by insisting that $u=w^{\prime }$ or, equivalently, by taking $P$ to be an antichain. Given $u\in P^{\ast }$, we prove that the language $\cF(u)=\{w : w\ge u\}$ is accepted by a finite state automaton. If $P$ is finite then it follows that the generating function $F(u)={\sum }_{w\ge u}w$ is rational. This is an analogue of a theorem of Björner and Sagan for generalized subword order. We also consider $P=\bbP$, the positive integers with the usual total order, so that $P^{\ast }$ is the set of compositions. In this case one obtains a weight generating function $F(u;t,x)$ by substituting $t{x}^n$ each time $n\in\bbP$ appears in $F(u)$. We show that this generating function is also rational by using the transfer-matrix method. Words $u,v$ are said to be Wilf equivalent if $F(u;t,x)=F(v;t,x)$ and we prove various Wilf equivalences combinatorially. Björner found a recursive formula for the Möbius function of ordinary factor order on $P^{\ast }$. It follows that one always has $\mu (u,w)=0,\pm 1$. Using the Pumping Lemma we show that the generating function $M(u)={\sum }_{w\ge u}|\mu (u,w)|w$ can be irrational.

25 pages, 2 figures