ArticleOpen Access http://dx.doi.org/10.26855/jamc.2021.12.002
Counting Transitive Relations with Two Ordered Pairs
Firdous Ahmad Mala
Department of Higher Education, Govt. Degree College Sopore, Baramulla, Jammu and Kashmir, India.
*Corresponding author: Firdous Ahmad Mala
Published: October 13,2021
Abstract
Enumerating transitive relations on a set seems very difficult. There is no known formula that counts the number of transitive relations on a set with n elements. However, OEIS, which is an online repository of more than 350,000 integer sequences, provides the number of transitive relations for all sets with fewer than nineteen elements. The problem is also closely related to some other open problems in Combinatorics including the enumeration of partial orders, quasiorders and topologies on a finite set. In this paper, we visualize the distribution of transitive relations with two ordered as a matrix. Consequently, an explicit biquadratic formula is obtained for the number of transitive relations with two ordered pairs. It is also shown that for sufficiently large sets, relations with two ordered pairs that are not transitive are extremely rare. The technique provided herein could conveniently be generalized to the enumeration of transitive relations with three or more ordered pairs.
Keywords
Transitive relations, Enumeration
References
[1] Pfeiffer, Götz. (2004). Counting transitive relations. Journal of Integer Sequences, (2004) https://cs.uwaterloo.ca/ journals/JIS/VOL7/Pfeiffer/pfeiffer6.html.
[2] Mala, F. A. (2021). On the number of transitive relations on a set. Indian J Pure Appl Math, (2021). https://doi.org/10.1007/s13226-021-00100-0.
[3] OEIS, Sloane, Neil J. A. and The OEIS Foundation Inc. The on-line encyclopedia of integer sequences, A006905. https://oeis.org/A006905.
[4] Kizmaz, M. Y. (2019). On the number of topologies on a finite set. Algebra and Discrete Mathematics, 27(1), 50-57. http://mi.mathnet.ru/adm691.
How to cite this paper
Counting Transitive Relations with Two Ordered Pairs
How to cite this paper: Firdous Ahmad Mala. (2021) Counting Transitive Relations with Two Ordered Pairs. Journal of Applied Mathematics and Computation, 5(4), 247-251.
DOI: http://dx.doi.org/10.26855/jamc.2021.12.002