%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2018}
\articlenumber{80}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}
\usepackage{mathrsfs,pgf,tikz,caption,subcaption,hyperref,mathtools}
\usepackage[colorinlistoftodos]{todonotes}
\usetikzlibrary{decorations.pathreplacing}
\usepackage{inputenc}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}

\usepackage{lipsum}


%% define your title in the usual way
\title{Doppelgangers: the Ur-Operation and Posets of Bounded Height
(extended abstract)}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Thomas
Browning\thanks{\href{mailto:tb65536@uw.edu}{tb65536@uw.edu}}\addressmark{1},
Max
Hopkins\thanks{\href{mailto:nmhopkin@eng.ucsd.edu}{nmhopkin@eng.ucsd.edu}}\addressmark{2}, \and
Zander Kelley\thanks{\href{mailto:awk2@illinois.edu}{awk2@illinois.edu}. Browning, Hopkins, and Kelley were partially supported by NSF Grant DMS-1460937.}\addressmark{3}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, University of
Washington, Seattle, WA \\ \addressmark{2}Department of Computer Science
and Engineering, University of California, San Diego, CA\\ \addressmark{3}Department of Computer Science, University of Illinois, Urbana-Champaign, IL}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{In the early 1970s, Richard Stanley and Kenneth Johnson
introduced and laid the groundwork for studying the order polynomial of
partially ordered sets (posets). Decades later, Hamaker, Patrias,
Pechenik, and Williams introduced the term ``doppelgangers'': equivalence
classes of posets given by equality of the order polynomial. We provide
necessary and sufficient conditions on doppelgangers through application
of both old and novel tools, including new recurrences and the
Ur-operation: a new generalized poset operation. In addition, we prove
that the doppelgangers of posets P of bounded height $|P|-k$ may be
classified up to systems of $k$ diophantine equations in $2^{O(k^2)}$
time, and similarly that the order polynomial of such posets may be
computed in $O(|P|)$ time. The full version of this paper may be found at
\url{https://arxiv.org/abs/1710.10407}.} 

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{posets, order polynomial, bounded height}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{80-Browning-Hopkins-Kelley.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}
\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}
\subsection{Background}
Richard Stanley introduced the order polynomial $F_P(m)$ of an unlabeled partially ordered set (poset) in 1970 as an analog to chromatic polynomials \cite{Order}. Soon after, Johnson introduced a recurrence relation on the order polynomial of unlabeled posets \cite{Johnson} which Stanley expanded upon through the introduction of induction on incomparable elements, a powerful tool for studying posets. Computing the order polynomial is difficult. For instance, Brightwell and Winkler proved that computing even the first coefficient of the order polynomial (counting linear extensions) is \#P-complete \cite{complexity}. Despite this, Faigle and Schrader proved that the order polynomial of special families, series-parallel posets and posets of bounded (constant) width, may be computed in polynomial time \cite{Faigle}. 

More recently, Boussicault, Feray, Lascoux, and Reiner examined posets from a geometric perspective by studying linear extension sums as valuations over polyhedral cones \cite{Feray2}. In their work, the authors re-introduce induction on incomparable elements, extending a simple recurrence on linear extensions to valuations. In 2014, McNamara and Ward \cite{McNamara} set out to classify the equivalence classes of the multivariate generating function $K_{(P,\omega)}$, a function introduced by Gessel in 1983 \cite{Ges}, and closely related to the labeled order polynomial $\Omega_{P,\omega}(m)$. In their work, McNamara and Ward prove a number of important poset invariants for $K_{P,\omega}(m)$, and offer several conjectures and unexplained equivalences--one of which we explain in section \ref{sp-results}. Later, Hamaker, Patrias, Pechenik and Williams coined the term doppelgangers for unlabeled posets with the same order polynomial, and demonstrated several examples related to the K-theory of miniscule varieties \cite{Hamaker}. Their paper focuses on infinite families of grid-like doppelgangers, raising the natural question of the existence and importance of similar families. We apply Johnson's initial recurrence to $F_P(m)$ as well as a new recurrence on both $\Omega_{P,\omega}(m)$ and $K_{(P,\omega)}$ similar to that used in \cite{Feray2} in order to further study doppelgangers. 
\subsection{Results}
\label{sec:results}
Our work begins with an exploration of the interaction between doppelgangers and the standard poset operations disjoint union and ordinal sum, the operations used to build series-parallel posets.
To this end, we introduce a number of recurrences that require the following definitions.
%To this end, we re-introduce Johnson's unlabeled recurrence and consider novel recurrences on $\Omega_{P,\omega}$ and $K_{P,\omega}$, which are closer in form to that used in \cite{Feray2}.
For incomparable elements $x,y$, let $P|x\leq y$ be the poset with added cover relation $x \lessdot y$ and all further relations required by transitivity, and $P|x=y$ be $P$ with $x$ and $y$ identified. In particular, if $v$ is the identification of $x$ and $y$ then $z\leq v$ in $P|x=y$ if and only if $z\leq x$ in $P$ or $z\leq y$ in $P$. Finally, given a labeled poset $(P,\omega)$, let $(P,\omega)|x<y$ be the poset $(P,\omega)$ with the added \textit{strict} relation $x<y$ and all other relations implied by transitivity. Note that $(P,\omega)|x<y$ may not correspond to a labeled poset. 

Recall that $F_P(m)$ counts the number of order-preserving maps $P\to[m]=\{1,\ldots,m\}$. $\Omega_{P,\omega}(m)$ counts the number of $(P,\omega)$-partitions into $[m]$--order preserving maps $P\to[m]$ that are consistent with the labeling $\omega$ (a bijection between $P$ and $[|P|]$). Finally, $K_{P,\omega}(x)$ is a sum over all $(P,\omega)$-partitions $f$ of the product of $x_j^{|f^{-1}(j)|}$ for each $j\geq1$.
More detail regarding these definitions can be found at the end of Section 2.
\begin{lemma}
\label{Irec}
The order polynomial and multivariate generating function admit the following recurrences:
\begin{align}
F_P &=F_{P|x\leq y}+F_{P|y\leq x}-F_{P|x=y}\\
\Omega_{P,\omega} &=\Omega_{P|x\leq y,\omega}+\Omega_{P|y\leq x,\omega}\\
K_{P,\omega} &=K_{P|x<y,\omega}+K_{P|y\leq x,\omega}
\end{align}
\end{lemma}
The objects $P|x<y,\omega$ and $P|y\leq x,\omega$ in $(1.3)$ might not be posets, but these objects remain valid for the purpose of calculating $K_{P,\omega}$. While we mostly focus on these recurrences to examine ordinal sum, they provide further results on doppelgangers as well. For instance, just a single step of recurrence $(1.1)$ provides new infinite families.
\begin{example}
\label{ex:fam_1}
For each $n\geq 2$, the posets $P_1$ and $P_2$ below are doppelgangers.
\begin{center}
\begin{tabular}{c c}
\begin{tikzpicture}[scale=0.3]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,0) (a) {\tiny x};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,2) (b) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (2,0) (c) {\tiny y};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (2,2) (d) {};
\draw[dotted] (a) -- (b);
\draw[dotted] (c) -- (d);
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.5,-0.3) -- (-0.5,2.3) node [black,midway,xshift=-0.35cm]
{\footnotesize $n$};
\draw [decorate,decoration={brace,amplitude=5pt}]
(1.5,-0.3) -- (1.5,2.3) node [black,midway,xshift=-0.35cm]
{\footnotesize $n$};
\end{tikzpicture}
&\begin{tikzpicture}[scale=0.3]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,0) (a) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,2) (b) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (-1,2) (c) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (2,4) (f) {\tiny x};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,4) (g) {\tiny y};
\draw[dotted] (c) -- (a) -- (b);
\draw (g) -- (b) -- (f);
\draw [decorate,decoration={brace,amplitude=5pt},rotate=9]
(-0.5,-0.4) -- (-1.4,2.2) node [black,midway,xshift=-0.4cm,yshift=-.15cm]
{\footnotesize $n$};
\draw [decorate,decoration={brace,mirror,amplitude=5pt},rotate=-10]
(0.5,-0.4) -- (1.4,2.2) node [black,midway,xshift=0.7cm,yshift=-.15cm]
{\footnotesize $n-1$};
\end{tikzpicture}
\\$P_1$
&$P_2$
\end{tabular}
\end{center}
We have the isomorphisms $(P_1|x\leq y)\cong(P_2|x\leq y)$, $(P_1|y\leq x)\cong(P_2|y\leq x)$, and $(P_1|x=y)\cong(P_2|x=y)$.
Since isomorphic posets have the same order polynomial, Equation 1.1 from Lemma 1.1 shows that $F_{P_1}=F_{P_2}$. Setting $n = 2$, we recover the Nicomachus formula
\[
\sum\limits_{k=1}^m k^3 = F_{P_2} = F_{P_1} = \left (\sum\limits_{k=1}^m k \right )^2
\]
\end{example}

