A396664 - OEIS

%I #13 Jun 08 2026 17:13:54

%S 0,0,3,264,16830,1269490,128127540

%N Number of relations on an n-set whose minimum-deletion-to-transitivity equals one.

%C Equivalently, a(n) counts binary relations R on {1,...,n} such that R is not transitive and there exists an ordered pair p in R with R \ {p} transitive. That is, the minimum number of single-pair deletions required to make R transitive equals 1.

%C Dual notion to A395083 (transitive closure adds exactly one pair). Here we count relations from which exactly one pair must be removed to attain transitivity.

%e For n=2 the a(2)=3 relations on {1,2} are: {(1,2),(2,1)}, {(1,1),(1,2),(2,1)}, and {(1,2),(2,1),(2,2)}. Each is non-transitive (e.g. (1,2),(2,1) in R but (1,1) not in R for the first); in each case removing exactly one ordered pair (namely (1,2) or (2,1)) yields a transitive relation.

%Y Cf. A395083.

%K nonn,hard,more

%O 0,3

%A _Firdous Ahmad Mala_, Jun 02 2026