Number of Directed Acyclic Graphs with indegree at most one

Question

How many DAGs are there where every vertex has indegree at most one? If not known, is there a lower bound?

Answer 1

Let $G$ be such a DAG. $G$ must have at least one source, i.e., at least one vertex of indegree $0$. Let $R$ be the set of sources, and for each $r\in R$ let $G_r$ be the set of vertices reachable from $r$. Each $G_r$ is an arborescence. Add one new vertex $v_G$ with edges from $v_G$ to each $r\in R$ to get a new DAG $G'$; $G'$ is itself an arborescence. Conversely, deleting the root from an arborescence with at least two vertices leaves a DAG in which every vertex has indegree at most $1$.

The sequence $\langle a_n:n\in\Bbb N\rangle$ in OEIS A000081 gives the number of unlabelled rooted trees with $n$ nodes; this is the same as the number of arborescences on $n$ nodes, so it’s the number of DAGs on $n-1$ nodes, all with indegree at most $1$. No closed form is given. There is an asymptotic result,

$$a_n\sim cd^nn^{-3/2}\;,$$

where $c=0.439924\ldots$ is Otter’s asymptotic constant $\beta$, and $d=2.955765\ldots$ is Otter’s rooted tree constant.

There is also a recurrence,

$$a_{n+1}=\frac1n\sum_{k=1}^n\left(\sum_{d\mid k}da_d\right)a_{n-k+1}\;.$$

Answer 2

I would like to add to the excellent answer by @BrianMScott by giving a proof of the recurrence relation. What we have here are forests of rooted trees. Working with rooted trees we obtain the species $\mathcal{T}$ (multiset of trees attached to the root):

$$\mathcal{T} = \mathcal{Z} \mathfrak{M}(\mathcal{T}).$$

This translates to the generating function

$$T(z) = z \exp\left(\sum_{l\le 1} \frac{T(z^l)}{l}\right).$$

Differentiate to obtain

$$T'(z) = \exp\left(\sum_{l\ge 1} \frac{T(z^l)}{l}\right) \\ + z \exp\left(\sum_{l\ge 1} \frac{T(z^l)}{l}\right) \sum_{l\ge 1} T'(z^l) z^{l-1} \\ = \frac{1}{z} T(z) + T(z) \sum_{l\ge 1} T'(z^l) z^{l-1}.$$

Extracting coefficients on $[z^n]$ yields

$$(n+1) T_{n+1} = T_{n+1} + \sum_{q=0}^{n-1} T_{n-q} [z^q] \sum_{l\ge 1} T'(z^l) z^{l-1} \\ = T_{n+1} + \sum_{q=0}^{n-1} T_{n-q} \sum_{l\ge 1} [z^{q-(l-1)}] T'(z^l).$$

For the coefficient extractor to return a non-zero coefficient we must have $q = l-1+pl$ with $p\ge 0$ and $l-1+lp\le n-1$ which implies $p\le n/l-1.$ The result is

$$(n+1) T_{n+1} = T_{n+1} + \sum_{l\ge 1} \sum_{p=0}^{\lfloor n/l\rfloor-1} T_{n+1-l(p+1)} [z^{pl}] T'(z^l) \\ = T_{n+1} + \sum_{l=1}^{n} \sum_{p=0}^{\lfloor n/l\rfloor-1} (p+1) T_{p+1} T_{n+1-l(p+1)}.$$

This finally yields

$$\bbox[5px,border:2px solid #00A000]{ T_{n+1} = \frac{1}{n} \sum_{l=1}^{n} \sum_{p=0}^{\lfloor n/l\rfloor-1} (p+1) T_{p+1} T_{n+1-l(p+1)}.}$$

Working to simplify this we first obtain

$$\frac{1}{n} \sum_{l=1}^{n} \sum_{p=1}^{\lfloor n/l\rfloor} p T_{p} T_{n+1-lp}.$$

Now we are enumerating pairs $lp$ here where $1\le lp\le n$ so putting $lp=k$ we may write this as

$$\frac{1}{n} \sum_{k=1}^{n} \sum_{p|k} p T_{p} T_{n+1-k}$$

which is

$$\bbox[5px,border:2px solid #00A000]{ T_{n+1} = \frac{1}{n} \sum_{k=1}^{n} T_{n+1-k} \sum_{p|k} p T_{p}.}$$

This is the form given in OEIS A000081.

Answering the question given by the OP we return to forests of rooted trees and obtain the species $\mathcal{F}$ with equation

$$\mathcal{F} = \mathfrak{M}(\mathcal{T})$$ which in terms of generating functions yields

$$F(z) = T(z)/z.$$

This simply says that a forest is in a bijection with a tree where we attach the trees to a new root node. Therefore a tree on $n$ nodes yields a forest on $n-1$ nodes and we may use $T_{n+1}$ to count the DAGs that were being queried.