7
$\begingroup$

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.

$\endgroup$

1 Answer 1

6
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .