login
A341471
Number of antisymmetric, antitransitive relations on n labeled nodes.
1
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."
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
KEYWORD
nonn,more
AUTHOR
Peter Kagey, Feb 13 2021
EXTENSIONS
a(6)-a(8) from Bert Dobbelaere, Feb 27 2021
STATUS
approved