Order polynomial

<h2 id="definition">Definition</h2>
Let 
 
 
 
 P
 
 
 {\displaystyle P}
 
 be a <a href="/facts/Finite_set/za1newlP">finite</a> <a href="/facts/Partially_ordered_set/qb4a3FAX">poset</a> with 
 
 
 
 p
 
 
 {\displaystyle p}
 
 elements denoted 
 
 
 
 x
 ,
 y
 ∈
 P
 
 
 {\displaystyle x,y\in P}
 
, and let 
 
 
 
 [
 n
 ]
 =
 {
 1
 <
 2
 <
 …
 <
 n
 }
 
 
 {\displaystyle [n]=\{1<2<\ldots <n\}}
 
 be a <a href="/facts/Total_order/xnTtmuYJ">chain</a> 
 
 
 
 n
 
 
 {\displaystyle n}
 
 elements. A map 
 
 
 
 ϕ
 :
 P
 →
 [
 n
 ]
 
 
 {\displaystyle \phi :P\to [n]}
 
 is order-preserving if 
 
 
 
 x
 ≤
 y
 
 
 {\displaystyle x\leq y}
 
 implies 
 
 
 
 ϕ
 (
 x
 )
 ≤
 ϕ
 (
 y
 )
 
 
 {\displaystyle \phi (x)\leq \phi (y)}
 
. The number of such maps grows polynomially with 
 
 
 
 n
 
 
 {\displaystyle n}
 
, and the function that counts their number is the order polynomial 
 
 
 
 Ω
 (
 n
 )
 =
 Ω
 (
 P
 ,
 n
 )
 
 
 {\displaystyle \Omega (n)=\Omega (P,n)}
 
. 
Similarly, we can define an order polynomial that counts the number of <a href="/facts/Strict/pxg8tukY">strictly</a> order-preserving maps 
 
 
 
 ϕ
 :
 P
 →
 [
 n
 ]
 
 
 {\displaystyle \phi :P\to [n]}
 
, meaning 
 
 
 
 x
 <
 y
 
 
 {\displaystyle x<y}
 
 implies 
 
 
 
 ϕ
 (
 x
 )
 <
 ϕ
 (
 y
 )
 
 
 {\displaystyle \phi (x)<\phi (y)}
 
. The number of such maps is the strict order polynomial 
 
 
 
 
 Ω
 
 ∘
 
 
 
 (
 n
 )
 =
 
 Ω
 
 ∘
 
 
 
 (
 P
 ,
 n
 )
 
 
 {\displaystyle \Omega ^{\circ }\!(n)=\Omega ^{\circ }\!(P,n)}
 
.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>
Both 
 
 
 
 Ω
 (
 n
 )
 
 
 {\displaystyle \Omega (n)}
 
 and 
 
 
 
 
 Ω
 
 ∘
 
 
 
 (
 n
 )
 
 
 {\displaystyle \Omega ^{\circ }\!(n)}
 
 have degree 
 
 
 
 p
 
 
 {\displaystyle p}
 
. The order-preserving maps generalize the <a href="/facts/Linear_extension/jKKPR2pn">linear extensions</a> of 
 
 
 
 P
 
 
 {\displaystyle P}
 
, the order-preserving bijections 
 
 
 
 ϕ
 :
 P
 
 
 
 
 ⟶
 
 
 ∼
 
 
 
 
 [
 p
 ]
 
 
 {\displaystyle \phi :P{\stackrel {\sim }{\longrightarrow }}[p]}
 
. In fact, the leading coefficient of 
 
 
 
 Ω
 (
 n
 )
 
 
 {\displaystyle \Omega (n)}
 
 and 
 
 
 
 
 Ω
 
 ∘
 
 
 
 (
 n
 )
 
 
 {\displaystyle \Omega ^{\circ }\!(n)}
 
 is the number of linear extensions divided by 
 
 
 
 p
 !
 
 
 {\displaystyle p!}
 
.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>

<h2 id="examples">Examples</h2>
Letting 
 
 
 
 P
 
 
 {\displaystyle P}
 
 be a <a href="/facts/Total_order/xnTtmuYJ">chain</a> of 
 
 
 
 p
 
 
 {\displaystyle p}
 
 elements, we have <blockquote>
 
 
 
 Ω
 (
 n
 )
 =
 
 
 
 (
 
 
 
 n
 +
 p
 −
 1
 
 p
 
 
 )
 
 
 
 =
 
 (
 
 
 
 (
 
 
 n
 p
 
 
 )
 
 
 
 )
 
 
 
 {\displaystyle \Omega (n)={\binom {n+p-1}{p}}=\left(\!\left({n \atop p}\right)\!\right)}
 
 and 
 
 
 
 
 Ω
 
 ∘
 
 
 (
 n
 )
 =
 
 
 
 (
 
 
 n
 p
 
 
 )
 
 
 
 .
 
 
 {\displaystyle \Omega ^{\circ }(n)={\binom {n}{p}}.}
 
 </blockquote>There is only one linear extension (the identity mapping), and both polynomials have leading term 
 
 
 
 
 
 
 1
 
 p
 !
 
 
 
 
 
 n
 
 p
 
 
 
 
 {\displaystyle {\tfrac {1}{p!}}n^{p}}
 
