

A355730


Number of binary relations R on [n] such that R is contained in R^2.


0




OFFSET

0,2


COMMENTS

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


LINKS



FORMULA

Limit_{n>oo} a(n)/2^(n^2) = 1.


EXAMPLE

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}}.


MATHEMATICA

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}]


CROSSREFS



KEYWORD

nonn,more,changed


AUTHOR



EXTENSIONS



STATUS

approved