In their work, McNamara and Ward offer four pairs of posets with equivalent $K_{P,\omega}$ which their methods do not explain as a springboard for further investigation \cite{McNamara}. Our improper recurrence, Equation (1.3), easily shows the first of these pairs, given in Figure \ref{fig:MW}, have equivalent $K_{P, \omega}$.
We expect Lemma \ref{Irec} has far reaching consequences for $K_{P,\omega}$.

In order to study the interaction of doppelgangers and the ordinal sum, we combine these recurrences with Stanley's method of induction on incomparable elements \cite{Stanley1}, re-introduced recently in \cite{Feray2}. This method provides elegant proofs of old results such as Stanley's poset reciprocity theorem \cite{Order}, and provides a basis for the order polynomial which interacts well with ordinal sum (see Proposition \ref{basisformula}), leading to the following results. Recall that the ordinal sum of $P$ and $Q$, $P \oplus Q$, follows from stacking the Hasse diagrams of $P$ and $Q$. We say $P \sim Q$ when $F_P(x) = F_Q(x)$.
Using induction on incomparable elements, we show in Lemma 3.2 that the order polynomial of an ordinal sum $P\oplus Q$ is given by the Cauchy product of the order polynomials of $P$ and $Q$ in a basis of binomial coefficients.
As corollaries of Lemma 3.2, we have the following results.
\begin{corollary}
\label{I2-3}
For labeled posets $(P,\omega),(P^\prime,\omega^\prime),(Q,\psi),(Q^\prime,\psi^\prime)$, any two conditions imply the third:

1) $(P,\omega)\sim(P^\prime,\omega^\prime)$

2) $(Q,\psi)\sim(Q^\prime,\psi^\prime)$

3) $(P\oplus Q,\omega\oplus\psi)\sim(P^\prime\oplus Q^\prime,\omega^\prime\oplus\psi^\prime)$
\end{corollary}
\begin{corollary}
\label{Isym}
For all labeled posets $(P,\omega),(Q,\psi)$,
\[(P\oplus Q,\omega\oplus\psi)\sim(Q\oplus P,\psi\oplus\omega).\]
\end{corollary}

