\documentclass[12pt,titlepage]{article}

\usepackage{amsmath}
\usepackage{mathrsfs}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{color}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage{xparse}
\usepackage{hyperref}

%----Macros----------
%
% Unresolved issues:
%
%  \righttoleftarrow
%  \lefttorightarrow
%
%  \color{} with HTML colorspec
%  \bgcolor
%  \array with options (without options, it's equivalent to the matrix environment)

% Of the standard HTML named colors, white, black, red, green, blue and yellow
% are predefined in the color package. Here are the rest.
\definecolor{aqua}{rgb}{0, 1.0, 1.0}
\definecolor{fuschia}{rgb}{1.0, 0, 1.0}
\definecolor{gray}{rgb}{0.502, 0.502, 0.502}
\definecolor{lime}{rgb}{0, 1.0, 0}
\definecolor{maroon}{rgb}{0.502, 0, 0}
\definecolor{navy}{rgb}{0, 0, 0.502}
\definecolor{olive}{rgb}{0.502, 0.502, 0}
\definecolor{purple}{rgb}{0.502, 0, 0.502}
\definecolor{silver}{rgb}{0.753, 0.753, 0.753}
\definecolor{teal}{rgb}{0, 0.502, 0.502}

% Because of conflicts, \space and \mathop are converted to
% \itexspace and \operatorname during preprocessing.

% itex: \space{ht}{dp}{wd}
%
% Height and baseline depth measurements are in units of tenths of an ex while
% the width is measured in tenths of an em.
\makeatletter
\newdimen\itex@wd%
\newdimen\itex@dp%
\newdimen\itex@thd%
\def\itexspace#1#2#3{\itex@wd=#3em%
\itex@wd=0.1\itex@wd%
\itex@dp=#2ex%
\itex@dp=0.1\itex@dp%
\itex@thd=#1ex%
\itex@thd=0.1\itex@thd%
\advance\itex@thd\the\itex@dp%
\makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}}
\makeatother

% \tensor and \multiscript
\makeatletter
\newif\if@sup
\newtoks\@sups
\def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}%
\def\reset@sup{\@supfalse\@sups={}}%
\def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else%
  \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}%
  \else \append@sup#2 \@suptrue \fi%
  \expandafter\mk@scripts\fi}
\def\tensor#1#2{\reset@sup#1\mk@scripts#2_/}
\def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2%
  \reset@sup\mk@scripts#3_/}
\makeatother

% \slash
\makeatletter
\newbox\slashbox \setbox\slashbox=\hbox{$/$}
\def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$}
  \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa
  \copy\slashbox \kern-\@tempdima \box\@tempboxa}
\def\slash{\protect\itex@pslash}
\makeatother

% math-mode versions of \rlap, etc
% from Alexander Perlis, "A complement to \smash, \llap, and lap"
%   http://math.arizona.edu/~aprl/publications/mathclap/
\def\clap#1{\hbox to 0pt{\hss#1\hss}}
\def\mathllap{\mathpalette\mathllapinternal}
\def\mathrlap{\mathpalette\mathrlapinternal}
\def\mathclap{\mathpalette\mathclapinternal}
\def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}}
\def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}}
\def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}}

% Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2}
\let\oldroot\root
\def\root#1#2{\oldroot #1 \of{#2}}
\renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}}

% Manually declare the txfonts symbolsC font
\DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n}
\SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n}
\DeclareFontSubstitution{U}{txsyc}{m}{n}

% Manually declare the stmaryrd font
\DeclareSymbolFont{stmry}{U}{stmry}{m}{n}
\SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n}

% Manually declare the MnSymbolE font
\DeclareFontFamily{OMX}{MnSymbolE}{}
\DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n}
\SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n}
\DeclareFontShape{OMX}{MnSymbolE}{m}{n}{
    <-6>  MnSymbolE5
   <6-7>  MnSymbolE6
   <7-8>  MnSymbolE7
   <8-9>  MnSymbolE8
   <9-10> MnSymbolE9
  <10-12> MnSymbolE10
  <12->   MnSymbolE12}{}

% Declare specific arrows from txfonts without loading the full package
\makeatletter
\def\re@DeclareMathSymbol#1#2#3#4{%
    \let#1=\undefined
    \DeclareMathSymbol{#1}{#2}{#3}{#4}}
\re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46}
\re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12}
\re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64}
\re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6}
\re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77}
\re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77}
\makeatother

% \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE
\makeatletter
\def\Decl@Mn@Delim#1#2#3#4{%
  \if\relax\noexpand#1%
    \let#1\undefined
  \fi
  \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}}
