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 extensional acyclic digraphs
POLICRITI, Alberto;
2011-01-01
Abstract
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.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
IPL - Counting extensional acyclic digraphs.pdf
non disponibili
Tipologia:
Versione Editoriale (PDF)
Licenza:
Non pubblico
Dimensione
152.7 kB
Formato
Adobe PDF
|
152.7 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