While Lemma \ref{Irec} and Corollaries \ref{I2-3} and \ref{Isym} explain a large number of small and series-parallel doppelgangers, there are examples of size $\geq 6$ (see Example \ref{Ur-ex}) they cannot explain. To this end, we introduce a new poset operation to generalize Corollaries \ref{I2-3} and \ref{Isym}. 
\begin{definition}
\label{Ur-def}
For a poset $\mathscr{P}=\{x_1,\cdots,x_n\}$ and a sequence of posets $\{P_1,\cdots,P_n\}$, let $\mathscr{P}[x_k\to P_k]_{k=1}^n$ be the poset on $\bigcup_kP_k$ with the following operation:
\[\text{For }p\in P_j,q\in P_k,\ p\leq q\text{ when }\begin{cases}p\leq q&j=k\\x_j\leq x_k&j\neq k\end{cases}.\]
We call this the Ur-operation on $\mathscr{P}$ by $\{P_1,\cdots,P_n\}$. If any $P_k$ is not specified, then that $P_k$ is assumed to be the poset on one element.
\end{definition}
\begin{example}
The Ur-operation generalizes disjoint union, ordinal sum, and ordinal product.
\begin{center}
\begin{tabular}{c c c c c c}
&
&
& $V + V$
& $V \oplus V$
& $V \otimes V$
\\
\begin{tikzpicture}[scale=0.27]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (-1,0) (a) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,0) (b) {};
\end{tikzpicture}
&\begin{tikzpicture}[scale=0.27]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,-1) (a) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,1) (b) {};
\draw (a) -- (b);
\end{tikzpicture}
&\begin{tikzpicture}[scale=0.27]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,0) (a) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (2,2) (b) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,2) (c) {};
\draw (b) -- (a) -- (c);
\end{tikzpicture}
&\begin{tikzpicture}[scale=0.27]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,0) (a) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (2,2) (b) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,2) (c) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (5,0) (d) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (6,2) (e) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (4,2) (f) {};
\draw (b) -- (a) -- (c);
\draw (e) -- (d) -- (f);
\end{tikzpicture}
&\begin{tikzpicture}[scale=0.27]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,0) (a) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (2,2) (b) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,2) (c) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,4) (d) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (2,6) (e) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,6) (f) {};
\draw (b) -- (a) -- (c);
\draw (e) -- (d) -- (f);
\draw (b) -- (d) -- (c);
\end{tikzpicture}
&\begin{tikzpicture}[scale=0.27]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,0) (a) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (2,2) (b) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,2) (c) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (3,4) (d) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (4,6) (e) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (2,6) (f) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (-1,4) (g) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,6) (h) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (-2,6) (i) {};
\draw (b) -- (a) -- (c);
\draw (e) -- (d) -- (f);
\draw (i) -- (g) -- (h);
\draw (b) -- (d);
\draw (c) -- (g);
\end{tikzpicture}
\\$A_2$
& $C_2$
&$V$
&$A_2[x _i\to V]_{i=1}^2$
&$C_2[x _i\to V]_{i=1}^2$
&$V[x_i \to V]_{i=1}^3$
\\
\end{tabular}
\end{center}
\end{example}
Further, using the operation we prove a generalization of Corollary \ref{I2-3}:
\begin{theorem}
For a poset $\mathscr P=\{x_1,\cdots,x_n\}$ and two sequences of posets $\{P_1,\ldots,P_n\}$ and $\{Q_1,\ldots,Q_n\}$ such that $P_i\sim Q_i$, we have that $\mathscr P[x_k\to P_k]_{k=1}^n\sim\mathscr P[x_k\to Q_k]_{k=1}^n$.
\label{Ur-thm}
\end{theorem}
Theorem \ref{Ur-thm} shows that elements of the same poset may be exchanged for doppelgangers while preserving equivalence. This raises the natural question of when distinct elements may be exchanged with the same result.
\begin{definition}
We say $x \in P,\ y \in Q$ are Ur-equivalent when $P[x \to R] \sim Q[y \to S]$ for all posets $R\sim S$.
\end{definition}
In Corollary \ref{urequivalenceresult} and Conjecture \ref{urequivalenceconjecture}, we offer a basic necessary and sufficient condition for Ur-equivalence, and conjecture a strengthening of the result.

Finally, we move to the classification of infinite families of doppelgangers. Faigle and Schrader proved that for posets with bounded width $k$, the order polynomial may be computed in $O(|P|^{2k+1})$ time. However, any algorithm to classify infinite families of doppelgangers must be constant with respect to $|P|$. We provide such an algorithm for posets of height $|P|-k$, a subfamily of Faigle and Schrader's posets of bounded width.
\begin{theorem}
\label{class-time}
For constant k, the doppelgangers among posets of height $|P|-k=n-k$ are
completely determined by sets of $k$ Diophantine equations computable in $2^{O(k^2)}$ time. In addition, $F_P(x)$ is computable in $O(n)$ time, and for $k=O(\frac{log(n)}{log(log(n))})$, the time is polynomial in $n$. 
\end{theorem}
Theorem \ref{class-time} takes advantage of several invariants on
doppelgangers we will introduce in Section \ref{sp-results}, as well as
the rigid structure of posets of bounded height. The improvement this
structure brings from $O(n^{2k+1})$ to $O(n)$ allows us to extend our
family of bounded height past the constant restriction imposed by Faigle
and Schrader on posets of bounded width. As an example, we provide the Diophantine equations for $k=1,2$ in Table \ref{tab:dio}, along with general solutions where possible.

\section{Doppelgangers and the Order Polynomial \label{notation}}
For a poset $P$, let $F_P(n)$ denote the number of order-preserving maps $f$ from $P$ to $\{1,2,\ldots,n\}$ -- that is, maps which satisfy $f(x) \leq f(y)$ whenever $x \leq y$ in $P$. 
Thus the numbers $F_P(n)$ provide a measure of how far the poset $P$ is from a total order. 
If two posets $P$ and $Q$ satisfy the equivalence $F_P(n) = F_Q(n)$ for all $n$, we will call them \textit{doppelgangers}, and we denote this fact by $P \sim Q$.
In this paper we establish certain structural properties of a pair of of posets $(P,Q)$ which are either necessary or sufficient conditions for $P \sim Q$. Stanley offered many necessary conditions in his early work and later as exercises in \textit{Enumerative Combinatorics} \cite{Stanley}. We provide some simple but important examples from these to aid intuition.
\begin{proposition}
If $P$ and $Q$ are doppelgangers, then $|P| = |Q|$ and $e(P) = e(Q)$.
\end{proposition}
Here, $e(P)$ is the number of \textit{linear extensions} of a poset $P$, order preserving bijections from $P\to[|P|]$. The above follows from the fact that the order polynomial is of degree $|P|$, and the leading coefficient is uniquely determined by $e(P)$. 

