TY - JOUR

T1 - Extended strict order polynomial of a Poset and fixed elements of linear extensions

AU - Langner, Johanna

AU - Witek, Henryk A.

N1 - Publisher Copyright:
© The author(s).

PY - 2021/10

Y1 - 2021/10

N2 - In this paper, we extend the concept of the strict order polynomial P (n),which enumerates strictly order-preserving maps: P ! n for a poset P, to the extended strict order polynomial EP (n; z) = PQP Q(n)zjQj, which enumerates analogous maps for all induced subposets of P. Richard Stanley showed that the strict order polynomial P (n) can be expressed as the sum P (n) =Pw2L(P) -n+des(w) p, where L(P) is the set of linear extensions of P, des(w) is the number of descents of w, and p is the number of elements of P. This reduces the computation of EP (n; z) to the enumeration of linear extensions of subposets of P by descents. We show that every linear extension v of every induced subposet of P can be associated with a linear extension w of P. The number of linear extensions of subposets of size k associated with a given linear extension w of P is -p-fixP (w) k-fixP (w), where fixP (w) is the number of fixed elements of w defined in the text. Consequently, the extended strict order polynomial.

AB - In this paper, we extend the concept of the strict order polynomial P (n),which enumerates strictly order-preserving maps: P ! n for a poset P, to the extended strict order polynomial EP (n; z) = PQP Q(n)zjQj, which enumerates analogous maps for all induced subposets of P. Richard Stanley showed that the strict order polynomial P (n) can be expressed as the sum P (n) =Pw2L(P) -n+des(w) p, where L(P) is the set of linear extensions of P, des(w) is the number of descents of w, and p is the number of elements of P. This reduces the computation of EP (n; z) to the enumeration of linear extensions of subposets of P by descents. We show that every linear extension v of every induced subposet of P can be associated with a linear extension w of P. The number of linear extensions of subposets of size k associated with a given linear extension w of P is -p-fixP (w) k-fixP (w), where fixP (w) is the number of fixed elements of w defined in the text. Consequently, the extended strict order polynomial.

UR - http://www.scopus.com/inward/record.url?scp=85114521395&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:85114521395

SN - 1034-4942

VL - 81

SP - 187

EP - 207

JO - Australasian Journal of Combinatorics

JF - Australasian Journal of Combinatorics

ER -