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

Johanna Langner, Henryk A. Witek

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)187-207
Number of pages21
JournalAustralasian Journal of Combinatorics
Volume81
StatePublished - Oct 2021

Fingerprint

Dive into the research topics of 'Extended strict order polynomial of a Poset and fixed elements of linear extensions'. Together they form a unique fingerprint.

Cite this