We recall several operations on posets and show that they behave well in relation to order polynomials. 
Let $P$ and $Q$ be posets: The \textit{disjoint union} of $P$ and $Q$, denoted $P + Q$, is constructed by taking the union of the elements of $P$ and $Q$ and inheriting the relations from $P$ and $Q$. The \textit{ordinal sum} of $P$ and $Q$, denoted $P \oplus Q$, is constructed by first taking $P + Q$,
and then imposing the relation $x \leq y$ for every $x \in P$ and $y \in Q$. 

\begin{proposition}
$F_{P+Q}(n) = F_{P}(n)F_Q(n).$
\end{proposition}

These operations can be used to generate larger, more complicated pairs of doppelgangers out of smaller pairs.
For example, if $Q \sim R$, then we get that
$$ F_{P+Q} = F_P F_Q = F_P F_R = F_{P+R},$$
and so $P + Q$ and $P + R$ are doppelgangers for all posets $P$.
Analogously, in Corollary \ref{I2-3} we will also see that $P \oplus Q$ and $P \oplus R$ are doppelgangers whenever $Q \sim R$. In fact, the Ur-operation provides a direct generalization of this property, given in Theorem \ref{blowuptheorem}.

The term doppelganger originally referred to unlabeled posets, but extends easily to labeled posets $(P,\omega)$. A \textit{labeled poset} $(P,\omega)$ is a poset $P$ equipped with a bijective labeling $\omega\colon P\to[|P|]$.
In this case, a map $f\colon(P,\omega)\to[m]$ is order-preserving when $f(x)\leq f(y)$ whenever $x\leq y$, and $f(x)<f(y)$ whenever $x<y$ and $\omega(x)>\omega(y)$. The number of such maps is the order polynomial of $(P,\omega)$, denoted $\Omega_{P,\omega}(m)$. In fact, every unlabeled poset $P$ may be written as a labeled poset $(P,\omega)$ where $\omega$ is a \textit{natural labeling} or a linear extension of $P$, that is when $\omega(x)<\omega(y)$ whenever $x<y$. In this case $F_P=\Omega_{P,\omega}$. In fact, labeled posets admit an interesting generalization of the order polynomial studied in recent work \cite{McNamara}. The \textit{multivariate generating function} of $(P,\omega)$ is
\[
K_{P,\omega}(x) = \sum\limits_{f \in (P,\omega)-\text{partitions}} x_1^{|f^{-1}(1)|}x_2^{|f^{-1}(2)|} \ldots
\]
Here, $(P,\omega)$-partitions differ from order preserving maps only in that they map to $\mathbb{Z}^+$.
\section{Order Polynomial Recurrence}
\subsection{Induction on Incomparable Elements \label{sp-results}}
Recall the poset operations introduced in Section \ref{sec:results}: $P|x\leq y$, $P|x=y$, and $P|x<y$. While this final operation might not result in a valid labeled poset, order preserving functions, and thus the order polynomial and multivariate generating functions, are still well-defined on these improper posets.

Equation (1.3) illuminates McNamara and Ward's first unexplained example (see Figure \ref{fig:MW}). This ends our discussion of $K_{P,\omega}$, but application of our methodology to the function is a possible direction of further research.
\begin{figure}[htb]
\begin{center}
\begin{tabular}{c c c c c c}
\begin{tikzpicture}[scale=0.3]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (-1,0) (a) {\tiny x};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,0) (b) {\tiny y};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (-1,2) (c) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,2) (d) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,4) (e) {};
\draw (b) -- (c) -- (a) -- (d);
\draw (d) -- (e);
\draw[double] (b) -- (d);
\end{tikzpicture}
&\begin{tikzpicture}[scale=0.3]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,0) (a) {\tiny x};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,2) (b) {\tiny y};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (-1,4) (c) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,4) (d) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,6) (e) {};
\draw (b) -- (c);
\draw (d) -- (e);
\draw[double] (b) -- (d);
\draw[double] (a) -- (b);
\end{tikzpicture}
&\begin{tikzpicture}[scale=0.3]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (-1,2) (a) {\tiny x};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,0) (b) {\tiny y};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (-1,4) (c) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,4) (d) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,6) (e) {};
\draw (c) -- (a) -- (d);
\draw (d) -- (e);
\draw[double] (b) -- (d);
\draw (a) -- (b);
\end{tikzpicture}
&\begin{tikzpicture}[scale=0.3]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,0) (a) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,2) (b) {\tiny y};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (-1,2) (c) {\tiny x};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,4) (d) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (-1,4) (e) {};
\draw (e) -- (c);
\draw (a) -- (b) -- (d);
\draw[double] (a) -- (c);
\end{tikzpicture}
&\begin{tikzpicture}[scale=0.3]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,0) (a) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,2) (b) {\tiny x};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (-1,4) (c) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,4) (d) {\tiny y};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,6) (e) {};
\draw (b) -- (c);
\draw (d) -- (e);
\draw[double] (b) -- (d);
\draw[double] (a) -- (b);
\end{tikzpicture}
&\begin{tikzpicture}[scale=0.3]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,2) (a) {\tiny y};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,0) (b) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,4) (c) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (-1,4) (d) {\tiny x};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (-1,6) (e) {};
\draw (c) -- (a) -- (d);
\draw (d) -- (e);
\draw[double] (b) -- (d);
\draw (a) -- (b);
\end{tikzpicture}
\\$P$
&$P|x < y$
&$P|y \leq x$
&$Q$
&$Q|x < y$
&$Q|y \leq x$\\
\end{tabular}
\end{center}
\caption{Equivalence of $K_{P,\omega}$ and $K_{Q,\omega}$. Double edges denoted strict order relations.}
\label{fig:MW}
\end{figure}

