login
Number of vacuously transitive relations on n nodes up to isomorphism.
(Formerly M1764)
3

%I M1764 #23 Oct 20 2023 22:32:16

%S 2,7,24,92,388

%N Number of vacuously transitive relations on n nodes up to isomorphism.

%C A transitive relation is vacuously transitive if it does not contain any transitive triple, that is, three distinct ordered pairs (a,b), (b,c), (a,c). - _Jukka Kohonen_, Sep 17 2021

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H H. Sharp, Jr., <a href="https://doi.org/10.1016/0012-365X(73)90081-2">Enumeration of vacuously transitive relations</a>, Discrete Math. 4 (1973), 185-196.

%e a(2)=7: The seven relations are {}, {(1,1)}, {(1,1),(2,2)}, {(2,1)}, {(1,1),(2,1)}, {(1,1),(2,1),(2,2)} and {(2,1),(2,2)}. - _Jukka Kohonen_, Sep 17 2021

%Y Cf. A347700, A348240.

%K nonn,more

%O 1,1

%A _N. J. A. Sloane_

%E Clarified and offset corrected by _Jukka Kohonen_, Sep 17 2021