Asymptotic enumeration of N-free partial orders (Q913831): Difference between revisions

It is well-known that N-free posets P are nice posets with respect to a great variety of ``problems'' in poset theory, although they are not as nice as the series-parallel posets (obtainable from a singleton by sum and ordinal sum operations) of which they form a superset. From the viewpoint of enumeration, density results or other probabilistic looks at posets it is useful to be able to provide accurate actual or asymptotic estimates of various quantities involved. In this paper the authors show that the number of unlabeled N-free posets with n elements is \(N(n)=2 \exp (2n \log n+O(n \log n))\). An interesting intermediate step in this computation is the determination of the generating function \(J(x)=\sum j(n)x^ n\) of N-free interval orders in which no two distinct elements have the same lower covers and the same upper covers, these being obtained from a particular block decomposition of the covering graph of a poset. The number j(n) is determined to be \(\sum^{n+1}_{k=2}\left( \begin{matrix} (k-1)(k-2)/2\\ n-k+1\end{matrix} \right)\). Using other counts already available or developed by the authors, a table counting various classes of posets up to \(n=12\) is also provided.