We use Lemma \ref{Irec} to prove results involving order polynomials by strong induction on the number of incomparable pairs of elements, as each of the terms of the recurrences have fewer such pairs than the original poset. It is clear from repeated applications of Equation (1.1) that the order polynomial of any poset should have an expression as the sum of the order polynomial of total orders, or \textit{chains}, with $F_{C_k} = \binom{m+k-1}{k}$ where $C_k$ is a chain of cardinality $k$. Indeed, as a consequence of poset reciprocity we can easily derive the expression for the order polynomial in the $\binom{m+k-1}{k}$ or \textit{chain basis}. 

\begin{proposition}
\label{basisformula}
For all posets $P$, there exist $c_k\in\mathbb{N}$ such that
\[F_P(m)=(-1)^{|P|}\sum_{k=h(P)}^{|P|}(-1)^kc_k\binom{m+k-1}{k}\]
where $h(P)$ is the height of $P$ and denotes the number of elements in the largest total order in $P$.
\end{proposition}

In the chain basis the coefficients of $F_{P \oplus Q}$ are given by the convolution of the coefficients of P with those of $Q$. Further, this extends to labeled posets and beyond the chain basis.
In particular, we generalize $\oplus$ to labeled posets in the following way:
given labeled posets $(P,\omega)$ and $(Q,\psi)$, let $\omega\oplus\psi$ be a labeling on $P\oplus Q$ given by
\[(\omega\oplus\psi)(x)=\begin{cases}\omega(x)&x\in P\\|P|+\psi(x)&x\in Q\end{cases}.\]
Then $(P\oplus Q,\omega\oplus\psi)$ is the labeled poset where every element of $P$ is weakly less than every element of $Q$.
\begin{lemma}
If $F_P(m) = \sum_{i=1}^{|P|} a_i {\binom{m + k - 1}{k}}$ and $F_Q(n) = \sum_{j=1}^{|Q|} b_j {\binom{m + k - 1}{k}}$, then
\[F_{P\oplus Q}(n) = \sum_{k=1}^{|P|+|Q|} \left( \sum_{i=1}^k a_i b_{k-i} \right) {\binom{m + k - 1}{k}}.\]
\end{lemma}
Corollaries \ref{I2-3}, \ref{Isym}, our results on doppelgangers with respect to ordinal sum, follow immediately. In Section 4, we will extend the unlabeled (naturally labeled) version of Corollary \ref{I2-3} to the Ur-operation. Despite its simplicity, Corollary \ref{Isym} has merit on its own, and easily recovers one of the doppelganger pairs discussed in \cite{Hamaker}.
If we let $C_n$ denote the total order on $n$ elements and if we let $A_n$ denote a collection of $n$ elements with no relations between them, then the posets in this example can be expressed by the ordinal sum as follows.
\begin{example}
$C_{n-1} \oplus A_2 \oplus C_{n-1} = \Lambda_{\mathbb{Q}^{2n}} \sim \Phi^{+}_{I_2(2n)} = A_2 \oplus C_{n-1} \oplus C_{n-1}$ (see Figure 1 in \cite{Hamaker}). This pair of doppelgangers is an immediate consequence of Corollary \ref{Isym}.
\end{example}

\section{The Ur-Operation}
Section \ref{sp-results} details the interactions of the order polynomial and standard poset operations. By considering the Ur-operation, Definition \ref{Ur-def}, it is possible in turn to extend our results. Recall the Ur-operation replaces some subset of points in a poset $\mathscr P$ by a corresponding set of posets $\{P_1,\cdots,P_k\}$, denoted by $\mathscr{P}[x_i\to P_i]_{i=1}^n$. Then the disjoint sum operation $P_1+P_2$ can be expressed as $A_2[x_k\to P_k]_{k=1}^2$, the ordinal sum operation $P_1\oplus P_2$ as $C_2[x_k\to P_k]_{k=1}^2$, and the ordinal product $P \otimes Q$ as $P[x_k\to Q]_{k=1}^n$. Here $A_2$ is the anti-chain, or completely un-ordered poset, of size $2$.

The order polynomial of the Ur-operation relies heavily on the structure $\mathscr P$. Therefore it is convenient throughout the rest of this section to have the following definition.
\begin{definition}
For a poset $\mathscr P$ and $x\in$ $\mathscr P$, define $g_x^P(n,m)$ to be the number of order-preserving maps $f: \mathscr P[x \to \varnothing] \to [m]$ such that $1 + \min\limits_{x\leq y}f(y)-\max\limits_{y\leq x}f(y) = n$, where the min and max are taken to be $m$ and $1$ respectively if not well defined.
\end{definition}
Note that $g_x^P(n,m)$ counts the number of ways to choose an order preserving map into $[m]$ such there are $n$ consistent choices for the value at $x$.
\subsection{The Order Polynomial}
With this in hand, we offer a simple formula for the order polynomial of a single substitution. The polynomial for the general operation may be given by repeated application
\begin{proposition}
\label{singleblowupformula}
For a poset $\mathscr{P}$ with $x\in\mathscr{P}$, a poset $Q$, and $m\geq1$,
\[F_{\mathscr{P}[x\to Q]}(m)=\sum_{n=1}^m g^{\mathscr P}_x(n,m)F_Q(n).\]
\end{proposition}
The Ur-operation generalizes the relation between ordinal sum and doppelgangers given by Corollaries \ref{I2-3} and \ref{Isym}.
In particular, we have Theorem 1.6 which we restate below.
\begin{theorem}
\label{blowuptheorem}
For a poset $\mathscr P=\{x_1,\cdots,x_n\}$ and two sequences of posets $\{P_1,\ldots,P_n\}$ and $\{Q_1,\ldots,Q_n\}$ such that $P_i\sim Q_i$, we have that $\mathscr P[x_k\to P_k]_{k=1}^n\sim\mathscr P[x_k\to Q_k]_{k=1}^n$.
\end{theorem}
\begin{example}
\label{Ur-ex}
The posets (d) and (e) below are doppelgangers by Theorem~\ref{blowuptheorem}. 
\begin{center}
\begin{tabular}{c c c c c}
\begin{tikzpicture}[scale=0.3]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,0) (a) {\tiny y};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,2) (b) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (2,2) (c) {\tiny x};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (2,0) (d) {};
\draw (a) -- (b) -- (d) -- (c);
\end{tikzpicture}
&\begin{tikzpicture}[scale=0.3]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,0) (a) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (2,2) (b) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,2) (c) {};
\draw (b) -- (a) -- (c);
\end{tikzpicture}
&\begin{tikzpicture}[scale=0.3]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,0) (a) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (2,0) (b) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,2) (c) {};
\draw (a) -- (c) -- (b);
\end{tikzpicture}
&\begin{tikzpicture}[scale=0.3]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,0) (a) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,2) (b) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (2,2) (c) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (2,0) (d) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (3,4) (e) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,4) (f) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (-1,-2) (g) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,-2) (h) {};
\draw (h) -- (a) -- (g);
\draw (a) -- (b) -- (d) -- (c);
\draw (c) -- (e);
\draw (c) -- (f);
\end{tikzpicture}
&\begin{tikzpicture}[scale=0.3]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,0) (a) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (-1,0) (g) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,-2) (h) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,2) (b) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (2,4) (c) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (2,0) (d) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (3,2) (e) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,2) (f) {};
\draw (a) -- (h) -- (g) -- (b);
\draw (a) -- (b) -- (d);
\draw (d) -- (e) -- (c) -- (f) -- (d);
\end{tikzpicture}
\\(a) $P$
&(b) $Q$
&(c) $Q^*$
&(d) $P[x \to Q, y \to Q^*]$
&(e) $P[x \to Q^*,y \to Q]$
\end{tabular}
\end{center}

