A391878 The number of vacuously transitive relations on an n-set.

1, 2, 12, 104, 1392, 26912, 745152, 29170304, 1609166592, 124719636992, 13580858084352, 2077626948184064, 446988353188687872, 135342931175100588032, 57738133535238631636992, 34729785659702961812701184, 29480128808177192701492396032, 35332909777591732535498857644032

Offset

0,2

Comments

A relation R on a set S is vacuously transitive if it is transitive but there are no two ordered pairs (a,b) and (b,c) in the relation where a != b and b != c.

a(n) is also the number of transitive relations T on an n-set such that every subset of T is also transitive. - Firdous Ahmad Mala, Jun 14 2026

References

C. K. Gordon, Jr., Introduction to Mathematical Structures, Dickenson Publishing Co., Belmont, CA, 1967, p. 53.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..111

Formula

a(n) = 2^n * A001831(n). - Alois P. Heinz, Jan 29 2026

Example

a(2) = 12 because out of 16 relations on a 2-set, there are four that contain pairs (a,b), (b,c), a != b, b != c.

Mathematica

a[0]=1; a[n_]:=2^n*Sum[Binomial[n, k]*(2^k-1)^(n-k), {k, 0, n}]; Array[a, 18, 0] (* Stefano Spezia, Jan 30 2026 *)

Crossrefs

Cf. A000079, A001831, A002416, A006905.

Sequence in context: A216794 A218300 A380406 * A125031 A258230 A085867

Adjacent sequences: A391875 A391876 A391877 * A391879 A391880 A391881

Keyword

nonn,changed

Author

Firdous Ahmad Mala, Jan 29 2026

Extensions

More terms from Alois P. Heinz, Jan 29 2026

Status

approved