This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A121337 Number of idempotent relations on n labeled elements. 2
 1, 2, 11, 123, 2360, 73023, 3465357 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,2 REFERENCES F. Kammüller, Interactive Theorem Proving in Software Engineering, Habilitationsschrift, Technische Universitaet Berlin (2006). LINKS G. Brinkmann and B. D. McKay, Counting unlabeled topologies and transitive relations, J. Integer Sequences, Volume 8, 2005. 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. FORMULA A relation r is idempotent if r ; r = r, where ; denotes sequential composition. 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). Sequence in context: A247736 A155928 A001946 * A269069 A224366 A279703 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 18 08:08 EDT 2019. Contains 328146 sequences. (Running on oeis4.)