{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:22:04Z","timestamp":1759335724029,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>Let $P$ be a partially ordered set and consider the free monoid $P^*$ of all words over $P$.  If $w,w'\\in P^*$ then $w'$ is a factor of $w$ if there are words $u,v$ with $w=uw'v$.  Define generalized factor order on $P^*$ by letting $u\\le w$ if there is a factor $w'$ of $w$ having the same length as $u$ such that $u\\le w'$, where the comparison of $u$ and $w'$ is done componentwise using the partial order in $P$.  One obtains ordinary factor order by insisting that $u=w'$ or, equivalently, by taking $P$ to be an antichain. Given $u\\in P^*$, we prove that the language ${\\cal F}(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\u00f6rner and Sagan for generalized subword order. We also consider $P={\\Bbb P}$, the positive integers with the usual total order, so that $P^*$ is the set of compositions.  In this case one obtains a weight generating function $F(u;t,x)$ by substituting $tx^n$ each time $n\\in{\\Bbb P}$ 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\u00f6rner found a recursive formula for the M\u00f6bius function of ordinary factor order on $P^*$.  It follows that one always has $\\mu(u,w)=0,\\pm1$.  Using the Pumping Lemma we show that the generating function $M(u)=\\sum_{w\\ge u} |\\mu(u,w)| w$ can be irrational.<\/jats:p>","DOI":"10.37236\/88","type":"journal-article","created":{"date-parts":[[2020,1,11]],"date-time":"2020-01-11T04:21:40Z","timestamp":1578716500000},"source":"Crossref","is-referenced-by-count":4,"title":["Rationality, Irrationality, and Wilf Equivalence in Generalized Factor Order"],"prefix":"10.37236","volume":"16","author":[{"given":"Sergey","family":"Kitaev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey","family":"Liese","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey","family":"Remmel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bruce E.","family":"Sagan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2009,12,2]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v16i2r22\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v16i2r22\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,18]],"date-time":"2020-01-18T00:03:28Z","timestamp":1579305808000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v16i2r22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12,2]]},"references-count":0,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2009,2,11]]}},"URL":"https:\/\/doi.org\/10.37236\/88","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2009,12,2]]},"article-number":"R22"}}