Is there a formula for the number of st-dags (DAG with 1 source and 1 sink) with n vertices? I am looking at doing some basic validation on a database of st-dags. It would be useful to have:

*

*A formula for the number of non-isomorphic st-dags with n vertices


*A formula for the same with n vertices and p edges
Is there such a formula, and is there some literature (accessible to the non-mathematician) that might discuss any special properties of st-dags.
 A: This is not a formula, but a method of counting the graphs in OP faster than straightforward enumeration. It's superpolynomial in complexity (although sub-exponential).
Let's start with a recurrence for the number $a_n$ of labelled directed acyclic graphs on $n$ vertices: $a_0 = 1$, and for any $n \geq 1$
$$a_n = \sum_{k = 1}^n (-1)^{k - 1} {n \choose k} a_{n - k} 2^{k(n - k)}.$$
This is inclusion-exclusion principle applied to the number $k$ of sources in the graph. If we want the graph to have a single sink, we simply forbid the empty graph, and each of the new sources to not have any outgoing edges, resulting in a recurrence $a'_{0} = 1$, $a'_{1} = 1$, and for any $n \geq 2$
$$a'_n = \sum_{k = 1}^n (-1)^{k - 1} {n \choose k} a'_{n - k} (2^{n - k} - 1)^k.$$
Finally, to also have a single source, for the final set of sources we tweak the inclusion-exclusion weights: having $k$ new sources on the final step has weight $(-1)^{k - 1} \cdot k$. One can see that only the graphs with a single source are not cancelled out (and are counted once), thus
$$a''_n = \sum_{k = 1}^n (-1)^{k - 1} {n \choose k} k a'_{n - k} (2^{n - k} - 1)^k.$$
To count unlabelled graphs of this kind (we denote the numbers $b_n$, $b'_n$, $b''_n$ similar to the above), we combine the above approach with Burnside's lemma. Let $S_{n - 1}$ be the symmetric group acting on all $n$ vertices except for the unique sink. Then the number of unlabelled graphs is given by $b''_n = \frac{1}{(n - 1)!} \sum_{\pi \in S_{n - 1}} a''_{\pi}$, where $a''_{\pi}$ is the number of labelled single source, single sink DAGs stabilized by the permutation $\pi$. Clearly, $a''_{\pi}$ depends only on the conjugation class (cyclic structure) of $\pi$, so we can write $a''_{\lambda}$ for a partition $\lambda$ of $n-1$.
With a slightly more sophisticated version of inclusion-exclusion, we have
$$a'_{\lambda} = \sum_{\varnothing \neq \mu \subset \lambda} (-1)^{|\mu|} {\lambda \choose \mu} a'_{\lambda - \mu} \prod_{i \in \mu} \left(2 \prod_{j \in \lambda - \mu} 2^{(i, j)} - 1\right).$$
The notation makes sense if $\lambda$ and $\mu$ are treated as multisets. Similarly, one can show that
$$a''_{\lambda} = \sum_{\varnothing \neq \mu \subset \lambda} (-1)^{|\mu|} {\lambda \choose \mu} \omega(\mu) a'_{\lambda - \mu} \prod_{i \in \mu} \left(2 \prod_{j \in \lambda - \mu} 2^{(i, j)} - 1\right),$$
where $\omega(\mu)$ is the number of summands $1$.
The complexity of this solution is roughly $Poly(n) $A000712$(n) \sim Poly(n) exp(\frac{2\pi}{\sqrt{3}}\sqrt{n})$. This is an improvement of my initial approach from the comments to another answer, and, implemented in C++, produces answers up to $n = 40$ in about two minutes.
To count unlabelled graphs of this kind with prescribed number of edges, one can ostensibly modify this approach to operate with generating polynomials $\sum_{e = \text{# of edges}} c_e x^e$ instead of numbers for values of $a_n$, $a_{\lambda}$, $a'_{\lambda}$, etc.
A: I do not have a formula, but here is a sample SageMath code that generates all  st-dags on $n$ vertices:
from sage.combinat.gray_codes import product as gc_product

def stDAGs(n):
    if n==1:
        yield DiGraph([[0],[]])
        return
    elif n==2:
        yield DiGraph([(0,1)])
        return

    for P in Posets(n-2):
        H = P.hasse_diagram()
        for t in P.maximal_elements():
            H.add_edge(t,n-2)
        for t in P.minimal_elements():
            H.add_edge(n-1,t)

        E = list( set(H.transitive_closure().edges(labels=False)) - set(H.edges(labels=False)) )

        G = H.copy()
        C = G.canonical_label()
        CC = set(C.dig6_string())
        yield C


        for e,d in gc_product([2]*len(E)):
            if d>0:
                G.add_edge(E[e])
            else:
                G.delete_edge(E[e])
            C = G.canonical_label()
            dig6 = C.dig6_string()
            if dig6 not in CC:
                CC.add(dig6)
                yield C

Then the number of such graphs with $n$ vertices can be obtained as
def f(n):
    return sum(1 for d in stDAGs(n))

which for $n=1,2,\dots,8$ gives
1, 1, 2, 10, 98, 1960, 80176, 6686760

These counts do not appear in the OEIS - so it's likely that little is known about them. I've added them as sequence A345258.
The above code can be easily adjusted to take into account the number of edges in each graph.
