login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

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.

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.

License Agreements, Terms of Use, Privacy Policy. .

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