Due to the underlying non-series-parallel structure of $P$, this does not follow from Corollaries \ref{I2-3} or \ref{Isym}, nor does it follow from a single application of Johnson's recurrence.
\end{example}

Theorem~\ref{blowuptheorem} allows us to build new doppelgangers out of an arbitrary poset by iteratively replacing points with corresponding doppelgangers. We know as well, however, that one can construct doppelgangers by replacing different points of some poset P with corresponding doppelgangers, such as in $C_k$ or $A_k$. It is natural then to ask about a generalization of this occurrence. For posets $P$ and $Q$ with $x\in P$ and $y\in Q$, when do we have $P[x \to R] \sim Q[y \to S]$ for all doppelgangers $R\sim S$?
\subsection{Ur-Equivalence}
\begin{definition}
We say $x \in P,\ y \in Q$ are Ur-equivalent when $P[x \to R] \sim Q[y \to S]$ for all posets $R\sim S$.
\end{definition}
Ur-equivalence relies on the same structure the order polynomial does: for $x \in P$ and $y \in Q$, $x$ and $y$ are Ur-equivalent if and only if $g^P_x = g^Q_y$.
As a corollary of this result, we have the following.
\begin{corollary}
\label{urequivalenceresult}
For $x \in P$ and $y \in Q$ with $|P|=|Q|=n$, $x$ and $y$ are Ur-equivalent if and only if there exist posets $\{S_1,\cdots, S_n\}$ with $|S_i|=i$ such that $P[x\to S_i]\sim Q[y\to S_i], \ \forall \ i \in [n]$
\end{corollary}
Unfortunately, while $g_x^P$ reveals the structure behind Ur-equivalence, in general it is too difficult to calculate to be of practical use. However, one may note that $g_x^P$ is totally determined by the structure of $P[x \to \varnothing]$ and its relation to $P$. The structure of $g_x^P$ suggests that we may be able to strengthen the Corollary \ref{urequivalenceresult}:
\begin{conjecture}
\label{urequivalenceconjecture}
For $x \in P$ and $y \in Q$, $x$ and $y$ are Ur-equivalent if and only if $P \sim Q$ and $P[x\to \varnothing]\sim Q[y\to \varnothing]$.
\end{conjecture}
The conjecture holds for small posets, and like the order polynomial, $g_x^P$ has significant extra structure that could be leveraged to prove such a result.

