A396055 Number of relations R on an n-element set such that the transitive closure of R has exactly six elements more than R.

0, 0, 0, 2, 8472, 2107750, 543534225

Offset

0,4

Comments

Equivalently, a(n) is the number of binary relations R on an n-set for which exactly six ordered pairs must be adjoined to obtain a transitive relation, i.e. |closure(R) \ R| = 6.

Links

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

Example

For n = 0, 1, 2 every relation R on [n] satisfies |closure(R) \ R| <= 4 < 6, so a(0) = a(1) = a(2) = 0.
For n = 3, a(3) = 2: the only two relations on a 3-set whose transitive closure is six ordered pairs larger are the directed 3-cycles R_1 = {(1,2),(2,3),(3,1)} and R_2 = {(1,3),(3,2),(2,1)}; the transitive closure of each is the universal relation on {1,2,3} (all 9 ordered pairs), and so 9 - 3 = 6 pairs must be added.

Crossrefs

Cf. A006905, A395083, A395919, A395920.

Sequence in context: A272241 A171939 A104904 * A272247 A167748 A203755

Adjacent sequences: A396052 A396053 A396054 * A396056 A396057 A396058

Keyword

nonn,hard,more

Author

Firdous Ahmad Mala, May 14 2026

Extensions

a(6) from Christian Sievers, May 20 2026

Status

approved