# 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

## Abstract

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.

Item type: | Article |
---|---|

ID code: | 49910 |

Keywords: | factor order, word order, weight generating function, Electronic computers. Computer science, Computational Theory and Mathematics, Geometry and Topology, Theoretical Computer Science |

Subjects: | Science > Mathematics > Electronic computers. Computer science |

Department: | Faculty of Science > Computer and Information Sciences |

Depositing user: | Pure Administrator |

Date deposited: | 21 Oct 2014 10:30 |

Last modified: | 07 Jan 2017 04:21 |

Related URLs: | |

URI: | http://strathprints.strath.ac.uk/id/eprint/49910 |

Export data: |