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 transfer-matrix 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.
Résumé. Soit P un ensemble partiellement ordoné. Nous considérons le monoïde libre P* de tous les mots utilisant P comme alphabet. Si w,w'∈ P*, on dit que w' est un facteur de w s'il y a des mots u,v avec w=uw'v. Nous definissons l'ordre facteur généralisé sur P* par: u≤w s'il y a un facteur w' de w ayant la même longueur que u tel que u≤w', où la comparison de u avec w' est faite lettre par lettre utilisant l'ordre en P. On obtient l'ordre facteur usuel si on insiste que u=w' ou, ce qui est la même chose, en prenant P comme antichaîne. Pour n'importe quel u∈P*, nous démontrons que le langage F(u)={w : w≥u} est accepté par un automaton avec un nombre fini d'états. Si P est fini, ca implique que la fonction génératrice F(u)=Σw≥u w est rationnelle. Björner et Sagan ont démontré le théorème analogue pour l'ordre où, en la définition au-dessus, w' est un sous-mot de w. Nous considérons aussi le cas P=ℙ, les entiers positifs avec l'ordre usuel, donc P* est l'ensemble des compositions. En ce cas on obtient une fonction génératrice pondéré F(u;t,x) en remplaçant txn chaque fois on trouve n∈ℙ en F(u). Nous démontrons que cette fonction génératrice est aussi rationnelle en utilisant la Méthode Matrice de Tranfert. On dit que let mots u,v sont Wilf-équivalents si F(u;t,x)=F(v;t,x). Nous pouvons démontré quelques équivalances dans une manière combinatorie. Björner a trouvé une formule recursive pour la fonction Möbius de l'ordre facteur usuel sur P*. Cette formule implique qu'on a toujours µ(u,w)=0,±1. En utilisant le Lemme de Pompage, nous démontrons que la fonction génératrice M(u)=Σw≥u |µ(u,w)| w peut être irrationnelle.