A396875 Number of relations on an n-set whose minimum-deletion-to-transitivity equals five.

0, 0, 0, 0, 368, 6449520, 13111763730

Offset

0,5

Comments

a(n) counts binary relations R on {1,...,n} such that R is not transitive, no deletion of fewer than five ordered pairs from R yields a transitive relation, but there exist five ordered pairs p_1,...,p_5 in R with R \ {p_1,...,p_5} transitive.

Links

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

Example

For n=4 the smallest example by cardinality has |R|=8: take R = {(1,2),(1,3),(2,3),(2,4),(3,1),(3,4),(4,1),(4,2)}. A maximum transitive subrelation is {(1,2),(1,3),(2,3)} of size 3. No subset of R obtained by deleting four or fewer pairs is transitive.

Crossrefs

Cf. A396664, A396669, A006905.

Sequence in context: A097501 A239411 A239339 * A352224 A294597 A294711

Adjacent sequences: A396872 A396873 A396874 * A396877 A396878 A396879

Keyword

nonn,hard,more

Author

Firdous Ahmad Mala, Jun 08 2026

Status

approved