\section{Posets of Bounded Height}
Due to the computational complexity of the order polynomial, a general
classification of doppelgangers seems hopeless. However, there are
certain large families for which the order polynomial is computable in
polynomial time. For instance, Faigle and Schrader showed that the order
polynomial of $P \in \mathscr W_k$, the set $\{P \in \mathscr P_n \ | \
w(P) \leq k\}$ may be computed in $O(n^{2k+1})$. While this set does not
have a rigid enough structure to permit classification, a special subset
does. Consider $\mathscr H_k$ $\subset \mathscr W_k$, the set $\{P \in
\mathscr P_n \ | \ h(P) = n-k\}$. We will leverage invariants on
doppelgangers and the rigid structure of $\mathscr H_k$ to prove that one
may reduce classification of doppelgangers to $k$ Diophantine equations in $2^{O(k^2)}$ time. In addition, we show that for constant k the order polynomial of posets in this class has time complexity $O(n)$, and is computable in polynomial time for $k=O(log(n)/log(log(n)))$.
\subsection{Invariants}
Proposition \ref{basisformula} introduces an important restriction on the roots of the order polynomial, first shown by Stanley \cite{Order}. Recall that the height of $P$, $h(P)$, is the cardinality of the largest total ordering contained in $P$.
\begin{lemma}
\label{rootresult}
$F_P(x)$ vanishes at $x=0,-1,\ldots,-h(P)+1$ but not at $-h(P),-h(P)-1,\ldots$.
\end{lemma}
In particular, doppelganger posets have the same height. 
In fact, combining Lemma \ref{rootresult} with a number other simple invariants, we produce a set of necessary and sufficient conditions for doppelgangers.
\begin{proposition}
\label{prop:classification}
$P\sim Q$ if and only if $|P|=|Q|$, $h(P)=h(Q)$, $e(P)=e(Q)$, and $F_P(x)=F_Q(x)$  at $|P|-h(P)-1$ distinct $x$--not counting the trivial agreement at $1,0,-1,\ldots,-h(P)$.
\end{proposition}
In the section that follows we will not use the $e(P)$ invariant, but it is particularly useful for enumerating $\mathscr H_1$ and $\mathscr H_2$.
\subsection{Classifying \texorpdfstring{$\mathscr H_k$}{Lg}}
The height invariant, Corollary \ref{rootresult}, and the underlying
structure of $\mathscr H_k$ allow us to theoretically classify all its
doppelgangers in time dependent on $k$ and compute their order
polynomials in $O(n)$ time. Consider a poset $P \in \mathscr H_k$. We may
view this poset as a set of ``on-chain'' elements $x_1 \leq \cdots \leq
x_h(p)$, and $k$ ``off-chain'' elements. For every off-chain element x, there exist nonnegative integers $a+b+c=h$ such that $x$ is greater than $x_1,\cdots,x_a$, $x$ is incomparable to $x_{a+1},\cdots,x_{a+b}$, and $x$ is less than $x_{a+b+1},\cdots,x_{a+b+c}$. The relative structure of these off-chain to on-chain elements is key to computing $F_P(m)$.
\begin{lemma}
\label{lem:F_P}
Let $P$ be a finite poset consisting of a chain $x_1\leq\ldots\leq x_{h(P)}$ and $k=|P|-h(P)$ other elements off the chain $y_1,\ldots,y_k$. Applying the above argument to each $y_i$ results in values $a+b+c=h$ for each term. For convenience, we define $(a_1 \leq \ldots \leq a_{2k})$ to be the ordering of these $2k$ values, and further define $a_0=0\leq a_1$, and $a_{2k+1} = h(P)+1 \geq a_{2k}$. Let $d_i, 0 \leq i \leq 2k$, be the difference between the $i$ and $i+1$st terms in this sequence, i.e. $d_i = a_{i+1}-a_{i}$. The value of $F_P(m)$ is a polynomial in the $d_i$ and can be computed in $O(m^{3k+1})$.
\end{lemma}
To see the above, begin by summing over at most $m^k$ possible choices of the values for some order preserving $f: |P| \to [m]$ on an off-chain elements $x$. For each choice of the value of $f$ on the $x$, we sum over the possible choices for how many times $f$ increases between each $x_{a_i}$ and $x_{a_i+1}$. The number of ways to arrange these increases is a polynomial in $m$ of degree at most $2k+1$. Together with our $m^k$ possible choices this gives $O(m^{3k+1})$. In fact, given the $d_i$ of Lemma \ref{lem:F_P}, we need only compute $F_P(1)\ldots F_P(k)$ to get the order polynomial. Thus the rate limiting step becomes computing the $a_i$ and $d_i$ for a given poset $P$.
\begin{lemma}
\label{lem:F_P2}
Given a poset $P$, $|P|=n$, with $h(P)=n-k$, computing the $a_i$ and $d_i$ of Lemma \ref{lem:F_P} takes $O(n)$ time.
\end{lemma}
This result follows from bounding the number of edges in the Hasse diagram of $|P|$, and then finding maximal paths in the graph in linear time. Lemma \ref{lem:F_P2} provides the key step to calculate $F_P$, but classifying doppelgangers does not require this computation. The limiting step in classification becomes enumerating all possible poset structures of off-chain elements, which may take up to $2^{O(k^2)}$ time. Together, this relative off and on-chain structure and Lemmas \ref{lem:F_P} and \ref{lem:F_P2} allow us to prove Theorem \ref{class-time}.
\subsection{Example: \texorpdfstring{$\mathscr H_1$}{Lg} and \texorpdfstring{$\mathscr H_2$}{Lg}}
While for large k, classifying the $\mathscr H_k$ may be computationally
intractable, $\mathscr H_1$ and $\mathscr H_2$ are simple enough to
compute by hand. We provide a classification of these families as an
example of the above method, and show how the Diophantine equations lead to new infinite families of doppelgangers. We begin by enumerating the families of $\mathscr H_1$ and $\mathscr H_2$
\begin{proposition}
All posets $P$ with $|P|-h(P)=1$ are isomorphic to a poset depicted by Figure~\ref{fig:h2}(a). All posets $P$ with $|P|-h(P)=2$ are isomorphic to poset depicted by Figures~\ref{fig:h2}(b-e).
\end{proposition}
The values of the invariants for the posets in Figure~\ref{fig:h2} are given in Table \ref{tab:dio} and the computation of these values can be found in the appendix of \cite{Ur}.
The result of this table is that we can compute all doppelgangers among posets of height at most $|P|-2$ by solving various pairs of Diophantine equations. In fact, Table \ref{tab:dio} implies that all doppelgangers between Tri and Tri, and Dtri and Dtri are completely determined by Corollary \ref{Isym}. In addition, doppelgangers between Ntri and Ntri are given by Corollary \ref{Isym} and the equivalence Ntri$(m_2,m_3,m_4)$ = Ntri$(3b-c-2(d+e),b,c)$ $\sim$ Ntri$(d,2b-d-e,e)$. Further examples of infinite doppelganger families following from Table 1 may be found in \cite{Ur}.

