Relación de recurrencia en $a_n$

Question

Dada la relación de recurrencia $$ 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 $$ con $a_0=1$ He tratado de evaluar $a_3$ y lo tengo igual a $25$ , pero el libro lo muestra igual a $19$ .

Mi esfuerzo: $a_1=1, a_2=3$ da

$$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$$

Este es el texto del libro ( Manual de Combinatoria Enumerativa de Miklos Bona )

Un problema muy clásico es el de enumerar digrafos acíclicos; son claramente sin bucles y dados dos vértices distintos $u$ y $v$ sólo uno de los dos arcos $u v$ y $v u$ puede estar presente. Dejemos que $a_{n}$ sea el número de digrafos acíclicos en $n$ vértices etiquetados, y que $a_{n, m}$ sea el número de los que tienen $m$ arcos. Existe una sencilla recurrencia para calcular estos números, encontrada independientemente en y redescubierta varias veces. El número de dígrafos acíclicos tales que $k$ los vértices dados son fuentes es igual a $2^{k(n-k)} a_{n-k}$ ya que el resto de $n-k$ Los vértices inducen un dígrafo acíclico y cada arco desde los orígenes hasta el complemento está permitido. Dado que un dígrafo acíclico siempre tiene al menos un origen, la inclusión-exclusión da $$ 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 $$ Esto da la secuencia $$ 1,1,3,19,219,4231,130023, \ldots $$

Answer 1

Por lo que veo, su libro tiene un resultado erróneo. Usando su relación de recurrencia, obtengo

$$\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}$$

y luego

$$\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}$$

y luego obtengo el mismo valor de $a_3$ como tú.

También parece que Wikipedia coincide con el número 25, no con el número 19. Lo mismo ocurre con el OEIS .

Answer 2

El Manual de Bona dice en la página 427

Esto da la secuencia $$1,1,3,19,219,4231,130023,\dots,$$ que es la secuencia A001035.

El Secuencia OEIS A001035 La entrada establece que es el número de acíclicos etiquetados transitivo dígrafos y el Manual de Bona es la segunda referencia. Es revelador que haya no fórmula o recurrencia para la secuencia en la entrada. Como han señalado varias personas, la recurrencia es para Secuencia OEIS A003024 "Número de digrafos acíclicos con n nodos etiquetados". La primera fórmula es esencialmente la recurrencia dada. La diferencia entre las dos secuencias es el requisito de ser transitivo. De alguna manera, Bona se confundió con eso.

Al comparar las secuencias se obtiene la tabla $$ \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}$$ donde la segunda secuencia es para transitivo dígrafos. Este requisito reduce el recuento.