Hill Publishing Group | contact@hillpublisher.com

Hill Publishing Group

Location:Home / Journals / Journal of Applied Mathematics and Computation /

DOI:http://dx.doi.org/10.26855/jamc.2021.12.002

Counting Transitive Relations with Two Ordered Pairs

Date: October 13,2021 |Hits: 4091 Download PDF How to cite this paper

Firdous Ahmad Mala

Department of Higher Education, Govt. Degree College Sopore, Baramulla, Jammu and Kashmir, India.

*Corresponding author: Firdous Ahmad Mala

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.

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 Computation5(4), 247-251.

DOI: http://dx.doi.org/10.26855/jamc.2021.12.002

Free HPG Newsletters

Add your e-mail address to receive free newsletters from Hill Publishing Group.

Contact us

Hill Publishing Group

8825 53rd Ave

Elmhurst, NY 11373, USA

E-mail: contact@hillpublisher.com

Copyright © 2019 Hill Publishing Group Inc. All Rights Reserved.