|
%I #59 Oct 21 2023 06:14:29
%S 1,2,11,123,2360,73023,3465357
%N Number of idempotent relations on n labeled elements.
%C A relation r is idempotent if r ; r = r, where ; denotes sequential composition.
%C From _Geoffrey Critzer_, Oct 18 2023 : (Start)
%C a(n) is also the number of maximal subgroups in the semigroup of binary relations on [n]. See Butler and Markowski link.
%C A binary relation is idempotent iff it is both dense (A355730) and transitive (A006905).
%C A binary relation is idempotent iff it is both limit dominating (A366194) and limit dominated (A366722). See Gregory, Kirkland, and Pullman link.
%C 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.
%C 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)
%D F. Kammüller, Interactive Theorem Proving in Software Engineering, Habilitationsschrift, Technische Universitaet Berlin (2006).
%D Ki Hang Kim, Boolean Matrix Theory and Applications, Marcel Decker, 1982.
%H G. Brinkmann and B. D. McKay, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/McKay/mckay170.html">Counting unlabeled topologies and transitive relations</a>, J. Integer Sequences, Volume 8, 2005.
%H K. K.-H. Butler and G. Markowsky, <a href="https://www.koreascience.or.kr/article/JAKO197225748110925.pdf">The Number of Maximal Subgroups of the Semigroup of Binary Relations</a>, Kyungpook Math. J. Vol 12, June 1972.
%H D. A. Gregory, S. Kirkland, and N. J. Pullman, <a href="https://doi.org/10.1016/0024-3795(93)90323-G">Power convergent Boolean matrices</a>, Linear Algebra and its Applications, Volume 179, 15 January 1993, Pages 105-117.
%H F. Kammüller, <a href="http://www.eecs.tu-berlin.de/fileadmin/f4/TechReports/2008/2008-15.pdf">Counting idempotent relations</a>.
%H F. Kammüller and J. W. Sanders, <a href="http://doi.org/10.1007/978-3-540-31862-0_23">Idempotent relations in Isabelle/HOL</a>, International Colloquium on Theoretical Aspects of Computing, ICTAC'04. Volume 3407 of Lecture Notes in Computer Science, Springer-Verlag (2005).
%H G. Pfeiffer, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL7/Pfeiffer/pfeiffer6.html">Counting transitive relations</a>, J. Integer Sequences, Volume 7, 2004, #3.
%H D. Rosenblatt, <a href="https://nvlpubs.nist.gov/nistpubs/jres/67B/jresv67Bn4p249_A1b.pdf">On the graphs of finite Boolean relation matrices</a>, Journal of Research of the National Bureau of Standards, 67B No. 4, 1963.
%H B. M. Schein, <a href="https://doi.org/10.3792/pja/1195520400">A construction for idempotent binary relations</a>, Proc. Japan Acad., Vol. 46, No. 3 (1970), pp. 246-247.
%e 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
%e 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
%t 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 *)
%Y 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.
%Y Row sums of A360984.
%K nonn,hard,more
%O 0,2
%A Florian Kammüller (flokam(AT)cs.tu-berlin.de), Aug 28 2006
%E Offset corrected by _James Mitchell_, Jul 28 2013
%E a(1) corrected by _Philippe Beaudoin_, Aug 11 2015
|
