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,3

Links

Table of n, a(n) for n=0..44.

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).

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)

Example

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)}.

Mathematica

LinearRecurrence[{5, -10, 10, -5, 1}, {0, 0, 5, 27, 90}, 50] (* Harvey P. Dale, Oct 23 2022 *)

Crossrefs

Cf. A006905, A336535, A349927.

This is a diagonal of the array A285192.

Sequence in context: A135713 A085740 A338996 * A212783 A226315 A201436

Adjacent sequences: A349916 A349917 A349918 * A349920 A349921 A349922

Keyword

nonn,easy

Author

Firdous Ahmad Mala, Dec 05 2021

Status

approved