A problem equivalent to counting directed acyclic graphs on labeled vertices

Abstract

An encoding of directed acyclic graphs (DAGs) on labeled vertices is proposed, which is a generalisation of the Prüfer code for labeled trees, if a certain orienation on the edges of the tree is introduced. Hence it is shown that the number of sequences $S_1,S_2,\dots ,S_{n-1}$ of subsets of $\{1,2,\dots ,n\}$ with the property that $|{\bigcup }_{i=1}^k{S}_i|\le k$ for every $1\le k\le n-1$, is equal to the number of DAGs on $n$ labeled vertices.