Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Discrete Mathematics...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Discrete Mathematics & Theoretical Computer Science
Article . 2009 . Peer-reviewed
Data sources: Crossref
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Electronic Journal of Combinatorics
Article . 2009 . Peer-reviewed
Data sources: Crossref
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Episciences
Article . 2009
Data sources: Episciences
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 2009
Data sources: zbMATH Open
https://dx.doi.org/10.48550/ar...
Article . 2008
License: arXiv Non-Exclusive Distribution
Data sources: Datacite
DBLP
Article . 2022
Data sources: DBLP
versions View all 8 versions
addClaim

Rationality, irrationality, and Wilf equivalence in generalized factor order

Authors: Kitaev, Sergey; Liese, Jeff; Remmel, Jeffrey; Sagan, Bruce;

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. 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.

Keywords

partially ordered set, rationality, factor order, Exact enumeration problems, generating functions, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], wilf equivalence, 68R15, Combinatorics of partially ordered sets, 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, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], generating function, composition, Electronic computers. Computer science, 06A07, finite state automaton, Combinatorics (math.CO), 05A15, Mathematics

  • BIP!
    Impact byBIP!
    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
Powered by OpenAIRE graph
Found an issue? Give us feedback
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).
BIP!Citations provided by BIP!
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.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
5
Average
Top 10%
Average
Green
Published in a Diamond OA journal