\def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}}
\def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}}
\Decl@Mn@Open{\llangle}{mnomx}{'164}
\Decl@Mn@Close{\rrangle}{mnomx}{'171}
\Decl@Mn@Open{\lmoustache}{mnomx}{'245}
\Decl@Mn@Close{\rmoustache}{mnomx}{'244}
\makeatother

% Widecheck
\makeatletter
\DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}}
\def\@widecheck#1#2{%
    \setbox\z@\hbox{\m@th$#1#2$}%
    \setbox\tw@\hbox{\m@th$#1%
       \widehat{%
          \vrule\@width\z@\@height\ht\z@
          \vrule\@height\z@\@width\wd\z@}$}%
    \dp\tw@-\ht\z@
    \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@
    \setbox\tw@\hbox{%
       \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box
\tw@}}}%
    {\ooalign{\box\tw@ \cr \box\z@}}}
\makeatother

% \mathraisebox{voffset}[height][depth]{something}
\makeatletter
\NewDocumentCommand\mathraisebox{moom}{%
\IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{%
\IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}%
}{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}%
\mathpalette\@temp{#4}}
\makeatletter

% udots (taken from yhmath)
\makeatletter
\def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.}
\mkern2mu\raise4\p@\hbox{.}\mkern1mu
\raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}}
\makeatother

