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

0, 0, 3, 264, 16830, 1269490, 128127540

Offset

0,3

Comments

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.

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.

Links

Table of n, a(n) for n=0..6.

Example

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.

Crossrefs

Cf. A395083.

Sequence in context: A219550 A319587 A058451 * A230373 A383690 A003761

Adjacent sequences: A396661 A396662 A396663 * A396665 A396666 A396667

Keyword

nonn,hard,more

Author

Firdous Ahmad Mala, Jun 02 2026

Status

approved