Rationality, irrationality, and Wilf equivalence in generalized factor order

Sergey Kitaev, Jeff Liese, Jeffrey Remmel, Bruce Sagan

Research output: Contribution to conferencePoster

1 Citation (Scopus)

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

Conference

Conference21st International Conference on Formal Power Series & Algebraic Combinatorics
CountryAustria
CityHagenberg
Period20/07/0924/07/09

Fingerprint

Irrationality
Rationality
Equivalence
Generating Function
Free Monoid
Möbius Function
Subword
Finite State Automata
Antichain
Transfer matrix method
Transfer Matrix Method
Recursive Formula
Partially Ordered Set
Finite automata
Partial Order
Weight Function
Lemma
Analogue
Integer
Chemical analysis

Keywords

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

Cite this

Kitaev, S., Liese, J., Remmel, J., & Sagan, B. (2009). 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.
Kitaev, Sergey ; Liese, Jeff ; Remmel, Jeffrey ; Sagan, Bruce. / Rationality, irrationality, and Wilf equivalence in generalized factor order. Poster session presented at 21st International Conference on Formal Power Series & Algebraic Combinatorics, Hagenberg, Austria.12 p.
@conference{842fff7a9d164ba88a5967d4ac10785a,
title = "Rationality, irrationality, and Wilf equivalence in generalized factor order",
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 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{\"o}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{\"o}rner found a recursive formula for the M{\"o}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.",
keywords = "composition, factor order, finite state automation, partially ordered set, rational generating function",
author = "Sergey Kitaev and Jeff Liese and Jeffrey Remmel and Bruce Sagan",
year = "2009",
language = "English",
pages = "515--526",
note = "21st International Conference on Formal Power Series & Algebraic Combinatorics ; Conference date: 20-07-2009 Through 24-07-2009",

}

Kitaev, S, Liese, J, Remmel, J & Sagan, B 2009, 'Rationality, irrationality, and Wilf equivalence in generalized factor order' 21st International Conference on Formal Power Series & Algebraic Combinatorics, Hagenberg, Austria, 20/07/09 - 24/07/09, pp. 515-526.

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

2009. 515-526 Poster session presented at 21st International Conference on Formal Power Series & Algebraic Combinatorics, Hagenberg, Austria.

Research output: Contribution to conferencePoster

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 -

Kitaev S, Liese J, Remmel J, Sagan B. Rationality, irrationality, and Wilf equivalence in generalized factor order. 2009. Poster session presented at 21st International Conference on Formal Power Series & Algebraic Combinatorics, Hagenberg, Austria.