%% Fix array
\newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}}
%% \itexnum is a noop
\newcommand{\itexnum}[1]{#1}

%% Renaming existing commands
\newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}}
\newcommand{\widevec}{\overrightarrow}
\newcommand{\darr}{\downarrow}
\newcommand{\nearr}{\nearrow}
\newcommand{\nwarr}{\nwarrow}
\newcommand{\searr}{\searrow}
\newcommand{\swarr}{\swarrow}
\newcommand{\curvearrowbotright}{\curvearrowright}
\newcommand{\uparr}{\uparrow}
\newcommand{\downuparrow}{\updownarrow}
\newcommand{\duparr}{\updownarrow}
\newcommand{\updarr}{\updownarrow}
\newcommand{\gt}{>}
\newcommand{\lt}{<}
\newcommand{\map}{\mapsto}
\newcommand{\embedsin}{\hookrightarrow}
\newcommand{\Alpha}{A}
\newcommand{\Beta}{B}
\newcommand{\Zeta}{Z}
\newcommand{\Eta}{H}
\newcommand{\Iota}{I}
\newcommand{\Kappa}{K}
\newcommand{\Mu}{M}
\newcommand{\Nu}{N}
\newcommand{\Rho}{P}
\newcommand{\Tau}{T}
\newcommand{\Upsi}{\Upsilon}
\newcommand{\omicron}{o}
\newcommand{\lang}{\langle}
\newcommand{\rang}{\rangle}
\newcommand{\Union}{\bigcup}
\newcommand{\Intersection}{\bigcap}
\newcommand{\Oplus}{\bigoplus}
\newcommand{\Otimes}{\bigotimes}
\newcommand{\Wedge}{\bigwedge}
\newcommand{\Vee}{\bigvee}
\newcommand{\coproduct}{\coprod}
\newcommand{\product}{\prod}
\newcommand{\closure}{\overline}
\newcommand{\integral}{\int}
\newcommand{\doubleintegral}{\iint}
\newcommand{\tripleintegral}{\iiint}
\newcommand{\quadrupleintegral}{\iiiint}
\newcommand{\conint}{\oint}
\newcommand{\contourintegral}{\oint}
\newcommand{\infinity}{\infty}
\newcommand{\bottom}{\bot}
\newcommand{\minusb}{\boxminus}
\newcommand{\plusb}{\boxplus}
\newcommand{\timesb}{\boxtimes}
\newcommand{\intersection}{\cap}
\newcommand{\union}{\cup}
\newcommand{\Del}{\nabla}
\newcommand{\odash}{\circleddash}
\newcommand{\negspace}{\!}
\newcommand{\widebar}{\overline}
\newcommand{\textsize}{\normalsize}
\renewcommand{\scriptsize}{\scriptstyle}
\newcommand{\scriptscriptsize}{\scriptscriptstyle}
\newcommand{\mathfr}{\mathfrak}
\newcommand{\statusline}[2]{#2}
\newcommand{\tooltip}[2]{#2}
\newcommand{\toggle}[2]{#2}

% Theorem Environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{cor}{Corollary}
\newtheorem*{utheorem}{Theorem}
\newtheorem*{ulemma}{Lemma}
\newtheorem*{uprop}{Proposition}
\newtheorem*{ucor}{Corollary}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{example}{Example}
\newtheorem*{udefn}{Definition}
\newtheorem*{uexample}{Example}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem{note}{Note}
\newtheorem*{uremark}{Remark}
\newtheorem*{unote}{Note}

%-------------------------------------------------------------------

\begin{document}

%-------------------------------------------------------------------


\section*{order polynomial}

\hypertarget{context}{}\subsubsection*{{Context}}\label{context}

\hypertarget{combinatorics}{}\paragraph*{{Combinatorics}}\label{combinatorics}

[[!include combinatorics - contents]]

\hypertarget{contents}{}\section*{{Contents}}\label{contents}

\noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak
\noindent\hyperlink{definition}{Definition}\dotfill \pageref*{definition} \linebreak
\noindent\hyperlink{examples}{Examples}\dotfill \pageref*{examples} \linebreak
\noindent\hyperlink{properties}{Properties}\dotfill \pageref*{properties} \linebreak
\noindent\hyperlink{relation_to_zeta_polynomial}{Relation to zeta polynomial}\dotfill \pageref*{relation_to_zeta_polynomial} \linebreak
\noindent\hyperlink{relation_to_the_strict_order_polynomial}{Relation to the strict order polynomial}\dotfill \pageref*{relation_to_the_strict_order_polynomial} \linebreak
\noindent\hyperlink{computational_complexity}{Computational complexity}\dotfill \pageref*{computational_complexity} \linebreak
\noindent\hyperlink{related_concepts}{Related concepts}\dotfill \pageref*{related_concepts} \linebreak
\noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak


\hypertarget{idea}{}\subsection*{{Idea}}\label{idea}

The \textbf{order polynomial} $\Omega_P(n)$ of a finite [[partially ordered set]] $P$ counts the number of ways that $P$ can be extended to a [[linear order]] of size $n$.

\hypertarget{definition}{}\subsection*{{Definition}}\label{definition}

By a \emph{linear extension} of $P$ of size $n$, we mean an [[order-preserving function]] from $P$ to $(n) = \{ 1 \lt \cdots \lt n \}$. To see that

\begin{displaymath}
\Omega_P(n) = |Hom(P,(n))|
\end{displaymath}
defines a [[polynomial]] in $n$, first observe that any function $P \to (n)$ factors as a [[surjection]] from $P$ onto some $(k) = \{ 1 \lt \cdots \lt k \}$ (where $k \le n$), followed by an [[injection]] from $(k)$ to $(n)$. The total number of order-preserving functions from $P$ to $(n)$ can therefore be calculated explicitly as

\begin{displaymath}
\Omega_P(n) = \sum_{k=1}^{|P|} e_k \binom{n}{k}
\end{displaymath}
where $e_k$ is the number of surjective order-preserving functions from $P$ to $(k)$. Hence $\Omega_P(n)$ is a polynomial of degree equal to the cardinality of $P$.

\hypertarget{examples}{}\subsection*{{Examples}}\label{examples}

The order polynomial of $(3) = \{ 1 \lt 2 \lt 3 \}$ is

\begin{displaymath}
n + 2 \binom{n}{2} + \binom{n}{3} = \frac{n^3 + 3n^2 + 2n}{6}
\end{displaymath}
For example, evaluating the polynomial at $n=3$ confirms that there are 10 order-preserving functions from $(3)$ to itself.

The order polynomial of the 3-element poset

\begin{displaymath}
P = \itexarray{&&c&& \\ &\nearrow& &\nwarrow& \\ a &&&& b}
\end{displaymath}
is $n + 3 \binom{n}{2} + 2\binom{n}{3} = \frac{2n^3 + 3n^2 + n}{6}$. Evaluating at $n=2$, we compute that there are 5 order-preserving functions from $P$ onto $(2)$.

\hypertarget{properties}{}\subsection*{{Properties}}\label{properties}

\hypertarget{relation_to_zeta_polynomial}{}\subsubsection*{{Relation to zeta polynomial}}\label{relation_to_zeta_polynomial}

Let $P^\downarrow \cong (2)^P$ denote the lattice of [[lower sets]] in $P$. The order polynomial of a finite poset $P$ is related to the [[zeta polynomial]] of its lattice of lower sets $P^\downarrow$ by the equation\footnote{Note that the definition we use for $Z_P(n)$ has an index shift from the definition that seems to be more standard in combinatorics (see the footnote at [[zeta polynomial]]), so this equation is sometimes expressed as $\Omega_P(n) = Z_{P^\downarrow}(n)$.} 

\begin{displaymath}
\Omega_P(n+2) = Z_{P^\downarrow}(n)
\end{displaymath}
This can be seen as a consequence of the [[currying]] isomorphisms

\begin{displaymath}
Hom([n], P^\downarrow) \cong Hom([n] \times P, (2)) \cong Hom(P, [n]^\downarrow)
\end{displaymath}
together with the isomorphisms $[n]^\downarrow \cong [n+1] \cong (n+2)$.

\hypertarget{relation_to_the_strict_order_polynomial}{}\subsubsection*{{Relation to the strict order polynomial}}\label{relation_to_the_strict_order_polynomial}

Let $\bar{\Omega}_P(n)$ denote the number of [[strict order-preserving functions]] from $P$ to $(n)$, that is, functions $f : P \to (n)$ such that $x \lt y$ implies $f(x) \lt f(y)$. This again defines a polynomial in $n$, called the \textbf{strict order polynomial} of $P$. The strict order polynomial of a finite poset $P$ is related to its order polynomial by the equation

\begin{displaymath}
\bar{\Omega}_P(n) = (-1)^p \Omega_P(-n)
\end{displaymath}
where $p = |P|$ is the cardinality of $P$. This is an example of a \emph{combinatorial reciprocity theorem} in the sense of \hyperlink{Stanley74}{Stanley (1974)}.

(Notice that we are evaluating the order polynomial at a negative integer, even though the putative definition $\Omega_P(n) = |Hom(P,(n))|$ only makes sense for natural numbers $n$. This is justified because the value of a polynomial on the natural numbers determines its value on arbitrary integers.)

As an example, the strict order polynomial of the 3-element poset $P$ defined above is $\bar{\Omega}_P(n) = \frac{2n^3 - 3n^2 + n}{6}$. Evaluation at $n=2$ confirms that there is exactly one strict monotone map from $P$ to a 2-element linear order (sending both $a$ and $b$ to the first element and $c$ to the second element).

Through [[Möbius inversion]], this equation relating the strict order polynomial to the order polynomial can be connected to the previous one relating the order polynomial to the zeta polynomial. Since the lattice of lower sets $P^\downarrow$ has [[bottom]] and [[top]] elements, we know that

\begin{displaymath}
\Omega_P(n) = Z_{P^\downarrow}(n-2) = \zeta^n(\emptyset,P)
\end{displaymath}
where $\zeta^n$ is the $n$-fold convolution of the zeta function of $P^\downarrow$. One can similarly work out that

\begin{displaymath}
\bar{\Omega}_P(n) = (-1)^p\mu^n(\emptyset,P)
\end{displaymath}
where $\mu^n$ is the $n$-fold convolution of the [[Möbius function]] of $P^\downarrow$. The equation $\bar{\Omega}_P(n) = (-1)^p \Omega_P(-n)$ then follows formally from the fact that $\mu = \zeta^{-1}$.

\hypertarget{computational_complexity}{}\subsubsection*{{Computational complexity}}\label{computational_complexity}

Counting the number of total linear extensions of a poset (i.e., number of linear extensions of an $n$-element poset to a linear order of size $n$) is a \#P-complete problem \hyperlink{BW1991}{(Brightwell and Winkler 1991)}, and thus so is the problem of computing the leading coefficient of the order polynomial (cf. \hyperlink{BHK2017}{Browning, Hopkins, and Kelley 2017}).

\hypertarget{related_concepts}{}\subsection*{{Related concepts}}\label{related_concepts}

\begin{itemize}%
\item [[zeta polynomial]]
\item [[incidence algebra]]
\item [[Möbius inversion]]

\end{itemize}
\hypertarget{references}{}\subsection*{{References}}\label{references}

\begin{itemize}%
\item Richard P. Stanley. Ordered structures and partitions. Memoirs of the AMS 119, 1972. (\href{http://www.ams.org/books/memo/0119/}{doi}) (Free copy available from the \href{http://www-math.mit.edu/~rstan/pubs/}{author's website}, see \#9.)

\end{itemize}
\begin{itemize}%
\item Richard P. Stanley. Combinatorial Reciprocity Theorems. Advances in Mathematics 14:194-253, 1974. (Free copy available from the \href{http://www-math.mit.edu/~rstan/pubs/}{author's website}, see \#22.)

\end{itemize}
\begin{itemize}%
\item Joseph P. S. Kung, [[Gian-Carlo Rota]], Catherine H. Yan. Combinatorics: The Rota Way. Cambridge, 2009.


\item Graham Brightwell and Peter Winkler. Counting Linear Extensions. \emph{Order} 8:225-242, 1991. \href{https://doi.org/10.1007/BF00383444}{doi}


\item Thomas Browning, Max Hopkins, and Zander Kelley. Doppelgangers: the Ur-Operation and Posets of Bounded Height. \href{https://arxiv.org/abs/1710.10407}{arXiv:1710.140407}



\end{itemize}
category: combinatorics



\end{document}