Generating functions for Wilf equivalence under generalized factor order

MaRDI QIDQ3004887zbMATH OpenFDO

Authors Thomas Langley, Jeffrey Liese, Jeffrey Remmel

Publication date 6 June 2011

Full work available at URL https://arxiv.org/abs/1005.4372, https://eudml.org/doc/230968, http://www.emis.de/journals/JIS/VOL14/Langley/langley2.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

generating functionrationalitycompositionpartially ordered setWilf equivalencefactor orders

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorics of partially ordered sets (06A07) Combinatorics on words (68R15)

Abstract: Kitaev, Liese, Remmel, and Sagan recently defined generalized factor order on words comprised of letters from a partially ordered set $(P,le{q}_P)$ by setting $ule{q}_{P}w$ if there is a subword $v$ of $w$ of the same length as $u$ such that the $i$-th character of $v$ is greater than or equal to the $i$-th character of $u$ for all $i$. This subword $v$ is called an embedding of $u$ into $w$. For the case where $P$ is the positive integers with the usual ordering, they defined the weight of a word $w=w_{1}ldots{w}_n$ to be $extwt(w)=x^{su{m}_{i=1}^n{w}_i}{t}^n$, and the corresponding weight generating function $F(u;t,x)=su{m}_{wge{q}_{P}u}extwt(w)$. They then defined two words $u$ and $v$ to be Wilf equivalent, denoted $$, if and only if $F(u;t,x)=F(v;t,x)$. They also defined the related generating function $S(u;t,x)=su{m}_{winmathcalS(u)}extwt(w)$ where $mathcalS(u)$ is the set of all words $w$ such that the only embedding of $u$ into $w$ is a suffix of $w$, and showed that $$ if and only if $S(u;t,x)=S(v;t,x)$. We continue this study by giving an explicit formula for $S(u;t,x)$ if $u$ factors into a weakly increasing word followed by a weakly decreasing word. We use this formula as an aid to classify Wilf equivalence for all words of length 3. We also show that coefficients of related generating functions are well-known sequences in several special cases. Finally, we discuss a conjecture that if $$ then $u$ and $v$ must be rearrangements, and the stronger conjecture that there also must be a weight-preserving bijection $f:mathcalS(u)ightarrowmathcalS(v)$ such that $f(u)$ is a rearrangement of $u$ for all $u$.

Recommendations

• Wilf equivalence for generalized factor orders modulo \(k\)
• Rationality, irrationality, and Wilf equivalence in generalized factor order
• Rationality, irrationality, and Wilf equivalence in generalized factor order
• Generating functions and Wilf equivalence for generalized interval embeddings
• On the rearrangement conjecture for generalized factor order over \(\mathbb P\)

Cited in

(7)

• Shift equivalence in the generalized factor order
• On the rearrangement conjecture for generalized factor order over \(\mathbb P\)
• Wilf equivalence for generalized factor orders modulo \(k\)
• Rationality, irrationality, and Wilf equivalence in generalized factor order
• Rationality, irrationality, and Wilf equivalence in generalized factor order
• Generating functions and Wilf equivalence for generalized interval embeddings
• The combinatorics of Jeff Remmel

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Generating functions for Wilf equivalence under generalized factor order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3004887)