A391878 - OEIS

%I #51 Jun 14 2026 20:19:47

%S 1,2,12,104,1392,26912,745152,29170304,1609166592,124719636992,

%T 13580858084352,2077626948184064,446988353188687872,

%U 135342931175100588032,57738133535238631636992,34729785659702961812701184,29480128808177192701492396032,35332909777591732535498857644032

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

%C 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.

%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

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

%H Alois P. Heinz, <a href="/A391878/b391878.txt">Table of n, a(n) for n = 0..111</a>

%F a(n) = 2^n * A001831(n). - _Alois P. Heinz_, Jan 29 2026

%e 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.

%t 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 *)

%Y Cf. A000079, A001831, A002416, A006905.

%K nonn

%O 0,2

%A _Firdous Ahmad Mala_, Jan 29 2026

%E More terms from _Alois P. Heinz_, Jan 29 2026