A121337 Number of idempotent relations on n labeled elements.

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

Offset

0,2

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)

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

Table of n, a(n) for n=0..6.

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.

Example

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

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

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.

Sequence in context: A247736 A155928 A001946 * A269069 A361036 A224366

Adjacent sequences: A121334 A121335 A121336 * A121338 A121339 A121340

Keyword

nonn,hard,more

Author

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

Extensions

Offset corrected by James Mitchell, Jul 28 2013

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

Status

approved