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

1, 2, 13, 333, 34924, 15339497, 28399641433

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 [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

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