A349927 Number of transitive relations on an n-set with exactly three ordered pairs.

0, 0, 2, 43, 276, 1150, 3710, 10017, 23688, 50556, 99450, 183095, 319132, 531258, 850486, 1316525, 1979280, 2900472, 4155378, 5834691, 8046500, 10918390, 14599662, 19263673, 25110296, 32368500, 41299050, 52197327, 65396268, 81269426, 100234150, 122754885, 149346592, 180578288, 217076706

Offset

0,3

Links

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

Index entries for linear recurrences with constant coefficients, signature (7,-21,35,-35,21,-7,1).

Formula

a(n) = 2*C(n,2) + 37*C(n,3) + 116*C(n,4) + 180*C(n,5) + 120*C(n,6).

a(n) = (1/6)*(n^6 - 6*n^5 + 24*n^4 - 47*n^3 + 38*n^2 - 10*n).

Example

a(2) = 2. These two transitive relations are {(1,1),(1,2),(2,2)} and {(1,1),(2,1),(2,2)} on the 2-set {1,2}.

Mathematica

A349927[n_] := Total[{2, 37, 116, 180, 120}*Binomial[n, Range[2, 6]]];
Array[A349927, 35, 0] (* or *)
LinearRecurrence[{7, -21, 35, -35, 21, -7, 1}, {0, 0, 2, 43, 276, 1150, 3710}, 35] (* Paolo Xausa, Mar 24 2026 *)

Prog

(PARI) A349927(n) = (1/6)*(n^6 - 6*n^5 + 24*n^4 - 47*n^3 + 38*n^2 - 10*n); \\ Antti Karttunen, Dec 05 2021

Crossrefs

Cf. A349919, A349849.

Sequence in context: A107156 A062582 A073594 * A112097 A354304 A375157

Adjacent sequences: A349924 A349925 A349926 * A349928 A349929 A349930

Keyword

nonn,easy

Author

Firdous Ahmad Mala, Dec 05 2021

Extensions

More terms from Paolo Xausa, Mar 24 2026

Status

approved