Skip to Main content Skip to Navigation
Conference papers

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' \in P^{\ast}$ then $w'$ is a factor of $w$ if there are words $u,v$ with $w=uw'v$. Define generalized factor order on $P^{\ast}$ by letting $u \leq w$ if there is a factor $w'$ of $w$ having the same length as $u$ such that $u \leq 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^{\ast}$, we prove that the language $\mathcal{F}(u)=\{w : w \geq u\}$ is accepted by a finite state automaton. If $P$ is finite then it follows that the generating function $F(u)=\sum_{w \geq u} w$ is rational. This is an analogue of a theorem of Björner and Sagan for generalized subword order. We also consider $P=\mathbb{P}$, the positive integers with the usual total order, so that $\mathbb{P}^{\ast}$ 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 \mathbb{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 can 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 \geq u} | \mu (u,w) | w$ can be irrational.
Complete list of metadata

Cited literature [5 references]  Display  Hide  Download

https://hal.inria.fr/hal-01185380
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 11:06:43 AM
Last modification on : Wednesday, August 7, 2019 - 2:32:05 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:06:30 AM

File

dmAK0143.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01185380, version 1

Collections

Citation

Sergey Kitaev, Jeffrey Liese, Jeffrey Remmel, Bruce Sagan. Rationality, irrationality, and Wilf equivalence in generalized factor order. 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), 2009, Hagenberg, Austria. pp.515-526. ⟨hal-01185380⟩

Share

Metrics

Record views

100

Files downloads

790