.
Letting 
 
 
 
 P
 
 
 {\displaystyle P}
 
 be an <a href="/facts/Antichain/rPuqkKJt">antichain</a> of 
 
 
 
 p
 
 
 {\displaystyle p}
 
 incomparable elements, we have 
 
 
 
 Ω
 (
 n
 )
 =
 
 Ω
 
 ∘
 
 
 (
 n
 )
 =
 
 n
 
 p
 
 
 
 
 {\displaystyle \Omega (n)=\Omega ^{\circ }(n)=n^{p}}
 
. Since any bijection 
 
 
 
 ϕ
 :
 P
 
 
 
 
 ⟶
 
 
 ∼
 
 
 
 
 [
 p
 ]
 
 
 {\displaystyle \phi :P{\stackrel {\sim }{\longrightarrow }}[p]}
 
 is (strictly) order-preserving, there are 
 
 
 
 p
 !
 
 
 {\displaystyle p!}
 
 linear extensions, and both polynomials reduce to the leading term 
 
 
 
 
 
 
 
 p
 !
 
 
 p
 !
 
 
 
 
 
 n
 
 p
 
 
 =
 
 n
 
 p
 
 
 
 
 {\displaystyle {\tfrac {p!}{p!}}n^{p}=n^{p}}
 
.

<h2 id="reciprocity-theorem">Reciprocity theorem</h2>
There is a relation between strictly order-preserving maps and order-preserving maps:<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

Ω
          
            ∘
          
        
        (
        n
        )
        =
        (
        −
        1
        
          )
          
            
              |
            
            P
            
              |
            
          
        
        Ω
        (
        −
        n
        )
        .
      
    
    {\displaystyle \Omega ^{\circ }(n)=(-1)^{|P|}\Omega (-n).}

In the case that 
 
 
 
 P
 
 
 {\displaystyle P}
 
 is a chain, this recovers the <a href="/facts/Binomial_coefficient/Tsx7eY5h">negative binomial identity</a>. There are similar results for the <a href="/facts/Chromatic_polynomial/dvr4Hyz9">chromatic polynomial</a> and <a href="/facts/Ehrhart_polynomial/WjuUYzrT">Ehrhart polynomial</a> (see below), all special cases of Stanley's general <a href="/facts/Stanley%2527s_reciprocity_theorem/1echtVQg">Reciprocity Theorem</a>.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

<h2 id="connections-with-other-counting-polynomials">Connections with other counting polynomials</h2>
<h3>Chromatic polynomial</h3>
The <a href="/facts/Chromatic_polynomial/dvr4Hyz9">chromatic polynomial</a> 
 
 
 
 P
 (
 G
 ,
 n
 )
 
 
 {\displaystyle P(G,n)}
 
counts the number of proper <a href="/facts/Graph_coloring/J6HoBfP0">colorings</a> of a finite <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graph</a> 
 
 
 
 G
 
 
 {\displaystyle G}
 
 with 
 
 
 
 n
 
 
 {\displaystyle n}
 
 available colors. For an <a href="/facts/Acyclic_orientation/cdAUkyFH">acyclic orientation</a> 
 
 
 
 σ
 
 
 {\displaystyle \sigma }
 
 of the edges of 
 
 
 
 G
 
 
 {\displaystyle G}
 
, there is a natural "downstream" partial order on the vertices 
 
 
 
 V
 (
 G
 )
 
 
 {\displaystyle V(G)}
 
 implied by the basic relations 
 
 
 
 u
 >
 v
 
 
 {\displaystyle u>v}
 
 whenever 
 
 
 
 u
 →
 v
 
 
 {\displaystyle u\rightarrow v}
 
 is a directed edge of 
 
 
 
 σ
 
 
 {\displaystyle \sigma }
 
. (Thus, the <a href="/facts/Hasse_diagram/EqeJbUH0">Hasse diagram</a> of the poset is a subgraph of the oriented graph 
 
 
 
 σ
 
 
 {\displaystyle \sigma }
 
.) We say 
 
 
 
 ϕ
 :
 V
 (
 G
 )
 →
 [
 n
 ]
 
 
 {\displaystyle \phi :V(G)\rightarrow [n]}
 
 is compatible with 
 
 
 
 σ
 
 
 {\displaystyle \sigma }
 
 if 
 
 
 
 ϕ
 
 
 {\displaystyle \phi }
 
 is order-preserving. Then we have

