|
|
A121337
|
|
Number of idempotent relations on n labeled elements.
|
|
12
|
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
A relation r is idempotent if r ; r = r, where ; denotes sequential composition.
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
|
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).
|
|
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
|
|
|
KEYWORD
|
nonn,hard,more
|
|
AUTHOR
|
Florian Kammüller (flokam(AT)cs.tu-berlin.de), Aug 28 2006
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|