A395544 Number of transitive relations on an n-set with at most eight ordered pairs.

1, 2, 13, 170, 3603, 76537, 1237063, 14880672, 138026469, 1028480758, 6376565693, 33839690644, 157221773711, 651190185153, 2440047906103, 8372244421294, 26571862674345, 78674635232130, 218890567556797, 575838484707638, 1440097225363915, 3439798249272641, 7879563768710679

Offset

0,2

Links

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

Index entries for linear recurrences with constant coefficients, signature (17,-136,680,-2380,6188,-12376,19448,-24310,24310,-19448,12376,-6188,2380,-680,136,-17,1).

Formula

a(n) = A395093(n) + A393925(n).

Example

a(2) = 13: every transitive relation on a 2-set has at most 4 <= 8 ordered pairs, so all 13 transitive relations on [2] are counted.
a(3) = 170: of the 171 transitive relations on [3], only the complete relation [3] X [3] (with 9 ordered pairs) is excluded.

Crossrefs

Cf. A006905, A348634, A349849, A349919, A349927, A392460, A393216, A393925, A394769, A395093.

Sequence in context: A078363 A143851 A395093 * A397036 A088316 A006905

Adjacent sequences: A395540 A395542 A395543 * A395545 A395546 A395547

Keyword

nonn,easy

Author

Firdous Ahmad Mala, Apr 28 2026

Status

approved