P
        (
        G
        ,
        n
        )
         
        =
         
        
          ∑
          
            σ
          
        
        
          Ω
          
            ∘
          
        
        
        (
        σ
        ,
        n
        )
        ,
      
    
    {\displaystyle P(G,n)\ =\ \sum _{\sigma }\Omega ^{\circ }\!(\sigma ,n),}

where 
 
 
 
 σ
 
 
 {\displaystyle \sigma }
 
 runs over all acyclic orientations of G, considered as poset structures.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>

<h3>Order polytope and Ehrhart polynomial</h3>
Main article: <a href="/facts/Order_polytope/l4xueKAh">Order polytope</a>
The <a href="/facts/Order_polytope/l4xueKAh">order polytope</a> associates a <a href="/facts/Polytope/a76nXrL0">polytope</a> with a partial order. For a poset 
 
 
 
 P
 
 
 {\displaystyle P}
 
 with 
 
 
 
 p
 
 
 {\displaystyle p}
 
 elements, the order polytope 
 
 
 
 O
 (
 P
 )
 
 
 {\displaystyle O(P)}
 
 is the set of order-preserving maps 
 
 
 
 f
 :
 P
 →
 [
 0
 ,
 1
 ]
 
 
 {\displaystyle f:P\to [0,1]}
 
, where 
 
 
 
 [
 0
 ,
 1
 ]
 =
 {
 t
 ∈
 
 R
 
 ∣
 0
 ≤
 t
 ≤
 1
 }
 
 
 {\displaystyle [0,1]=\{t\in \mathbb {R} \mid 0\leq t\leq 1\}}
 
 is the ordered unit interval, a continuous chain poset.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a><a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> More geometrically, we may list the elements 
 
 
 
 P
 =
 {
 
 x
 
 1
 
 
 ,
 …
 ,
 
 x
 
 p
 
 
 }
 
 
 {\displaystyle P=\{x_{1},\ldots ,x_{p}\}}
 
, and identify any mapping 
 
 
 
 f
 :
 P
 →
 
 R
 
 
 
 {\displaystyle f:P\to \mathbb {R} }
 
 with the point 
 
 
 
 (
 f
 (
 
 x
 
 1
 
 
 )
 ,
 …
 ,
 f
 (
 
 x
 
 p
 
 
 )
 )
 ∈
 
 
 R
 
 
 p
 
 
 
 
 {\displaystyle (f(x_{1}),\ldots ,f(x_{p}))\in \mathbb {R} ^{p}}
 
; then the order polytope is the set of points 
 
 
 
 (
 
 t
 
 1
 
 
 ,
 …
 ,
 
 t
 
 p
 
 
 )
 ∈
 [
 0
 ,
 1
 
 ]
 
 p
 
 
 
 
 {\displaystyle (t_{1},\ldots ,t_{p})\in [0,1]^{p}}
 
 with 
 
 
 
 
 t
 
 i
 
 
 ≤
 
 t
 
 j
 
 
 
 
 {\displaystyle t_{i}\leq t_{j}}
 
 if 
 
 
 
 
 x
 
 i
 
 
 ≤
 
 x
 
 j
 
 
 
 
 {\displaystyle x_{i}\leq x_{j}}
 
.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> 
The <a href="/facts/Ehrhart_polynomial/WjuUYzrT">Ehrhart polynomial</a> counts the number of <a href="/facts/Integer_lattice/h4FP4pjm">integer lattice</a> points inside the dilations of a <a href="/facts/Polytope/a76nXrL0">polytope</a>. Specifically, consider the lattice 
 
 
 
 L
 =
 
 
 Z
 
 
 n
 
 
 
 
 {\displaystyle L=\mathbb {Z} ^{n}}
 
 and a 
 
 
 
 d
 
 
 {\displaystyle d}
 
-dimensional polytope 
 
 
 
 K
 ⊂
 
 
 R
 
 
 d
 
 
 
 
 {\displaystyle K\subset \mathbb {R} ^{d}}
 
 with vertices in 
 
 
 
 L
 
 
 {\displaystyle L}
 
; then we define

