A341473 -id:A341473 - cp's OEIS frontend

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

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

Offset: 0

Peter Kagey, Feb 13 2021

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."

			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)}.

Wikipedia, Binary relation

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).

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions