| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428621 | Information Processing Letters | 2011 | 5 Pages |
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.
► Counting transitive sets is equivalent to counting extensional acyclic digraphs. ► We give a recurrence formula for labeled extensional acyclic digraphs. ► We count (weakly) extensional acyclic digraphs by sources. ► We also count (weakly) extensional acyclic digraphs by vertices of maximum rank.