L
        (
        K
        ,
        n
        )
        =
        #
        (
        n
        K
        ∩
        L
        )
        ,
      
    
    {\displaystyle L(K,n)=\#(nK\cap L),}

the number of lattice points in 
 
 
 
 n
 K
 
 
 {\displaystyle nK}
 
, the dilation of 
 
 
 
 K
 
 
 {\displaystyle K}
 
 by a positive integer scalar 
 
 
 
 n
 
 
 {\displaystyle n}
 
. <a href="/facts/Eug%25C3%25A8ne_Ehrhart/HLX2DDBq">Ehrhart</a> showed that this is a <a href="/facts/Rational_function/2nJGu0Ko">rational polynomial</a> of degree 
 
 
 
 d
 
 
 {\displaystyle d}
 
 in the variable 
 
 
 
 n
 
 
 {\displaystyle n}
 
, provided 
 
 
 
 K
 
 
 {\displaystyle K}
 
 has vertices in the lattice.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>

In fact, the Ehrhart polynomial of an order polytope is equal to the order polynomial of the original poset (with a shifted argument):<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a><a class="footnote-ref" id="fnref:11" href="#fn:11">11</a><blockquote>
 
 
 
 L
 (
 O
 (
 P
 )
 ,
 n
 )
  
 =
  
 Ω
 (
 P
 ,
 n
 
 +
 
 1
 )
 .
 
 
 {\displaystyle L(O(P),n)\ =\ \Omega (P,n{+}1).}
 
</blockquote>This is an immediate consequence of the definitions, considering the embedding of the 
 
 
 
 (
 n
 
 +
 
 1
 )
 
 
 {\displaystyle (n{+}1)}
 
-chain poset 
 
 
 
 [
 n
 
 +
 
 1
 ]
 =
 {
 0
 <
 1
 <
 ⋯
 <
 n
 }
 ⊂
 
 R
 
 
 
 {\displaystyle [n{+}1]=\{0<1<\cdots <n\}\subset \mathbb {R} }
 
.

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Stanley, Richard P. (1972). Ordered structures and partitions. Providence, Rhode Island: American Mathematical Society. <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Stanley, Richard P. (1986). "Two poset polytopes". Discrete & Computational Geometry. 1: 9–23. doi:10.1007/BF02187680. <a href="https://doi.org/10.1007%2FBF02187680" target="_blank">https://doi.org/10.1007%2FBF02187680</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Stanley, Richard P. (1970). "A chromatic-like polynomial for ordered sets". Proc. Second Chapel Hill Conference on Combinatorial Mathematics and Its Appl.: 421–427. <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Stanley, Richard P. (2012). "4.5.14 Reciprocity theorem for linear homogeneous diophantine equations". Enumerative combinatorics. Volume 1 (2nd ed.). New York: Cambridge University Press. ISBN 9781139206549. OCLC 777400915. <a href="9781139206549" target="_blank">9781139206549</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Stanley, Richard P. (1973). "Acyclic orientations of graphs". Discrete Mathematics. 5 (2): 171–178. doi:10.1016/0012-365X(73)90108-8. <a href="/wiki/Discrete_Mathematics_(journal)" target="_blank">/wiki/Discrete_Mathematics_(journal)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Karzanov, Alexander; Khachiyan, Leonid (1991). "On the conductance of Order Markov Chains". Order. 8: 7–15. doi:10.1007/BF00385809. S2CID 120532896. <a href="/wiki/Order_(journal)" target="_blank">/wiki/Order_(journal)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Brightwell, Graham; Winkler, Peter (1991). "Counting linear extensions". Order. 8 (3): 225–242. doi:10.1007/BF00383444. S2CID 119697949. <a href="/wiki/Order_(journal)" target="_blank">/wiki/Order_(journal)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Stanley, Richard P. (1986). "Two poset polytopes". Discrete & Computational Geometry. 1: 9–23. doi:10.1007/BF02187680. <a href="https://doi.org/10.1007%2FBF02187680" target="_blank">https://doi.org/10.1007%2FBF02187680</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Beck, Matthias; Robins, Sinai (2015). Computing the continuous discretely. New York: Springer. pp. 64–72. ISBN 978-1-4939-2968-9. <a href="978-1-4939-2968-9" target="_blank">978-1-4939-2968-9</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Stanley, Richard P. (1986). "Two poset polytopes". Discrete & Computational Geometry. 1: 9–23. doi:10.1007/BF02187680. <a href="https://doi.org/10.1007%2FBF02187680" target="_blank">https://doi.org/10.1007%2FBF02187680</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Linial, Nathan (1984). "The information-theoretic bound is good for merging". SIAM J. Comput. 13 (4): 795–801. doi:10.1137/0213049.Kahn, Jeff; Kim, Jeong Han (1995). "Entropy and sorting". Journal of Computer and System Sciences. 51 (3): 390–399. doi:10.1006/jcss.1995.1077. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
</ol>

Order polynomial open-in-new

Order polynomial