Generating Functions for Wilf Equivalence Under Generalized Factor Order

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

of the same length as

such that the

-th character of

is greater than or equal to the

-th character of

for all

. This subword

is called an embedding of

into

. For the case where

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

. They then defined two words

and

to be Wilf equivalent, denoted $u \backsim v$ , if and only if

. They also defined the related generating function $S(u;t,x) = \sum_{w \in \mathcal{S}(u)}$ wt

where $\mathcal{S}(u)$ is the set of all words

such that the only embedding of

into

is a suffix of

, and showed that $u \backsim v$ if and only if

. We continue this study by giving an explicit formula for

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

and

must be rearrangements, and the stronger conjecture that there also must be a weight-preserving bijection

on words over the positive integers such that

is a rearrangement of

for all

, and

embeds

if and only if

embeds