### Abstract

Language | English |
---|---|

Pages | 515-526 |

Number of pages | 12 |

Publication status | Published - 2009 |

Event | 21st International Conference on Formal Power Series & Algebraic Combinatorics - Hagenberg, Austria Duration: 20 Jul 2009 → 24 Jul 2009 |

### Conference

Conference | 21st International Conference on Formal Power Series & Algebraic Combinatorics |
---|---|

Country | Austria |

City | Hagenberg |

Period | 20/07/09 → 24/07/09 |

### Fingerprint

### Keywords

- composition
- factor order
- finite state automation
- partially ordered set
- rational generating function

### Cite this

*Rationality, irrationality, and Wilf equivalence in generalized factor order*. 515-526. Poster session presented at 21st International Conference on Formal Power Series & Algebraic Combinatorics, Hagenberg, Austria.

}

**Rationality, irrationality, and Wilf equivalence in generalized factor order.** / Kitaev, Sergey; Liese, Jeff; Remmel, Jeffrey; Sagan, Bruce.

Research output: Contribution to conference › Poster

TY - CONF

T1 - Rationality, irrationality, and Wilf equivalence in generalized factor order

AU - Kitaev, Sergey

AU - Liese, Jeff

AU - Remmel, Jeffrey

AU - Sagan, Bruce

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

KW - composition

KW - factor order

KW - finite state automation

KW - partially ordered set

KW - rational generating function

UR - http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAK0143

UR - http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAK0143/2757

M3 - Poster

SP - 515

EP - 526

ER -