Asymptotic enumeration of partial orders on a finite set

Kleitman, D. J.; Rothschild, B. L.

doi:10.1090/S0002-9947-1975-0369090-9

Asymptotic enumeration of partial orders on a finite set
HTML articles powered by AMS MathViewer

by D. J. Kleitman and B. L. Rothschild PDF

Trans. Amer. Math. Soc. 205 (1975), 205-220 Request permission

Abstract:

By considering special cases, the number ${P_n}$ of partially ordered sets on a set of $n$ elements is shown to be $(1 + O(1/n)){Q_n}$, where ${Q_n}$ is the number of partially ordered sets in one of the special classes. The number ${Q_n}$ can be estimated, and we ultimately obtain \[ {P_n} = \left ( {1 + O\left ( {\frac {1}{n}} \right )} \right )\left ( {\sum \limits _{i = 1}^n {\sum \limits _{j = 1}^{n - i} {\left ( {_i^n} \right )\left ( {_j^{n - i}} \right ){{\left ( {{2^i} - 1} \right )}^j}{{\left ( {{2^j} - 1} \right )}^{n - i - j}}} } } \right ).\]

References

The number of finite partially ordered sets

18

The number of topologies on $n$ points

Louis Comtet, Recouvrements, bases de filtre et topologies d’un ensemble fini, C. R. Acad. Sci. Paris Sér. A-B 262 (1966), A1091–A1094 (French). MR 201325

On the computer enumeration of finite topologies

10

David A. Klarner, The number of graded partially ordered sets, J. Combinatorial Theory 6 (1969), 12–19. MR 236035
David A. Klarner, The number of classes of isomorphic graded partially ordered sets, J. Combinatorial Theory 9 (1970), 412–419. MR 268090
D. Kleitman and B. Rothschild, The number of finite topologies, Proc. Amer. Math. Soc. 25 (1970), 276–282. MR 253944, DOI 10.1090/S0002-9939-1970-0253944-9
V. Krishnamurthy, On the number of topologies on a finite set, Amer. Math. Monthly 73 (1966), 154–157. MR 201324, DOI 10.2307/2313548
A. Shafaat, On the number of topologies definable for a finite set, J. Austral. Math. Soc. 8 (1968), 194–198. MR 0225670