Recordemos que los números de Bell cumplen una relación de recurrencia muy interesante:\[B_n=\sum_{k=0}^{n-1}B_k\binom{n-1}{k}\]
Ejercicio: Utilizando la fórmula anterior, construir un algoritmo en maxima que nos calcule cualquier número de Bell.
Sin embargo, resulta más sencillo calcularlos con el llamado triángulo de Bell.
- Comience con el número uno. Pon esto en una fila por sí mismo. \({\displaystyle x_{0,1}=1}\)
- Comience una nueva fila con el elemento más a la derecha de la fila anterior como el número más a la izquierda \(({\displaystyle x_{i,1}\leftarrow x_{i-1,r}}\) donde \(r\) es el último elemento de (i-1)-fila).
- Determine los números que no están en la columna izquierda tomando la suma del número a la izquierda y el número sobre el número a la izquierda, es decir, el número diagonalmente arriba y a la izquierda del número que estamos calculando(\({\displaystyle (x_{i,j}\leftarrow x_{i,j-1}+x_{i-1,j-1}}\))
- Repita el paso tres hasta que haya una nueva fila con un número más que la fila anterior (haga el paso 3 hasta \({\displaystyle j=r+1}\))
- El número en el lado izquierdo de una fila dada es el número de Bell para esa fila. \({\displaystyle B_{i}\leftarrow x_{i,1}}\)
Estas son las primeras cinco filas del triángulo construido por estas reglas:
\[\begin{array}{rrrrr} 1&&&& \\ 1&2&&& \\ 2&3&5&& \\ 5&7&10&15& \\ 15&20&27&37&52 \end{array}\]
Ejercicio: Utilizando el triángulo de Bell, construir un algoritmo con máxima que nos devuelva \(B_n\).
Sabemos que los números de Stirling de segunda especie siguen la relación de recurrencia
\[ \left\{{\begin{matrix}n\\k\end{matrix}}\right\}=\left\{{\begin{matrix}n-1\\k-1\end{matrix}}\right\}+k\left\{{\begin{matrix}n-1\\k\end{matrix}}\right\}\]
con \[\left\{{\begin{matrix}0\\0\end{matrix}}\right\}=1,\quad \left\{{\begin{matrix}n\\0\end{matrix}}\right\}=0,\quad \left\{{\begin{matrix}n\\1\end{matrix}}\right\}=\left\{{\begin{matrix}n\\n\end{matrix}}\right\}=1,\quad {\mbox{ y }}\quad \left\{{\begin{matrix}n\\k\end{matrix}}\right\}=0,\ \forall k>n.\]
| n \ k | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 1 | |||||
| 1 | 0 | 1 | ||||
| 2 | 0 | 1 | 1 | |||
| 3 | 0 | 1 | 3 | 1 | ||
| 4 | 0 | 1 | 7 | 6 | 1 | |
| 5 | 0 | 1 | 15 | 25 | 10 | 1 |
Ejercicio: Utilizando la recurrencia anterior, construir un algoritmo con máxima que nos devuelva \[ \left\{{\begin{matrix}n\\k\end{matrix}}\right\}\]
El pasado día tratamos los árboles, entre ellos los árboles enraizados. Por ejemplo, en la imagen vemos todos los posibles árboles enraizados ordenados que tienen cuatro aristas y dos hojas.
By Řiťopič – Own work, CC BY-SA 4.0, Link
Los árboles enraizados ordenados imponen un orden lineal (izquierda a derecha) en los hijos de cada nodo, haciendo que las permutaciones de hermanos generen árboles distintos. Un árbol enraizado ordenado parte de un árbol enraizado estándar, pero los subárboles de cada nodo se ordenan secuencialmente, como «primer hijo», «segundo hijo», etc. Esto permite referir posiciones específicas, similar a un árbol binario donde izquierda < raíz < derecha.
Proposición: Sea \({\displaystyle \mathbf{N} (n,k),n\in \mathbb {N} ^{+},1\leq k\leq n}\) el número de árboles enraizados ordenados con \(n\) lados y \(k\) hojas, entonces
\[{\displaystyle \mathbf{N} (n,k)={\frac {1}{n}}{n \choose k}{n \choose k-1}}\]
La siguiente tabla está construida con la fórmula anterior.
| n \ k | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 1 | 1 | |||||||
| 2 | 1 | 1 | ||||||
| 3 | 1 | 3 | 1 | |||||
| 4 | 1 | 6 | 6 | 1 | ||||
| 5 | 1 | 10 | 20 | 10 | 1 | |||
| 6 | 1 | 15 | 50 | 50 | 15 | 1 | ||
| 7 | 1 | 21 | 105 | 175 | 105 | 21 | 1 | |
| 8 | 1 | 28 | 196 | 490 | 490 | 196 | 28 | 1 |
Proposición: Si consideramos $\mathbf{N}(n, 1) = 1$ y $\mathbf{N}(n, n) = 1$, entonces
$$ \mathbf{N}(n, k) = \mathbf{N}(n, k-1) \cdot \frac{(n-k+1)(n-k+2)}{k(k-1)} $$
Ejercicio: Utilizando el resultado anterior, construir un algoritmo con máxima que nos devuelva \(\mathbf{N}(n,k)\).