A397036 The number of transitive relations T on an n-element set such that T has a transitive subset of every cardinality k in {0,1,...,|T|}.

1, 2, 13, 170, 3981, 154182, 9414027

Offset

0,2

Comments

a(n) is the number of transitive relations T such that for every possible size of a subset of T, at least one transitive sub-relation of that size exists.

Number of transitive relations T on an n-element set such that, for every k with 0 <= k <= |T|, T has a transitive subset with exactly k ordered pairs.

Links

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

Example

For n = 3 there are A006905(3) = 171 transitive relations on {1,2,3}. The only failure is the complete relation {1,2,3} X {1,2,3} (size 9): removing any pair (a,b) leaves (a,c),(c,b) for some c without (a,b), violating transitivity, so no transitive subset of size 8 exists. Thus a(3) = 171 - 1 = 170.
For n = 4, the 13 failing transitive relations are all of the form A X B with |A|, |B| >= 3 (A, B subsets of {1,2,3,4}); each such "complete bipartite" relation has no transitive subset of size |A|*|B| - 1. Thus a(4) = 3994 - 13 = 3981.

Crossrefs

Cf. A006905.

Sequence in context: A143851 A395093 A395544 * A088316 A006905 A119400

Adjacent sequences: A397030 A397031 A397032 * A397037 A397039 A397040

Keyword

nonn,more,hard,new

Author

Firdous Ahmad Mala, Jun 14 2026

Status

approved