# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/
Search: id:a355730
Showing 1-1 of 1
%I A355730 #37 Oct 16 2023 23:38:17
%S A355730 1,2,13,333,34924,15339497,28399641433
%N A355730 Number of binary relations R on [n] such that R is contained in R^2.
%C A355730 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.
%C A355730 Almost all relations are dense.
%C A355730 A relation is idempotent if and only if it is both transitive and dense. A transitive relation R is dense (hence idempotent) if and only if there does not exist a pair (C_1,C_2) of edgeless components such that C_1 covers C_2 in the condensation of G(R). Here, G(R) is the directed graph (with self loops allowed) associated to R. The condensation of G(R) is the acyclic digraph obtained from G(R) by replacing every strongly connected component (SCC) by a single vertex and all directed edges from one SCC to another with a single directed edge. See Schein reference.
%C A355730 If R is contained in R^2 then the maximal cyclic nets in R are primitive (A070322) so that R is convergent, i.e., the period of R is equal to 1. Moreover, R converges to its transitive closure so that the index of R is at most n. See Rosenblatt reference. - _Geoffrey Critzer_, Sep 05 2023
%H A355730 G. Markowsky, Bounds on the index and period of a binary relation on a finite set, Semigroup Forum, Vol 13 (1977), 253-259.
%H A355730 D. Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research of the National Bureau of Standards, 67B No. 4, 1963.
%H A355730 B. M. Schein, A construction for idempotent binary relations, Proc. Japan Acad., Vol. 46, No. 3 (1970), pp. 246-247.
%H A355730 Wikipedia, Dense order.
%F A355730 Limit_{n->oo} a(n)/2^(n^2) = 1.
%e A355730 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}}.
%t A355730 Table[B = Tuples[Tuples[{0, 1}, nn], nn]; subsetQ[matrix1_, matrix2_] :=
%t A355730 Apply[And, Map[! MemberQ[#, 1] &, matrix1 - matrix2]];Select[B, subsetQ[#, Clip[#.#]] &] // Length, {nn, 0, 4}]
%Y A355730 Cf. A006905, A121337, A070322.
%K A355730 nonn,more
%O A355730 0,2
%A A355730 _Geoffrey Critzer_, Jul 15 2022
%E A355730 a(5)-a(6) from _Pontus von Brömssen_, Jul 19 2022
%E A355730 Comments clarified by _Geoffrey Critzer_, Oct 16 2023
# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE