A355730 -id:A355730 - cp's OEIS frontend

A365985 Triangular array read by rows: T(n,k) is the number of binary relations on [n] that are dense (A355730) and have exactly k strongly connected components, n>=0, 0<=k<=n.

1, 0, 2, 0, 3, 10, 0, 85, 114, 134, 0, 13317, 10029, 6972, 4606, 0, 8300125, 4026580, 1756610, 866300, 389882, 0, 19743155103, 6020248905, 1736497215, 589363590, 231745290, 78631330

Offset: 0

Geoffrey Critzer, Sep 24 2023

			Triangle begins ...
  1;
  0,     2;
  0,     3,    10;
  0,    85,   114,  134;
  0, 13317, 10029, 6972, 4606;
  ...

Wikipedia, Dense order.

Cf. A355730 (row sums).

Row n = 5 from Pontus von Brömssen, Sep 24 2023

Row n = 6 from Pontus von Brömssen, Sep 25 2023

A121337 Number of idempotent relations on n labeled elements.

Original entry on oeis.org

1, 2, 11, 123, 2360, 73023, 3465357

Offset: 0

Florian Kammüller (flokam(AT)cs.tu-berlin.de), Aug 28 2006

A relation r is idempotent if r ; r = r, where ; denotes sequential composition.
From Geoffrey Critzer, Oct 18 2023 : (Start)
a(n) is also the number of maximal subgroups in the semigroup of binary relations on [n].  See Butler and Markowski link.
A binary relation is idempotent iff it is both dense (A355730) and transitive (A006905).
A binary relation is idempotent iff it is both limit dominating (A366194) and limit dominated (A366722).  See Gregory, Kirkland, and Pullman link.
A binary relation R on [n] is idempotent iff the following biconditional statement holds for all x,y in [n]:  There is a cyclic traverse from x to y in G(R) iff (x,y) is in R.  Here, G(R) is the directed graph with self loops allowed (A002416) corresponding to R.  See Rosenblatt link.
Let Q be a quasi-order (A000798) on [n].  Let D(X) be the relation {(x,x):x is in X}.  Let S be a subset of [n] such that: (i) For all x in S, the class in the equivalence relation Q intersect Q^(-1) containing (x,x) is a singleton and (ii) for all x,y in S, the component containing x is not covered by the component containing y in the condensation of G(Q) .  Here, the condensation of G(Q) is the acyclic digraph (A003024) obtained from G(Q) 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.  Then a relation is idempotent iff it is of the form Q-D(S).  See Schein link.  (End)

			a(2) = 11 because given a set {a,b} of two elements, of the 2^(2*2) = 16 relations on the set, only 5 are not idempotent. - _Michael Somos_, Jul 28 2013
These 5 relations that are not idempotent are: {(a,b)}, {(b,a)}, {(a,b),(b,a)}, {(a,b),(b,a),(b,b)}, {(a,a),(a,b),(b,a)}. - _Geoffrey Critzer_, Aug 07 2016

F. Kammüller, Interactive Theorem Proving in Software Engineering, Habilitationsschrift, Technische Universitaet Berlin (2006).
Ki Hang Kim, Boolean Matrix Theory and Applications, Marcel Decker, 1982.

G. Brinkmann and B. D. McKay, Counting unlabeled topologies and transitive relations, J. Integer Sequences, Volume 8, 2005.
K. K.-H. Butler and G. Markowsky, The Number of Maximal Subgroups of the Semigroup of Binary Relations, Kyungpook Math. J. Vol 12, June 1972.
D. A. Gregory, S. Kirkland, and N. J. Pullman, Power convergent Boolean matrices, Linear Algebra and its Applications, Volume 179, 15 January 1993, Pages 105-117.
F. Kammüller, Counting idempotent relations.
F. Kammüller and J. W. Sanders, Idempotent relations in Isabelle/HOL, International Colloquium on Theoretical Aspects of Computing, ICTAC'04. Volume 3407 of Lecture Notes in Computer Science, Springer-Verlag (2005).
G. Pfeiffer, Counting transitive relations, J. Integer Sequences, Volume 7, 2004, #3.
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.

Cf. A000798 (labeled quasi-orders (or topologies)), A001930 (unlabeled quasi-orders), A001035 (labeled partial orders), A000112 (unlabeled partial orders), A002416, A003024, A366722, A366194, A355730, A006905.

Row sums of A360984.

Prepend[Table[Length[Select[Tuples[Tuples[{0, 1}, n], n], (MatrixPower[#, 2] /. x_ /; x > 0 -> 1) == # &]], {n, 1, 4}], 1] (* Geoffrey Critzer, Aug 07 2016 *)

Offset corrected by James Mitchell, Jul 28 2013

a(1) corrected by Philippe Beaudoin, Aug 11 2015

A366194 Number of limit dominating binary relations on [n].

Original entry on oeis.org

1, 2, 13, 177, 4486

Offset: 0

Geoffrey Critzer, Oct 03 2023

A relation R is limit dominating iff R converges to a single limit L (A365534) and R contains L.  See Gregory, Kirkland, and Pullman.
A convergent relation R is limit dominating iff the following implication holds for all x,y in [n].  If there is a cyclic traverse from x to y in G(R) then (x,y) is in R, where G(R) is the directed graph with loops associated to R.
A relation R is limit dominating iff it converges to L, the biggest dense relation (A355730) contained in R.  In which case L is the intersection of R^i for all i>=1. - Geoffrey Critzer, Dec 03 2023

			Every idempotent relation (A121337) is limit dominating.
Every transitive relation (A006905) is limit dominating.
Every nilpotent relation (A003024) is limit dominating.

D. A. Gregory, S. Kirkland, and N. J. Pullman, Power convergent Boolean matrices, Linear Algebra and its Applications, Volume 179, 15 January 1993, Pages 105-117.
D. Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research of the National Bureau of Standards, 67B No. 4, 1963.

Cf. A365534, A121337, A006905, A003024, A366722.

A366722 Number of limit dominated binary relations on [n].

Original entry on oeis.org

1, 2, 13, 399, 55894

Offset: 0

Geoffrey Critzer, Oct 17 2023

A relation R is limit dominated iff R converges to a single limit L (A365534) and R is contained in L.
A convergent relation R is limit dominated iff the following implication holds for all x,y in [n].  If (x,y) is in R then there is a cyclic traverse from x to y in G(R), where G(R) is the directed graph with loops associated to R.
A relation R is limit dominated iff it converges to L, the smallest transitive relation (A006905) containing R. In which case, L is the union of R^i for all i >= 1. - Geoffrey Critzer, Dec 03 2023

			Every idempotent relation (A121337) is limit dominated.
Every dense relation (A355730) is limit dominated.
Every primitive relation (A070322) is limit dominated.

D. A. Gregory, S. Kirkland, and N. J. Pullman, Power convergent Boolean matrices, Linear Algebra and its Applications, Volume 179, 15 January 1993, pp. 105-117.
D. Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research of the National Bureau of Standards, 67B No. 4, 1963.

Cf. A365534, A121337, A006905, A366194, A355730, A070322.

cp's OEIS Frontend

A365985 Triangular array read by rows: T(n,k) is the number of binary relations on [n] that are dense (A355730) and have exactly k strongly connected components, n>=0, 0<=k<=n.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A121337 Number of idempotent relations on n labeled elements.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

A366194 Number of limit dominating binary relations on [n].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A366722 Number of limit dominated binary relations on [n].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs