Recurrence relation on $a_n$

Question

Given the recurrence relation$$ a_{n}=\sum_{t=0}^{n-1}\left(\begin{array}{l} n \\ t \end{array}\right)(-1)^{n-t-1} 2^{t(n-t)} a_{t}, \quad a_{0}=1 $$ with $a_0=1$, I tried to evaluate $a_3$, and I got it equal to $25$, but the book shows it equal to $19$.

My effort: $a_1=1, a_2=3$ gives

$$a_3=\binom{3}{0}\times (-1)^2\times 2^0\times 1+\binom{3}{1}\times (-1)^1\times 2^2\times 1+\binom{3}{2}\times (-1)^0\times 2^2\times 3\\=1-12+36=25$$

Here is the text from the book (Handbook of Enumerative Combinatorics by Miklos Bona)

A very classical problem is to enumerate acyclic digraphs; they are clearly loopless and given two distinct vertices $u$ and $v$, only one of the two arcs $u v$ and $v u$ can be present. Let $a_{n}$ be the number of acyclic digraphs on $n$ labeled vertices, and let $a_{n, m}$ be the number of those having $m$ arcs. There is a simple recurrence for computing these numbers, found independently in and rediscovered several times. The number of acyclic digraphs such that $k$ given vertices are sources is equal to $2^{k(n-k)} a_{n-k}$ since the remaining $n-k$ vertices induce an acyclic digraph and every arc from the sources to the complement is allowed. Given that an acyclic digraph always has at least one source, inclusion-exclusion gives $$ a_{n}=\sum_{t=0}^{n-1}\left(\begin{array}{l} n \\ t \end{array}\right)(-1)^{n-t-1} 2^{t(n-t)} a_{t}, \quad a_{0}=1 $$ This gives the sequence $$ 1,1,3,19,219,4231,130023, \ldots $$

Answer 1

From what I can tell, your book has the wrong result. Using your recurrence relation, I get

$$\begin{align}a_{1}=\sum_{t=0}^{0}{1 \choose t}(-1)^{1-t-1} 2^{t(1-t)} a_{t} = {1\choose 0}\cdot (-1)^0\cdot 2^0\cdot a_0=a_0=1\end{align}$$

and then

$$\begin{align}a_2 = \sum_{t=0}^{1}{2 \choose t}(-1)^{2-t-1} 2^{t(2-t)} a_{t} &= {2 \choose 0}(-1)^{2-0-1} 2^{0(2-0)} a_{0} + {2 \choose 1}(-1)^{2-1-1} 2^{1(2-1)} a_{1}\\&=1\cdot (-1)\cdot 1\cdot a_0 + 2\cdot 1\cdot 2 \cdot a_1 = -a_0+4a_1=3\end{align}$$

and then I get the same value of $a_3$ as you.

It also seems like Wikipedia agrees with the number 25, not the number 19. So does the OEIS.

Answer 2

The Bona Handbook states on page 427

This gives the sequence $$1,1,3,19,219,4231,130023,\dots,$$ which is sequence A001035.

The OEIS sequence A001035 entry states that this is the number of labeled acyclic transitive digraphs and the Bona Handbook is the second reference. Tellingly, there is no formula or recurrence for the sequence in the entry. As several people noted, the recurrence is for OEIS sequence A003024 "Number of acyclic digraphs with n labeled nodes". The first formula is essentially the recurrence given. The difference between the two sequences is the requirement of being transitive. Somehow Bona got confused about that.

Comparing the sequences gives the table $$ \begin{matrix} n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\ a_n & 1 & 1 & 3 & 25 & 543 & 29281 & 3781503 & 1138779265\\ b_n & 1 & 1 & 3 & 19 & 215 & 4231 & 130023 & 6129859 \end{matrix}$$ where the second sequence is for transitive digraphs. This requirement reduces the count.