
arXiv: 0806.3469
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. Soit $P$ un ensemble partiellement ordonné. Nous considérons le monoïde libre $P^{\ast}$ de tous les mots utilisant $P$ comme alphabet. Si $w,w' \in P^{\ast}$, on dit que $w'$ est un facteur de $w$ s'il y a des mots $u,v$ avec $w=uw'v$. Nous définissons l'ordre facteur généralisé sur $P^{\ast}$ par: $u \leq w$ s'il y a un facteur $w'$ de $w$ ayant la même longueur que $u$ tel que $u \leq w'$, où la comparaison de $u$ avec $w'$ est faite lettre par lettre utilisant l'ordre en $P$. On obtient l'ordre facteur usuel si on insiste que $u=w'$ ou, ce qui est la même chose, en prenant $P$ comme antichaîne. Pour n'importe quel $u \in P^{\ast}$, nous démontrons que le langage $\mathcal{F}(u)=\{w : w \geq u\}$ est accepté par un automaton avec un nombre fini d'états. Si $P$ est fini, ça implique que la fonction génératrice $F(u)=\sum_{w \geq u} w$ est rationnelle. Björner et Sagan ont démontré le théorème analogue pour l'ordre où, en la définition au-dessus, $w'$ est un sous-mot de $w$. Nous considérons aussi le cas $P=\mathbb{P}$, les entiers positifs avec l'ordre usuel, donc $P^{\ast}$ est l'ensemble des compositions. En ce cas on obtient une fonction génératrice pondéré $F(u;t,x)$ en remplaçant $tx^n$ chaque fois on trouve $n \in \mathbb{P}$ en $F(u)$. Nous démontrons que cette fonction génératrice est aussi rationnelle en utilisant la Méthode Matrice de Tranfert. On dit que let mots $u,v$ sont Wilf-équivalents si $F(u;t,x)=F(v;t,x)$. Nous pouvons démontré quelques équivalences dans une manière combinatoire. Björner a trouvé une formule récursive pour la fonction Möbius de l'ordre facteur usuel sur $P^{\ast}$. Cette formule implique qu'on a toujours $\mu (u,w)=0, \pm 1$. En utilisant le Lemme de Pompage, nous démontrons que la fonction génératrice $M(u)= \sum_{w \geq u} | \mu (u,w) | w$ peut être irrationnelle.
partially ordered set, rationality, factor order, Exact enumeration problems, generating functions, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], wilf equivalence, 68R15, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Combinatorics of partially ordered sets, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], QA1-939, FOS: Mathematics, Mathematics - Combinatorics, transfer matrix, [math.math-co] mathematics [math]/combinatorics [math.co], rational generating function, 05A15; 68R15; 06A07, 000, Combinatorics on words, Wilf equivalence, 004, generating function, composition, Electronic computers. Computer science, 06A07, finite state automaton, Combinatorics (math.CO), 05A15, Mathematics
partially ordered set, rationality, factor order, Exact enumeration problems, generating functions, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], wilf equivalence, 68R15, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Combinatorics of partially ordered sets, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], QA1-939, FOS: Mathematics, Mathematics - Combinatorics, transfer matrix, [math.math-co] mathematics [math]/combinatorics [math.co], rational generating function, 05A15; 68R15; 06A07, 000, Combinatorics on words, Wilf equivalence, 004, generating function, composition, Electronic computers. Computer science, 06A07, finite state automaton, Combinatorics (math.CO), 05A15, Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 5 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
