A349919 Number of transitive relations on an n-set with exactly two ordered pairs.
0, 0, 5, 27, 90, 230, 495, 945, 1652, 2700, 4185, 6215, 8910, 12402, 16835, 22365, 29160, 37400, 47277, 58995, 72770, 88830, 107415, 128777, 153180, 180900, 212225, 247455, 286902, 330890, 379755, 433845, 493520, 559152, 631125, 709835, 795690, 889110, 990527, 1100385, 1219140, 1347260, 1485225, 1633527, 1792670
Offset: 0
Examples
a(2) = 5. The five relations on a 2-set are {(1,1),(1,2)}, {(1,1),(2,1)}, {(1,1),(2,2)}, {(1,2),(2,2)} and {(2,1),(2,2)}.
Links
- Firdous Ahmad Mala, Counting Transitive Relations with Two Ordered Pairs, Journal of Applied Mathematics and Computation, 5(4), 247-251.
- Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).
Programs
-
Mathematica
LinearRecurrence[{5,-10,10,-5,1},{0,0,5,27,90},50] (* Harvey P. Dale, Oct 23 2022 *)
Formula
a(n) = 5*C(n,2) + 12*C(n,3) + 12*C(n,4).
a(n) = (1/2)*(n^4 - 2*n^3 + 4*n^2 - 3*n).
a(n) = A336535(n) - 1.
From Elmo R. Oliveira, Aug 26 2025: (Start)
G.f.: x^2*(5 + 2*x + 5*x^2)/(1 - x)^5.
E.g.f.: x^2*(5 + 4*x + x^2)*exp(x)/2.
a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5). (End)