A394405 Number of transitive relations, on an n-set, that are not quasi-orders.

0, 1, 9, 142, 3639, 147361, 9205662, 868687289, 121564924269, 24827487632524, 7298473245637245, 3051704700294366865, 1796484203652704550216, 1475854812473362457120271, 1679123941097593174888995537, 2628136437874738720379203091550, 5626082456400367348667440806098859

Offset

0,3

Comments

A quasi-order is a relation that is both transitive and reflexive.

a(n) is the number by which the number of transitive relations exceeds the number of quasi-orders.

Links

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

Formula

a(n) = A006905(n) - A000798(n).

Example

On a 1-set, X={x}, the only relation that is transitive but not reflexive (or a quasi-order) is the empty relation, thus, a(1)=1.

Crossrefs

Cf. A000798, A006905.

Sequence in context: A187402 A385929 A363478 * A303147 A317354 A050787

Adjacent sequences: A394402 A394403 A394404 * A394406 A394407 A394408

Keyword

nonn,hard

Author

Firdous Ahmad Mala, Mar 19 2026

Status

approved