\begin{figure}
\begin{center}
\begin{tabular}{c c c c c}
\begin{tikzpicture}[scale=0.3]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,0) (a) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,2) (b) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,4) (c) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,6) (d) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,3) (e) {};
\draw[dotted] (a) -- (b) -- (c) -- (d);
\draw (b) -- (e) -- (c);
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.3,-0.3) -- (-0.3,2.3) node [black,midway,xshift=-0.4cm]
{\footnotesize $m_1$};
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.3,2.3) -- (-0.3,3.7) node [black,midway,xshift=-0.4cm]
{\footnotesize $m_2$};
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.3,3.7) -- (-0.3,6.3) node [black,midway,xshift=-0.4cm]
{\footnotesize $m_3$};
\end{tikzpicture}
&\begin{tikzpicture}[scale=0.3]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,0) (a) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,2) (b) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,4) (c) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,6) (d) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,8) (e) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,10) (f) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,3) (g) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,7) (h) {};
\draw[dotted] (a) -- (b) -- (c) -- (d) -- (e) -- (f);
\draw (b) -- (g) -- (c);
\draw (d) -- (h) -- (e);
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.3,-0.3) -- (-0.3,2.3) node [black,midway,xshift=-0.4cm]
{\footnotesize $m_1$};
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.3,2.3) -- (-0.3,3.7) node [black,midway,xshift=-0.4cm]
{\footnotesize $m_2$};
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.3,3.7) -- (-0.3,6.3) node [black,midway,xshift=-0.4cm]
{\footnotesize $m_3$};
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.3,6.3) -- (-0.3,7.7) node [black,midway,xshift=-0.4cm]
{\footnotesize $m_4$};
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.3,7.7) -- (-0.3,10.3) node [black,midway,xshift=-0.4cm]
{\footnotesize $m_5$};
\end{tikzpicture}
&\begin{tikzpicture}[scale=0.3]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,0) (a) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,2) (b) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,4) (c) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,6) (d) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,8) (e) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,10) (f) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,5) (g) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (2,5) (h) {};
\draw[dotted] (a) -- (b) -- (c) -- (d) -- (e) -- (f);
\draw (c) -- (g) -- (d);
\draw (b) -- (h) -- (e);
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.3,-0.3) -- (-0.3,2.3) node [black,midway,xshift=-0.4cm]
{\footnotesize $m_1$};
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.3,2.3) -- (-0.3,4.3) node [black,midway,xshift=-0.4cm]
{\footnotesize $m_2$};
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.3,4.3) -- (-0.3,5.7) node [black,midway,xshift=-0.4cm]
{\footnotesize $m_3$};
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.3,5.7) -- (-0.3,7.7) node [black,midway,xshift=-0.4cm]
{\footnotesize $m_4$};
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.3,7.7) -- (-0.3,10.3) node [black,midway,xshift=-0.4cm]
{\footnotesize $m_5$};
\end{tikzpicture}
&\begin{tikzpicture}[scale=0.3]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,0) (a) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,2) (b) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,4) (c) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,6) (d) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,8) (e) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,10) (f) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,4) (g) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,6) (h) {};
\draw[dotted] (a) -- (b) -- (c) -- (d) -- (e) -- (f);
\draw (b) -- (g) -- (d);
\draw (c) -- (h) -- (e);
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.3,-0.3) -- (-0.3,2.3) node [black,midway,xshift=-0.4cm]
{\footnotesize $m_1$};
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.3,2.3) -- (-0.3,4.3) node [black,midway,xshift=-0.4cm]
{\footnotesize $m_2$};
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.3,4.3) -- (-0.3,5.7) node [black,midway,xshift=-0.4cm]
{\footnotesize $m_3$};
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.3,5.7) -- (-0.3,7.7) node [black,midway,xshift=-0.4cm]
{\footnotesize $m_4$};
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.3,7.7) -- (-0.3,10.3) node [black,midway,xshift=-0.4cm]
{\footnotesize $m_5$};
\end{tikzpicture}
&\begin{tikzpicture}[scale=0.3]
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,0) (a) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,2) (b) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,4) (c) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,6) (d) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,8) (e) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (0,10) (f) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,4) (g) {};
\node[draw, circle, inner sep=0pt, minimum size=5pt] at (1,6) (h) {};
\draw[dotted] (a) -- (b) -- (c) -- (d) -- (e) -- (f);
\draw (b) -- (g) -- (d);
\draw (c) -- (h) -- (e);
\draw (g) -- (h);
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.3,-0.3) -- (-0.3,2.3) node [black,midway,xshift=-0.4cm]
{\footnotesize $m_1$};
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.3,2.3) -- (-0.3,4.3) node [black,midway,xshift=-0.4cm]
{\footnotesize $m_2$};
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.3,4.3) -- (-0.3,5.7) node [black,midway,xshift=-0.4cm]
{\footnotesize $m_3$};
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.3,5.7) -- (-0.3,7.7) node [black,midway,xshift=-0.4cm]
{\footnotesize $m_4$};
\draw [decorate,decoration={brace,amplitude=5pt}]
(-0.3,7.7) -- (-0.3,10.3) node [black,midway,xshift=-0.4cm]
{\footnotesize $m_5$};
\end{tikzpicture}
\\(a) $Tri$
&(b) $Dtri$
&(c) $Ntri$
&(d) $Xdis$
&(e) $Xcon$
\end{tabular}
\end{center}
\caption{The five families of posets of height $n-1$ and $n-2$. \label{fig:h2}}
\end{figure}
\begin{table}
\centering%
\begin{tabular}{c|c|c}
Family&$e(P)$&$F_P(2)$\\
$Tri$&$m_2+1$&$|P|+m_2+1$\\
$Dtri$&$(m_2+1)(m_4+1)$&$|P|+m_2+m_4+1$\\
$Ntri$&$(m_2+m_3+m_4+2)(m_3+1)$&$|P|+m_2+3m_3+m_4+2$\\
$Xdis$&$(m_2+m_3+1)(m_3+m_4+1)+m_3+1$&$|P|+m_2+3m_3+m_4+2$\\
$Xcon$&$(m_2+m_3+1)(m_3+m_4+1)-\frac{1}{2}m_3(m_3+1)$&$|P|+m_2+2m_3+m_4+1$
\end{tabular}
\caption{Values of $e(P)$ and $F_P(2)$ for the five infinite families in Figure 1.}
\label{tab:dio}
\end{table}

\acknowledgements{We would like to thank Dr. Hamaker, whose suggestions and guidance were invaluable to our research, and Professor Billey, who initially proposed the problem to Dr. Hamaker. In addition, we would like to thank Sean Griffin for his insightful comments and edits along the way, and Professor Stanley for his guidance later in the process. Finally, we would like to thank Professor Morrow for bringing the authors together.}

\printbibliography
\end{document}
