Counting extensional acyclic digraphs


Transitive sets with n elements were counted by Peddicord in 1962, by the use of Ackermann’s numeric encoding of a (hereditarily finite) set. In this paper we give a combinatorial interpretation of this number by counting extensional acyclic digraphs. In a similar constructive manner, we also obtain the number of weakly extensional acyclic digraphs with a given number of labeled sinks and a given number of sources, or with a given number of vertices of maximum rank. © 2011 Elsevier B.V.

Information Processing Letters