The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (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)
 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 Table of n, a(n) for n=0..6. 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. FORMULA Limit_{n->oo} a(n)/2^(n^2) = 1. EXAMPLE a(2) = 13 because all 16 binary relations on  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 Cf. A006905, A121337. Sequence in context: A134485 A236551 A304727 * A075620 A336188 A348015 Adjacent sequences: A355727 A355728 A355729 * A355731 A355732 A355733 KEYWORD nonn,more,changed AUTHOR Geoffrey Critzer, Jul 15 2022 EXTENSIONS a(5)-a(6) from Pontus von Brömssen, Jul 19 2022 STATUS approved

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.

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