A121337 Number of idempotent relations on n labeled elements.

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

Offset: 0

Author

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

Keywords

• nonn
• hard
• more

Comments

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)

Examples

			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
		

References

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

Links

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

Crossrefs

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.

Programs

Mathematica

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 *)

Extensions

Offset corrected by James Mitchell, Jul 28 2013

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