9.3: Números de campana y funciones de generación exponencial

A veces una relación de recurrencia involucra factoriales, o coeficientes binomiales. Cuando esto sucede, se vuelve difícil si no imposible usar funciones generadoras ordinarias para encontrar una fórmula explícita para el enésimo término de la secuencia. En algunos casos, un tipo diferente de función generadora, la función generadora exponencial, puede tener éxito donde falla una función generadora ordinaria.

Definición: Función generadora exponencial

La función de generación exponencial para la secuencia\(a_0, a_1, . . .,\) es

\[\sum_{i=0}^{\infty} \dfrac{a_ix^i}{i!} \]

Obviamente, la diferencia entre ésta y una función generadora ordinaria proviene de la expresión factorial en el denominador. La cancelación entre esto y expresiones en el numerador puede conducir a expresiones compactas más agradables

Ejemplo\(\PageIndex{1}\)

La función de generación exponencial para la secuencia\(1, 1, 1, . . .\) es

\(\dfrac{1}{0!} + \dfrac{x}{1!} + \dfrac{x^2}{2!} + ... \)

Esta es la expansión de la serie Taylor para\(e^x\). Así,\(e^x\) es la función generadora exponencial para\(1, 1, 1, . . .\).

No vamos a utilizar funciones de generación exponencial en esta clase; solo estamos introduciendo el tema. Pasaremos por un ejemplo de una secuencia para la que son útiles las funciones generadoras exponenciales: los números de Bell

Definición: Número de campana

El número Bell\(B_n\) es el número de particiones de\(\{1, . . . , n\}\) en subconjunto.

Veamos los primeros números de Bell

Ejemplo\(\PageIndex{2}\)

Solo hay una manera de particionar\(\{1\}\) en subconjuntos:\(\{1\}\), entonces\(B_1 = 1\).

Hay dos formas de particionar\(\{1, 2\}\) en subconjuntos:\(\{1\}\),\(\{2\}\), o\(\{1, 2\}\), así\(B_2 = 2\).

Hay cinco formas de particionar\(\{1, 2, 3\}\) en subconjuntos:\(\{1\}\),,\(\{2\}\)\(\{3\}\), o,\(\{1, 2\}\), o\(\{3\}\), o\(\{1, 3\}\)\(\{2\}\), o\(\{2, 3\}\), o\(\{1\}\), o\( \{1, 2, 3\}\), así\(B_3 = 5\).

Probablemente después de ver los ejemplos anteriores, no desea calcular números de Bell más grandes directamente. Sin embargo, podemos derivar una relación recursiva para estos números. Para que esta relación funcione correctamente, vamos a definir\(B_0 = 1\).

Proposición\(\PageIndex{1}\)

Para\(n ≥ 1\), el nésimo número de Bell

\[B_n = \sum_{k=1}^{n} \binom{n-1}{k-1} B_{n-k} \]

Prueba

Usaremos una prueba combinatoria de esta afirmación. Sabemos que Bn es el número de particiones de\(\{1, . . . , n\}\) en subconjuntos.

Para el otro lado de la ecuación, consideremos el subconjunto que contiene el elemento\(n\), y llamemos a la cardinalidad de este subconjunto\(k\). Ya que\(n\) está en este subconjunto\(k ≥ 1\),, y dado que este es un subconjunto de\({1, . . . , n}\), tenemos\(k ≤ n\), así\(1 ≤ k ≤ n\). Hay\(\binom{n−1}{k−1}\) formas de elegir los\(k −1\) elementos restantes de este subconjunto; es decir, para cualquiera\(1 ≤ k ≤ n\), hay\(\binom{n−1}{k−1} \) formas de elegir el subconjunto de\({1, . . . n}\) que contiene el elemento\(n\). Para cada una de estas formas, hay\(n − k\) otros elementos que deben particionarse, y por la definición de los números de Bell, hay\(B_{n−k}\) formas de particionarlos en subconjuntos. (Nuestra definición de\(B_0 = 1\) trata con el caso\(k = n\), asegurando que la\(\binom{n−1}{n−1} = 1\) forma de\(n\) elegir estar en un solo conjunto de todos los\(n\) elementos se cuente una vez y sólo una vez.)

Así, usando las reglas de producto y suma, vemos que

\(B_n = \sum_{k=1}^{n} \binom{n-1}{k-1} B_{n-k} \)

Tratemos de encontrar la función generadora exponencial para los números de Bell. Cuando se trata de funciones de generación exponencial, observe que la derivada de\(\dfrac{x^n}{n!}\) es\(n\dfrac{x^n}{n!} = \dfrac{x^{n−1}}{(n − 1)!}\), por lo que tomar derivadas a menudo resulta en una expresión agradable que nos ayuda a encontrar una buena expresión para los coeficientes. Ya conoces un ejemplo particularmente agradable de esto: la derivada de\(e^x\) is\(e^x\), que nos dice que todos los coeficientes en esa función generadora exponencial son iguales.

