\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}
\DeclareMathOperator{\lcm}{lcm}
\newcommand\la{\langle}
\newcommand\ra{\rangle}
\newcommand\df{\emph}
\newcommand\ls{\leqslant}
\newcommand\nls{\nleqslant}
\newcommand\pos{\mathbf}
\newcommand\dg{\cellcolor{gray}}
\newcommand\g{\cellcolor{lightgray}}
\newcommand\tb[1][0.3cm]{\hspace*{#1}}
\newcommand\tab[1][0.7cm]{\hspace*{#1}}
\newcommand\taab[1][1.5cm]{\hspace*{#1}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{algorithm}[theorem]{Algorithm}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
An Exact Enumeration of the \\
\vskip .1in
Unlabeled Disconnected Posets
}
\vskip 1cm
\large
Salah Uddin Mohammad, Md.\ Shah Noor, and Md.\ Rashed Talukder\\
Department of Mathematics\\
Shahjalal University of Science and Technology\\
Sylhet-3114 \\
Bangladesh\\
\href{mailto:salahuddin-mat@sust.edu}{\tt salahuddin-mat@sust.edu}\\
\href{mailto:msnoor-mat@sust.edu}{\tt msnoor-mat@sust.edu}\\
\href{mailto:r.talukder-mat@sust.edu}{\tt r.talukder-mat@sust.edu}
\end{center}
\vskip .2 in
\begin{abstract}
We give an exact enumeration of the unlabeled disconnected posets
according to the number of connected components of the posets. This
result establishes that the enumeration of unlabeled posets belonging
to a class that is closed under the direct sum depends mainly on the
enumeration of unlabeled connected posets contained in the class. We also
give an algorithm to determine the parameters involved in the enumeration
formula, and finally, find the number of unlabeled disconnected posets
with a certain number of elements. We show that the enumeration algorithm
runs in polynomial time.
\end{abstract}
\section{Introduction}
We give an exact enumeration of the unlabeled disconnected posets belonging to a class of posets that is closed under the direct sum of posets. Let $\mathcal{P}_n$, $n\geq 1$ be the set of all $n$-element unlabeled posets. Also let $\mathcal{Q}_n$, $n\geq 1$ and $\mathcal{R}_n$, $n\geq 2$ be the sets of all $n$-element unlabeled connected and disconnected posets, respectively. Since the singleton poset is connected, we have $\mathcal{P}_1$ = $\mathcal{Q}_1$ and $|\mathcal{P}_1|$ = $|\mathcal{Q}_1|$ = 1. In general, for all $n\geq 2$, we have $\mathcal{P}_n$ = $\mathcal{Q}_n\cup\mathcal{R}_n$ and hence $|\mathcal{P}_n|$ = $|\mathcal{Q}_n|+|\mathcal{R}_n|$. We observe that every member of $\mathcal{R}_{n}$ can be expressed as the direct sum of two or more members from $\mathcal{Q}_{r}$, $1\leq r\leq n-1$. In our enumeration method, for finite $n\geq 2$, we express $|\mathcal{R}_{n}|$ as a finite series consisting of the numbers $|\mathcal{Q}_{r}|$, $r\leq n-1$ that gives the enumeration of the posets belonging to $\mathcal{R}_{n}$ according to the number of connected direct terms (components) of the posets. Here, we establish in general the criterion for the pairwise nonisomorphic direct sum of unlabeled posets obtained by Mohammad~\cite{Mohammad-2022} and used particularly for the enumeration of the class of $P$-series, a subclass of the class of series-parallel posets.
For common enumeration methods, we refer the readers to~\cite{Brinkmann-Mckay-2002,Chaunier-Lygeros-1992,Heitzig-Reinhold-2000,Khamis-2006} for the enumeration of finite posets,~\cite{Bayoumi-Zahar-Khamis-1997,Bodirsky-Gimenez-Kang-Noy-2007} for graphs, and~\cite{Erne-1981,Koda-1994} for topologies. In the most of these cases, the enumeration of a class of structures was done by generating and counting all the pairwise nonisomorphic structures belonging to the class. The running time of these algorithms increases rapidly even though the structures under consideration are significantly small in size. Mainly, the running time for generating pairwise nonisomorphic structures make these algorithms highly time-complex. We observe that the steps for generating pairwise nonisomorphic disconnected posets in an enumeration process can be skipped. Therefore, the proposed exact enumeration method for the unlabeled disconnected posets must reduce the time-complexities of the algorithms for enumeration of unlabeled posets. Further, this enumeration method is applicable for the enumeration and generation of any unlabeled mathematical structures (posets, graphs, networks, topologies, and so on) belonging to a class that is closed under the direct sum of the structures.
We also give an algorithm to determine the parameters involved in the enumeration formula and to compute the numbers $|\mathcal{R}_{n}|$ for $n\geq 2$. We show that the enumeration algorithm runs in polynomial time with complexity $\mathcal{O}(n^{5})$. We implement the enumeration algorithm into the computer and gather some numerical results. Brinkmann and McKay~\cite{Brinkmann-Mckay-2002} obtained the number of unlabeled posets up to $16$ elements, the sequence~\seqnum{A000112} in OEIS~\cite{Sloane-Plouffe-2022}. By using the number of unlabeled connected posets up to $16$ elements, we determine the number of unlabeled disconnected posets up to $17$ elements according to the number of connected direct terms of the posets, the sequences~\seqnum{A349401} and~\seqnum{A263864} in OEIS~\cite{Sloane-Plouffe-2022}. Khamis~\cite{Khamis-2004} obtained the number of unlabeled $N$-free posets up to $14$ elements according to the height of the posets, the sequence~\seqnum{A202182} in OEIS~\cite{Sloane-Plouffe-2022}. By using the number of unlabeled connected $N$-free posets up to $14$ elements, we determine the number of unlabeled disconnected $N$-free posets up to $15$ elements according to the number of connected direct terms of the posets, the sequences~\seqnum{A349367} and~\seqnum{A350783} in OEIS~\cite{Sloane-Plouffe-2022}.
In Section~\ref{Preliminaries}, we recall some basic terminologies related to the posets and their direct sum. In Section~\ref{NonisomorphicSums}, we give the criterion for pairwise nonisomorphic direct sums of connected posets. In Section~\ref{EnumerationFormulas}, we establish the formulae giving the enumeration of disconnected posets. In Section~\ref{EnumerationAlgorithm}, we give the enumeration algorithm and prove its time-complexity. In Section~\ref{append}, we include the numerical results obtained by implementing the enumeration algorithm into the computer.
\section{Preliminaries}
\label{Preliminaries}
A \df{poset} (\df{partially ordered set}) is a structure $\pos{A}=\la A,\ls \ra$ consisting of the nonempty set $A$ with the order relation $\ls$ on $A$. A poset $\pos{A}$ is called \df{finite} if the underlying set $A$ is finite. Here, we assume that every poset is finite. Let $\pos{A}=\la A,\ls_A\ra$ and $\pos{B}=\la B,\ls_B\ra$ be any posets. A bijective map $\phi: A\rightarrow B$ is called an \df{order isomorphism} if for all $x,y\in A$, $x\ls_A y$ if and only if $\phi(x)\ls_B \phi(y)$. We write $\pos{A}\cong \pos{B}$ whenever $\pos{A}$ and $\pos{B}$ are order isomorphic. By saying that a collection of posets is isomorphic (analogously, nonisomorphic), we mean that the posets in the collection are \df{pairwise} isomorphic (nonisomorphic). For further details on posets, we refer the readers to the classical book by Davey and Priestley~\cite{Davey-Priestley-2002}.
We use the notation $\textbf{1}$ for the singleton poset, $\pos{C}_n$ ($n\geq 1$) for the $n$-element chain poset, $\pos{I}_n$ ($n\geq 1$) for the $n$-element antichain poset, $\pos{B}_{m,n}$ ($m\geq 1, n\geq 1$) for the complete bipartite poset with $m$ minimal elements and $n$ maximal elements. We write $\pos{A}+\pos{B}$ to denote the direct sum of $\pos{A}$ and $\pos{B}$. Here, $\pos{A}$ and $\pos{B}$ are called the \df{direct terms} (\df{components}) of the poset $\pos{A}+\pos{B}$. We write briefly $\sum_{i=1}^{r}\pos{A}_i$ for the direct sum $\pos{A}_1+\pos{A}_2+\cdots+\pos{A}_r$ and $r\pos{A}$ for the direct sum $\pos{A}$+$\pos{A}$+$\cdots$+$\pos{A}$ of $r$ posets $\pos{A}$. For example, $\pos{I_n}\cong n\pos{1}$. A poset having two or more direct terms is called \df{disconnected}, otherwise, it is called \df{connected}. Note that, for all posets $\pos{A}_{i}, \pos{B}_{i}$, $1\leq i\leq r$, since the direct sum of posets is commutative, we have $\sum_{i=1}^{r}\pos{A}_i$ $\cong$ $\sum_{i=1}^{r}\pos{B}_i$ if and only if $\pos{A}_{i}\cong\pos{B}_{i}$ for every $1\leq i\leq r$.
\section{Nonisomorphic direct sum criterion}
\label{NonisomorphicSums}
For unlabeled connected posets, in particular, we have $\mathcal{Q}_1=\{\pos{1}\}$, $\mathcal{Q}_2=\{\pos{C}_2\}$, and $\mathcal{Q}_3=\{\pos{B}_{1,2}$, $\pos{B}_{2,1}$, $\pos{C}_3\}$. For unlabeled disconnected posets, we have $\mathcal{R}_2=\{2\pos{1}\}$, $\mathcal{R}_3=\{1+\pos{C}_2$, $3\pos{1}\}$, and $\mathcal{R}_4=\{1+\pos{C}_3$, $1+\pos{B}_{1,2}$, $1+\pos{B}_{2,1}$, $\pos{C}_2+\pos{C}_2$, $2\pos{1}+\pos{C}_2$, $4\pos{1}\}$. We observe that, for every $2\leq n\leq 4$, every member of $\mathcal{R}_n$ can be expressed as the direct sum of some members of $\mathcal{Q}_r$, $1\leq r\leq 3$. In general, for $\pos{R}_n\in\mathcal{R}_n$, $n\geq 2$, there exist $\pos{Q}_{n_i}\in\mathcal{Q}_{n_i}$, $1\leq i\leq m$ such that
\begin{equation}
\label{equation-direct-sum-express}
\pos{R}_n\cong\pos{Q}_{n_1}+\pos{Q}_{n_2}+\cdots+\pos{Q}_{n_m}=\sum_{i=1}^{m}\pos{Q}_{n_i},
\end{equation}
where $2\leq m\leq n$ and $n=\sum_{i=1}^{m}n_i$. Here, $m$ is the number of connected direct terms of $\pos{R}_n$. Since the direct sum of posets is commutative, we observe the following.
\begin{enumerate}
\item For $n=2$, we have $\pos{R}_2\cong\pos{Q}_1+\pos{Q}_1$. Thus an $\pos{R}_2$ can be obtained only in one way with 2 connected direct terms.
\item For $n=3$, we have $\pos{R}_3\cong\pos{Q}_1+\pos{Q}_2\cong\pos{Q}_2+\pos{Q}_1$ and $\pos{R}_3\cong\pos{Q}_1+\pos{Q}_1+\pos{Q}_1$. Thus, an $\pos{R}_3$ can be obtained in one way with 2 connected direct terms and in one way with 3 direct terms.
\item For $n=4$, all the ways in which an $\pos{R}_4$ can be obtained are given in Table~\ref{table-direct-sum-posets-n4}. Here, we see that an $\pos{R}_4$ can be obtained in two ways with 2 connected direct terms, in one way with 3 connected direct terms, and in one way with 4 connected direct terms.
\end{enumerate}
\begin{table}[ht]
\centering
\begin{tabular}{| c | r |}
\hline
Number of &Ways in which an\\
connected direct terms &$\pos{R}_4$ can be obtained\\
\hline\hline
2 &$\pos{Q}_2+\pos{Q}_2$\\
&and $\pos{Q}_1+\pos{Q}_3\cong\pos{Q}_3+\pos{Q}_1$\\
\hline
3 &$\pos{Q}_1+\pos{Q}_1+\pos{Q}_2\cong\pos{Q}_1+\pos{Q}_2+\pos{Q}_1$\\
&$\cong\pos{Q}_2+\pos{Q}_1+\pos{Q}_1$\\
\hline
4 &$\pos{Q}_1+\pos{Q}_1+\pos{Q}_1+\pos{Q}_1$\\
\hline
\end{tabular}
\caption{All the ways in which an $\pos{R}_4$ can be obtained as a direct sum of $\pos{Q}_r$, $r\leq 3$.}
\label{table-direct-sum-posets-n4}
\end{table}
We see that if the posets $\pos{R}_n\in\mathcal{R}_n$ are obtained as above, some of the posets in $\mathcal{R}_n$ can be isomorphic even though the collection of direct terms $\pos{Q}_{n_i}$, $1\leq i\leq m$ is nonisomorphic. In this section, we establish the criterion for the direct sum so that all the posets in $\mathcal{R}_n$ obtained as the direct sum of the posets $\pos{Q}_{n_i}$, $1\leq i\leq m$ are nonisomorphic. Here, for every $1\leq r\leq n-1$, we must assume that the collection $\mathcal{Q}_r$ is nonisomorphic. To make our intuition more precise, we observe the connected direct terms of the posets $\pos{R}_6\in\mathcal{R}_6$. We see that an $\pos{R}_6$ can be obtained in all the ways given in Table~\ref{table-direct-sum-posets-n6}.
\begin{table}[ht]
\centering
\begin{tabular}{| c | r |}
\hline
Number of& Ways in which an\\
connected direct terms& $\pos{R}_6$ can be obtained\\
\hline\hline
2 &$\pos{Q}_1+\pos{Q}_5$, $\pos{Q}_2+\pos{Q}_4$,\\
&and $\pos{Q}_3+\pos{Q}_3$\\
\hline
3 &$\pos{Q}_1+\pos{Q}_1+\pos{Q}_4$,\\
&$\pos{Q}_1+\pos{Q}_2+\pos{Q}_3$,\\
&and $\pos{Q}_2+\pos{Q}_2+\pos{Q}_2$\\
\hline
4 &$\pos{Q}_1+\pos{Q}_1+\pos{Q}_1+\pos{Q}_3$\\
&and $\pos{Q}_1+\pos{Q}_1+\pos{Q}_2+\pos{Q}_2$\\
\hline
5 &$\pos{Q}_1+\pos{Q}_1+\pos{Q}_1+\pos{Q}_1+\pos{Q}_2$\\
\hline
6 &$\pos{Q}_1+\pos{Q}_1+\pos{Q}_1+\pos{Q}_1+\pos{Q}_1+\pos{Q}_1$\\
\hline
\end{tabular}
\caption{All the ways in which an $\pos{R}_6$ can be obtained as a direct sum of $\pos{Q}_r$, $r\leq 5$.}
\label{table-direct-sum-posets-n6}
\end{table}
Here, in Table~\ref{table-direct-sum-posets-n6}, we see that all the other direct sums in which an $\pos{R}_6$ can be obtained are isomorphic to one of the direct sums given in the table. This observation shows that all the direct sums in which a poset $\pos{R}_n$ can be obtained will be nonisomorphic if the sequence $\la n_1$, $n_2$, $\hdots$, $n_m\ra$, as in the equation~(\ref{equation-direct-sum-express}), is nondecreasing, that is, $n_1\leq n_2\leq \cdots \leq n_m$. We prove this conjecture in the following. Recall the assumption that, for every $1\leq r\leq n-1$, the collection $\mathcal{Q}_{r}$ is nonisomorphic.
\begin{theorem}
\label{theo-enum-disconn-posets}
For all $\pos{R}_n\in\mathcal{R}_{n}$, let $\pos{R}_n=\sum_{i=1}^{m}\pos{Q}_{n_i}$, where $n=\sum_{i=1}^{m}n_i$ for some $2\leq m\leq n$, such that the sequences $\la n_1$, $n_2$, $\hdots$, $n_{m}\ra$ are all nondecreasing and distinct. Then for every pair of posets $\pos{R}_n, \pos{R'}_n\in\mathcal{R}_{n}$, we have $\pos{R}_n\ncong\pos{R'}_n$.
\end{theorem}
\begin{proof}
For $\pos{R}_n,\pos{R'}_n\in\mathcal{R}_{n}$, let $\pos{R}_n\cong\sum_{i=1}^{m}\pos{Q}_{n_i}$ and $\pos{R'}_n\cong\sum_{i=1}^{m'}\pos{Q}_{r_i}$, as in the hypothesis, such that $L=\la n_1$, $n_2$, $\hdots$, $n_m\ra$ $\neq$ $\la r_1$, $r_2$, $\hdots$, $r_{m'}\ra=L'$. If $m\neq m'$ then $\pos{R}_n$ and $\pos{R'}_n$ have different numbers of connected direct terms and, clearly, $\pos{R}_n\ncong\pos{R'}_n$. Otherwise, let $m = m'$. In this case, since both $L$ and $L'$ contain nondecreasing lengths, there exist $1\leq s,t\leq m$, such that $n_i\neq r_i$ when $s\leq i\leq t$ and $n_i$ = $r_i$ otherwise (in the simplest case, for example, consider the sequences $\la 1$, $2$, $3$, $4$, $5\ra$ and $\la 1$, $2$, $2$, $5$, $5\ra$ where $s=3$ and $t=4$). Also, $r_i1$); and $n_t