Show that the number of dags with n vertices and indegree

Question

Problem

Recall that the Θ(f(n)) denotes both an asymptotic lower bound and an asymptotic upper bound (up to a constant factor).

a. Show that the number of DAGs with n vertices is 2^Θ(n²) .

b. Show that the number of DAGs with n vertices and indegree bounded by d is 2^{Θ(dn log n)}.

c. Show that the number of DAGs with n vertices and indegree bounded by d that are consistent with a given order is 2^{Θ(dn log n)}.