Journal of Integer Sequences, Vol. 14 (2011), Article 11.4.2

Generating Functions for Wilf Equivalence Under Generalized Factor Order

Thomas Langley
Department of Mathematics
Rose-Hulman Institute of Technology
Terre Haute, IN 47803

Jeffrey Liese
Department of Mathematics
California Polytechnic State University
San Luis Obispo, CA 93407-0403

Jeffrey Remmel
Department of Mathematics
University of California, San Diego
La Jolla, CA 92093-0112


Kitaev, Liese, Remmel, and Sagan recently defined generalized factor order on words comprised of letters from a partially ordered set $ (P,
\leq_P)$ by setting $ u \leq_P w$ if there is a contiguous 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 wt$ (w) =
t^{n} x^{\sum_{i=1}^n w_i}$, and the corresponding weight generating function $ F(u;t,x) = \sum_{w \geq_P u}$   wt$ (w)$. They then defined two words $ u$ and $ v$ to be Wilf equivalent, denoted $ u
\backsim v$, if and only if $ F(u;t,x) = F(v;t,x)$. They also defined the related generating function $ S(u;t,x) = \sum_{w \in \mathcal{S}(u)}$   wt$ (w)$ where $ \mathcal{S}(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 $ u
\backsim v$ 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 $ u
\backsim v$ then $ u$ and $ v$ must be rearrangements, and the stronger conjecture that there also must be a weight-preserving bijection $ f$ on words over the positive integers such that $ f(w)$ is a rearrangement of $ w$ for all $ w$, and $ w$ embeds $ u$ if and only if $ f(w)$ embeds $ v$.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000045 A000071 A000073 A000078 A000124 A000126 A000292 A001591 A001949 A007800 A008466 A008937 A014162 A050231 A050232 A050233 A107066 A145112 A145113 A172119.)

Received May 24 2010; revised version received March 16 2011. Published in Journal of Integer Sequences, March 26 2011.

Return to Journal of Integer Sequences home page