Exact Counting of Unlabeled Rigid Interval Posets Regarding or Disregarding Height

Abstract

In this paper, the author gives the exact counting of unlabeled rigid interval posets regarding or disregarding the height by using generating functions. The counting technique follows those introduced in El-Zahar (1989), Hanlon (Trans Amer Math Soc 272:383-426, 1982), Khamis (Discrete Math 275:165-175, 2004). The main advantage of the suggested technique is that a very simple recursive construction of unlabeled rigid interval poset from small ones leads to derive the given generating function for unlabeled rigid interval posets whose coefficients can be easily computed. Moreover, it is proven that the sets of n-element unlabeled rigid interval posets and upper triangular 0-1 matrices with n ones and no zero rows or columns are in one-to-one correspondence. In addition, n-element unlabeled interval posets are counted for n ≥ 1, using the given generating function for rigid ones. Upper and lower bounds for the number of n-element unlabeled rigid interval posets are given. Also, an asymptotic estimate for the required numbers is obtained. Numerical results for unlabeled interval posets coincide with those given in El-Zahar (1989) and Khamis (Discrete Math 275:165-175, 2004). The exact numbers of n-element unlabeled rigid and general interval posets with and without height k are included, for 1 ≤ k ≤ n ≤ 15. © 2011 Springer Science+Business Media B.V.