The OEIS is supported by the many generous donors to the OEIS Foundation.


(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A355730 Number of binary relations R on [n] such that R is contained in R^2. 0
1, 2, 13, 333, 34924, 15339497, 28399641433 (list; graph; refs; listen; history; text; internal format)
Equivalently, a(n) is the number of binary relations R on [n] such that for all x,y in [n], if (x,y) is in R then there is a z in [n] such that (x,z) and (z,y) are both in R. A relation having this property is sometimes called a dense relation. Almost all relations are dense. A relation is idempotent if and only if it is both transitive and dense. A transitive relation is dense (hence idempotent) if and only if there does not exist a pair of irreflexive points x,y in [n] such that x covers y. Cf. Schein reference.
If R is contained in R^2 then the maximal cyclic nets in R are universal so that R is convergent, i.e., the period of R is equal to 1. Cf. Rosenblatt reference. Moreover, R converges to its transitive closure so that the index of R is at most n. - Geoffrey Critzer, Sep 05 2023
G. Markowsky, Bounds on the index and period of a binary relation on a finite set, Semigroup Forum, Vol 13 (1977), 253-259.
D. Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research of the National Bureau of Standards, 67B No. 4, 1963.
B. M. Schein, A construction for idempotent binary relations, Proc. Japan Acad., Vol. 46, No. 3 (1970), pp. 246-247.
Wikipedia, Dense order.
Limit_{n->oo} a(n)/2^(n^2) = 1.
a(2) = 13 because all 16 binary relations on [2] are dense except for {{0,1},{0,0}}, {{0,0},{1,0}}, {{0,1},{1,0}}.
Table[B = Tuples[Tuples[{0, 1}, nn], nn]; subsetQ[matrix1_, matrix2_] :=
Apply[And, Map[! MemberQ[#, 1] &, matrix1 - matrix2]]; Select[B, subsetQ[#, Clip[#.#]] &] // Length, {nn, 0, 4}]
Sequence in context: A134485 A236551 A304727 * A075620 A336188 A348015
Geoffrey Critzer, Jul 15 2022
a(5)-a(6) from Pontus von Brömssen, Jul 19 2022

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 4 17:22 EDT 2023. Contains 365887 sequences. (Running on oeis4.)