Article
Full entry |
PDF
(0.5 MB)
Feedback
PDF
(0.5 MB)
Feedback
Keywords:
enumeration; transitivity; partial order
enumeration; transitivity; partial order
Summary:
In this paper we find a one-to-one correspondence between transitive relations and partial orders. On the basis of this correspondence we deduce the recurrence formula for enumeration of their numbers. We also determine the number of all transitive relations on an arbitrary $n$-element set up to $n=14$.
References:
[1] Z. I. Borevich: Periodicity of residues of the numbeг of finite labeled $T_0$-topologies. Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. 114 (1982), 32-36. (In Russian.) MR 0669557
[2] Z. I. Borevich: A comparison for the number of finite labeled $T_0$-topologies. Mat. Issled. (1982), no. 65, 9-16. (In Russian.) MR 0669739
[3] M. Erné: Struktur- und Anzahlformeln für Topologien auf endlichen Mengen. Manuscripta Math. 11 (1974), 221-259. DOI 10.1007/BF01173716 | MR 0360300
[4] M. Erné аnd K. Stege: Counting finite posets and topologies. Order 8 (1991), no. 3, 247-265. DOI 10.1007/BF00383446 | MR 1154928
[5] J. W. Evаns F. Hаrаry аnd M. S. Lynn: On the computer enumeration of finite topologies. Coom. ACM 10 (1967), 295-298. DOI 10.1145/363282.363311
[6] K. H. Kim аnd F. W. Roush: Posets and finite topologies. Pure Appl. Math. Sci. 14 (1981), no. 1-2, 9-22. MR 0613626
[7] J. Klаškа: Partitions and partially ordered sets. Acta Math. Inform. Univ. Ostraviensis 3 (1995), 45-54. MR 1474065
[8] D. Kleitmаn аnd B. Rothschild: Asymptotic enumeration of partial orders on a finite set. Trans. Amer. Math. Soc. 205 (1975), 205-220. DOI 10.1090/S0002-9947-1975-0369090-9 | MR 0369090
[9] V. Novák аnd M. Novotný: Transitive ternary relations and quasiorderings. Arch. Math. (Brno) 25 (1989), no. 1-2, 5-12. MR 1189193
[10] V. Novák аnd M. Novotný: Binaгy and teгnary relations. Math. Bohem. 117 (1992), no. 3, 283-292.
Search
Partner of
