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
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
KEYWORD
nonn,more
AUTHOR
Peter Kagey, Feb 13 2021
EXTENSIONS
a(6)-a(8) from Bert Dobbelaere, Feb 27 2021
STATUS
approved