Definir

\(B(x) = \sum_{i=0}^{\infty} B_i \dfrac{x^i}{i!} = B_0 + B_1 \dfrac{x}{1!} + B_2 \dfrac{x^2}{2!} +...+ B_n \dfrac{x^n}{n!} \)

Observe que el derivado de esto es

\( \begin{equation} \begin{split} \dfrac{d}{dx} B(x) &= B_1 + B_2 \dfrac{x}{1!} + B_3 \dfrac{x^2}{2!} +...+ B_n \dfrac{x^{n-1}}{(n-1)!} \\ &= \sum_{n=1}^{\infty} B_n \dfrac{x^{n-1}}{(n-1)!} \end{split} \end{equation} \)

Usando nuestra relación recursiva de la Proposición 9.3.1, vemos que esto es

\( \begin{equation} \begin{split} \dfrac{d}{dx} B(x) &= \sum_{n=1}^{\infty} \left[ \sum_{k=1}^{n} \binom{n-1}{k-1} B_{n-k} \right] \dfrac{x^{n-1}}{(n-1)!} \\ &= \sum_{n=1}^{\infty} \left[ \sum_{k=1}^{n} \dfrac{(n − 1)!}{(k − 1)!(n − k)!} B_{n-k} \dfrac{x^{n-1}}{(n-1)!} \right] \\ &= \sum_{n=1}^{\infty} \left[ \sum_{k=1}^{n} \dfrac{1}{(k − 1)!(n − k)!} B_{n-k} x^{n-1} \right] \\ &= \sum_{n=1}^{\infty} \left[ \sum_{k=1}^{n} \dfrac{x^{k-1}}{(k − 1)!} B_{n-k} \dfrac{x^{n-k}}{(n-k)!} \right] \\ \end{split} \end{equation} \)

Observe que para cada valor de\(n\), como\(k\) va de\(1\) a\(n\) los valores\(k − 1\) y\(n − k\) asumir cada par de valores integrales no negativos que se suman a\(n\). Así, como\(n\) va desde\(1\) el infinito, los valores\(k − 1\) y\(n − k\) asumen cada par posible de valores integrales no negativos. Por lo tanto, podemos reescribir esta expresión como

\[ \begin{equation} \begin{split} \dfrac{d}{dx} B(x) &= \sum_{j=0}^{\infty} \left[ \sum_{i=0}^{\infty} \dfrac{x^j}{j!} B_i \dfrac{x^i}{i!} \right] \\ &= \sum_{j=0}^{\infty} \dfrac{x^j}{j!} \left[ \sum_{i=0}^{\infty} B_i \dfrac{x^i}{i!} \right] \\ &= \left[ \sum_{j=0}^{\infty} \dfrac{x^j}{j!} \right] \left[ \sum_{i=0}^{\infty} B_i \dfrac{x^i}{i!} \right] \end{split} \end{equation} \]

Ahora, considere la derivada de\(e^{−(e^x)}B(x)\). Por las reglas del producto y de la cadena, esto es

\(e^{−(e^x)}e^x B(x) - B(x)e^{−(e^x)}e^x = 0 \),

por lo que debe ser el caso que\(e^{−(e^x)}B(x)\) sea constante, digamos\(e^{−(e^x)}B(x) = c\). Entonces\(B(x) = ce^{(e^x)}\).

Desde

\(B(0) = \sum_{n=0}^{\infty} B_n \dfrac{0^n}{n!} = 1 + \sum_{n=1}^{\infty} 0 = 1 \),

(recuerda eso\(0^0 = 0\), o si no te gusta eso, simplemente usa la expansión de\(B(0)\)), vemos que

\(ce^{e^0} = ce^1 = ce = 1\),

así\(c = e^{−1}\). De ahí

\(B(x) = e^{−1} e^{(e^x)} = e^{(e^x−1)} \).

Existen técnicas para extraer coeficientes de expresiones como esta, también, pero no vamos a cubrir estas técnicas en esta clase.

Ejercicio\(\PageIndex{1}\)

1. Encuentra\(B_4\).
2. ¿Cuál es la función generadora exponencial para la secuencia\(a_i = i!\) para cada uno\(i ≥ 0\)? Dar la secuencia tanto en forma expandida como cerrada.
3. ¿Cuál es la función generadora exponencial para la secuencia\(b_i = \dfrac{(i + 1)!}{2}\) para cada uno\(i ≥ 0\)? Dar la secuencia tanto en forma expandida como cerrada.