A395093 Number of transitive relations on an n-set with at most seven ordered pairs.

1, 2, 13, 170, 3174, 51272, 613273, 5522106, 39166083, 228033502, 1126456193, 4844806594, 18514777184, 63899672916, 201812008205, 589636064914, 1608228271365, 4126273835322, 10023956065669, 23185222993658, 51305293465210, 109069477192736, 223570382775345, 443281708368842

Offset

0,2

Links

Paolo Xausa, Table of n, a(n) for n = 0..10000

Index entries for linear recurrences with constant coefficients, signature (15,-105,455,-1365,3003,-5005,6435,-6435,5005,-3003,1365,-455,105,-15,1).

Formula

a(n) = C(n,0) + C(n,1) + 10*C(n,2) + 136*C(n,3) + 2565*C(n,4) + 36981*C(n,5) + 350035*C(n,6) + 2200507*C(n,7) + 9502656*C(n,8) + 28893816*C(n,9) + 62455680*C(n,10) + 94857840*C(n,11) + 97130880*C(n,12) + 60540480*C(n,13) + 17297280*C(n,14).

a(n) = A394769(n) + A392460(n).

Example

a(2) = 13, the same as the total number of transitive relations on a 2-set because every transitive relation on a 2-set has at most 7 (actually at most 4) ordered pairs.
a(3) = 170: of the 171 transitive relations on a 3-set, the only one excluded is the complete relation {1,2,3} x {1,2,3} with 9 > 7 ordered pairs.

Mathematica

A395093[n_] := 1 + n + Total[{10, 136, 2565, 36981, 350035, 2200507, 9502656, 28893816, 62455680, 94857840, 97130880, 60540480, 17297280}*Binomial[n, Range[2, 14]]];
Array[A395093, 25, 0] (* Paolo Xausa, May 22 2026 *)
(* Alternative: *)
LinearRecurrence[{15, -105, 455, -1365, 3003, -5005, 6435, -6435, 5005, -3003, 1365, -455, 105, -15, 1}, {1, 2, 13, 170, 3174, 51272, 613273, 5522106, 39166083, 228033502, 1126456193, 4844806594, 18514777184, 63899672916, 201812008205}, 25] (* Paolo Xausa, May 22 2026 *)

Crossrefs

Cf. A000290, A006905, A349919, A349927, A349849, A348634, A393216, A392460, A394769.

Sequence in context: A351021 A078363 A143851 * A395544 A397036 A088316

Adjacent sequences: A395090 A395091 A395092 * A395094 A395095 A395096

Keyword

nonn,easy

Author

Firdous Ahmad Mala, Apr 11 2026

Status

approved