A393295 Number of transitive relations on an n-set with at most three ordered pairs.

1, 2, 12, 80, 383, 1406, 4242, 11012, 25405, 53338, 103736, 189432, 328187, 543830, 867518, 1339116, 2008697, 2938162, 4202980, 5894048, 8119671, 11007662, 14707562, 19392980, 25264053, 32550026, 41511952, 52445512, 65683955, 81601158, 100614806, 123189692, 149841137

Offset

0,2

Links

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

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

Formula

a(n) = C(n,0) + C(n,1) + 9*C(n,2) + 49*C(n,3) + 128*C(n,4) + 180*C(n,5) + 120*C(n,6).

a(n) = A393238(n) + A349927(n). (corrected by Falk Hüffner, May 21 2026)

a(n) = (1/6)*(n^6 - 6*n^5 + 27*n^4 - 53*n^3 + 56*n^2 - 19*n + 6). - Falk Hüffner, May 21 2026

Example

On the 2-set {1,2}, there are 2^4 = 16 relations, and a(2) = 12 excludes exactly 4 of them: the universal relation {(1,1),(1,2),(2,1),(2,2)} is transitive but has 4 > 3 ordered pairs, and the non-transitive {(1,2),(2,1)}, {(1,1),(1,2),(2,1)}, and {(1,2),(2,1),(2,2)}. - Falk Hüffner, May 21 2026

Mathematica

a[n_] := Total[{1, 1, 9, 49, 128, 180, 120} * Binomial[n, Range[0, 6]]]; Array[a, 33, 0] (* Amiram Eldar, Feb 10 2026 *)

Crossrefs

Cf. A349927, A393238.

Sequence in context: A289662 A107632 A270775 * A240836 A270919 A082142

Adjacent sequences: A393292 A393293 A393294 * A393296 A393297 A393298

Keyword

nonn,easy

Author

Firdous Ahmad Mala, Feb 10 2026

Status

approved