Rationality, irrationality, and Wilf equivalence in generalized factor order
Kitaev, Sergey and Liese, Jeff and Remmel, Jeffrey and Sagan, Bruce (2009) Rationality, irrationality, and Wilf equivalence in generalized factor order. In: 21st International Conference on Formal Power Series & Algebraic Combinatorics, 20090720  20090724.
Full text not available in this repository.Request a copy from the Strathclyde authorAbstract
Let P be a partially ordered set and consider the free monoid P* of all words over P. If w,w'∈P* then w' is a factor of w if there are words u,v with w=uw'v. Define generalized factor order on P* by letting u≤w if there is a factor w' of w having the same length as u such that u≤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∈P*, we prove that the language F(u)={w : w≥u} is accepted by a finite state automaton. If P is finite then it follows that the generating function F(u)=Σw≥u w is rational. This is an analogue of a theorem of Björner and Sagan for generalized subword order. We also consider P=ℙ, the positive integers with the usual total order, so that ℙ* is the set of compositions. In this case one obtains a weight generating function F(u;t,x) by substituting txn each time n∈ℙ appears in F(u). We show that this generating function is also rational by using the transfermatrix 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*. It follows that one always has µ(u,w)=0,±1. Using the Pumping Lemma we show that the generating function M(u)=Σw≥u µ(u,w) w can be irrational.
ORCID iDs
Kitaev, Sergey ORCID: https://orcid.org/0000000333241647, Liese, Jeff, Remmel, Jeffrey and Sagan, Bruce;

Item type: Conference or Workshop Item(Poster) ID code: 49974 Dates: DateEvent2009PublishedKeywords: composition, factor order, finite state automation, partially ordered set, rational generating function, Mathematics, Computational Mathematics Subjects: Science > Mathematics Department: Faculty of Science > Computer and Information Sciences Depositing user: Pure Administrator Date deposited: 21 Oct 2014 14:59 Last modified: 01 Jan 2021 07:43 Related URLs: URI: https://strathprints.strath.ac.uk/id/eprint/49974