The number of partially ordered sets with more points than incomparable pairs
Marcel Em · 1992
ErnC, M., The number of partially ordered sets with more points than incomparable pairs, Discrete Mathematics 105 (1992) 49-60. Let pkn denote the number of unlabeled posets with n points and k unrelated pairs. We show that for k <n, these numbers satisfy a recursion formula of the form pkn = &~~p~_~,~_,_,, where the coefficients cj can be computed if the numbers qjm of all ordinally indecomposable posets with m points and j unrelated pairs are known for m - 1 <j G k. The crucial lemma for the proof states that (lim = 0 for j cm - 1. From the recursion formula it follows that pkn is a polynomial of degree k in the variable n and that pa. 2 (” ; ‘) with asymptotic equality for fixed k. For small values of k, we determine these polynomials explicitly. At the other end of the scale, we find that 9n-,,n = 2”m3 for n 3 3. Similar results are obtained for the number of labeled posets with a fixed linear extension and a given number of unrelated pairs.