# Trying to understand the formula for counting labelled directed acyclic graphs?

Let $$a_n$$ represent the number of directed acyclic graphs on $$n$$ vertices. Then the wikipedia, gives me the following recurrence:

$$a_n = \sum_{k=1}^{n}(-1)^{k-1}\binom{n}{k}2^{k(n-k)}a_{n-k}$$

This formula shouts some sort of inclusion-exclusion, but I don't understand how it is derived. For example: the first term in the formula for $$k=1$$ is $$n2^{n-1}a_{n-1}$$, and I don't understand why is this itself not equal to $$a_n$$, because intuitively give $$a_{n-1}$$,you add one node and assume it to be highest in the order in comparison to all other nodes and now you have $$n$$ ways of doing this due to labelling and $$2^{n-1}$$ of connecting the $$n-1$$ nodes. Where is the over-counting ? If some one could point me to an inclusion-exclusion based proof then that would be great. I am not looking for a generating functions based proof.

The term $$n 2^{n-1} a_{n-1}$$ overcounts acyclic digraphs that have multiple nodes of indegree $$0$$. In such a case, any of the indegree-$$0$$ nodes can be chosen to be the first node.
For concreteness, let $$A_i$$ be the set of acyclic digraphs with nodes $$[n] = \{1,2,\dots,n\}$$ where node $$i$$ has indegree $$0$$. As usual with an inclusion-exclusion problem, let $$A_I = \bigcap_{i \in I} A_i$$, which in this case denotes the set of acyclic digraphs where all nodes in the set $$I$$ have indegree $$0$$.
There is always at least one such node, so $$a_n = |A_1 \cup A_2 \cup \dots \cup A_n|$$. By the inclusion-exclusion principle, we have $$a_n = \sum_{\emptyset \ne I \subseteq [n]} (-1)^{|I|-1} |A_I|.$$ When $$|I|=k$$, we have $$|A_I| = 2^{k(n-k)} a_{n-k}$$: there are $$a_{n-k}$$ ways to choose the arcs in the complement of $$I$$, and $$2^{k(n-k)}$$ ways to choose the arcs between $$I$$ and its complement. Grouping together all terms $$(-1)^{|I|-1} |A_I|$$ where $$|I|=k$$ gives us $$(-1)^{k-1} \binom nk 2^{k(n-k)} a_{n-k}$$, and summing over all $$k$$ results in the formula on Wikipedia.