¿Cuántos vértices hay en cada nivel en este árbol?

Question

Supongamos que tenemos un árbol como en la imagen de abajo ( tenga en cuenta que sólo una parte del árbol que está en la foto ), es decir, cada vez el número de aristas que viene desde el vértice está aumentando por 1 (de izquierda a derecha).

Nos deja denotar $A(n)$ como un número de vértices en el nivel $n$. Por ejemplo, la primera $A(n)$ $$A(0) = 1,\, A(1) = 1,\, A(2) = 2,\, A(3) = 7,\, A(4) =\ldots$$ La pregunta es

encontrar la forma cerrada para $A(n)$.

Answer 1

Podemos encontrar una función de recursión para$A(n)$. Dejar $B(n)= \sum_{i=0}^{n-1} A(i)$. Los números en el nivel$n$ son los números de$B(n) + 1, \ldots, B(n) + A(n)$. Por lo tanto, la suma de estos números es el número de vértices en el nivel$n+1$, que es $$\begin{split}\sum_{j=B(n)+1}^{B(n)+A(n)}j &=\sum_{j=1}^{B(n)+A(n)} j - \sum_{j=1}^{B(n)} j\\ &=\frac{(B(n)+A(n))(B(n)+A(n)+1)}{2}-\frac{B(n)(B(n)+1)}{2}\\ &= \frac{A(n)^2 + 2A(n)B(n)+A(n)}{2}\end {split}$$ De ahí$2A(n+1)=A(n)^2 + 2A(n)\left(\sum_{i=0}^{n-1}A(i)\right) + A(n)$.

Answer 2

No es una respuesta.

---

Tengo una relación recurrente para$A(n)$ también. Pero difiere ligeramente de @ Simon's. Aquí cómo lo hice.

---

Es fácil mostrar que $$A(n) = A(n-1)X_n + \frac{A(n-1)(A(n-1)+1)}{2},$ $ donde$X_n$ es un número de vértices generados por el último vértice (de derecha a izquierda) en el nivel$n-1$. A continuación, se puede mostrar que$$ X_n = \sum_0^{n-2}A(k).
Así que parece que mi respuesta es dos veces menos que la de @ Simon.