Picture of person typing on laptop with programming code visible on the laptop screen

World class computing and information science research at Strathclyde...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of Open Access research papers by University of Strathclyde researchers, including by researchers from the Department of Computer & Information Sciences involved in mathematically structured programming, similarity and metric search, computer security, software systems, combinatronics and digital health.

The Department also includes the iSchool Research Group, which performs leading research into socio-technical phenomena and topics such as information retrieval and information seeking behaviour.


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. The Electronic Journal of Combinatorics, 16 (2). ISSN 1077-8926

Full text not available in this repository. Request a copy from the Strathclyde author


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 component wise 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≥uw is rational. This is an analogue of a theorem of Björner and Sagan for generalized subword order. We also consider P=P, the positive integers with the usual total order, so that P∗ is the set of compositions. In this case one obtains a weight generating function F(u;t,x) by substituting txn each time n∈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 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.