A349849 Number of transitive relations on an n-set with exactly four ordered pairs.

0, 0, 1, 45, 549, 3755, 18120, 69006, 220710, 616554, 1545435, 3544915, 7552611, 15119325, 28699034, 52032540, 90643260, 152465316, 248625765, 394404489, 610396945, 923906655, 1370595996, 1996425530, 2859913794, 4034751150, 5612802975, 7707539151, 10457928495

Offset

0,4

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,2) + 42*C(n,3) + 375*C(n,4) + 1450*C(n,5) + 2940*C(n,6) + 3360*C(n,7) + 1680*C(n,8).

a(n) = (1/24)*(n^8 - 12*n^7 + 84*n^6 - 340*n^5 + 814*n^4 - 1130*n^3 + 829*n^2 - 246*n).

Example

a(2) = binomial(2,2) = 1. The only transitive relation with four ordered pairs on the 2-set {1,2} is {(1,1),(1,2),(2,1),(2,2)}.

Mathematica

A349849[n_] := Total[{1, 42, 375, 1450, 2940, 3360, 1680}*Binomial[n, Range[2, 8]]];
Array[A349849, 30, 0] (* or *)
LinearRecurrence[{9, -36, 84, -126, 126, -84, 36, -9, 1}, {0, 0, 1, 45, 549, 3755, 18120, 69006, 220710}, 30] (* Paolo Xausa, Mar 24 2026 *)

Crossrefs

Cf. A349919, A349927, A006905.

Sequence in context: A283116 A223047 A147842 * A027783 A160837 A160838

Adjacent sequences: A349846 A349847 A349848 * A349850 A349851 A349852

Keyword

nonn,easy

Author

Firdous Ahmad Mala, Dec 06 2021

Status

approved