A394722 Number of transitive relations on an n-set with at most four ordered pairs.

1, 2, 13, 125, 932, 5161, 22362, 80018, 246115, 669892, 1649171, 3734347, 7880798, 15663155, 29566552, 53371656, 92651957, 155403478, 252828745, 400298537, 618516616, 934914317, 1385303558, 2015818510, 2885177847, 4067301176, 5654314927, 7759984663, 10523612450, 14114439607, 18736596836

Offset

0,2

Links

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

Index entries for linear recurrences with constant coefficients, signature (9,-36,84,-126,126,-84,36,-9,1).

Formula

a(n) = C(n,0) + C(n,1) + 10*C(n,2) + 91*C(n,3) + 503*C(n,4) + 1630*C(n,5) + 3060*C(n,6) + 3360*C(n,7) + 1680*C(n,8).

a(n) = A393295(n) + A349849(n).

a(n) = 1 + A000290(n) + A349919(n) + A349927(n) + A349849(n).

G.f.: (1 - 7*x + 31*x^2 - 4*x^3 + 233*x^4 + 307*x^5 + 435*x^6 + 512*x^7 + 172*x^8)/(1 - x)^9. - Stefano Spezia, Mar 30 2026

Example

a(1) = 2 because there are only 2 transitive relations on a singleton with at most four ordered pairs, which include the empty relation and the universal relation.

Mathematica

A394722[n_] := Total[{10, 91, 503, 1630, 3060, 3360, 1680}*Binomial[n, Range[2, 8]]] + n + 1;
Array[A394722, 35, 0] (* or *)
LinearRecurrence[{9, -36, 84, -126, 126, -84, 36, -9, 1}, {1, 2, 13, 125, 932, 5161, 22362, 80018, 246115}, 35] (* Paolo Xausa, Apr 07 2026 *)

Crossrefs

Cf. A393295, A349849, A000290, A349919, A349927.

Sequence in context: A151361 A328008 A372103 * A073559 A074365 A071362

Adjacent sequences: A394719 A394720 A394721 * A394723 A394724 A394725

Keyword

nonn,easy

Author

Firdous Ahmad Mala, Mar 30 2026

Status

approved