A341471 Number of antisymmetric, antitransitive relations on n labeled nodes.

1, 1, 3, 21, 317, 9735, 583907, 66226033, 13837055261

Offset

0,3

Comments

An antisymmetric, antitransitive relation is one where xRy implies "not yRx" and xRy and yRz implies "not xRz". All antitransitive relations are irreflexive, so this sequence is counting "anti-equivalence relations".

a(n) < A047656(n).

Idea thanks to Richard Arratia, who saw, verbatim in an editorial, "False equivalences? There were almost too many to count."

Links

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

Wikipedia, Binary relation

Example

There are a(3) = 21 antisymmetric, antitransitive relations on n = 3 letters:
  - the empty relation,
  - all six relations containing only a single pair (x,y) (with x != y),
  - all twelve relations {(x1,y1), (x2,y2)} containing exactly two ordered pairs, neither of which is (y1,x1) or (y2,x2), and
  - two relations containing three ordered pairs: {(1,2), (2,3), (3,1)} and {(1,3), (3,2), (2,1)}.

Crossrefs

Number of relations on labeled nodes: A000110 (equivalence), A001831 (transitive and antitransitive), A002416 (unrestricted), A006125 (symmetric), A006905 (transitive), A047656 (reflexive and antisymmetric), A083667 (antisymmetric), A341473 (antitransitive).

Sequence in context: A331583 A305532 A005329 * A134528 A332974 A118410

Adjacent sequences: A341468 A341469 A341470 * A341472 A341473 A341474

Keyword

nonn,more

Author

Peter Kagey, Feb 13 2021

Extensions

a(6)-a(8) from Bert Dobbelaere, Feb 27 2021

Status

approved