Funciones generadoras · Definición

Función generadora exponencial

combinatoria enumerativafunciones generadoras

Las funciones generadoras ordinarias funcionan bien para selecciones sin orden, pero fallan cuando los elementos están etiquetados y se reordenan. La versión exponencial divide cada término entre el factorial para absorber esas permutaciones.

Definición

La función generadora exponencial de una sucesión \(a_0, a_1, \ldots\) es la serie formal \(A(x)\) cuyo coeficiente de \(x^n\) es \(a_n/n!\).

\[A(x)=\sum_{n\ge 0}\frac{a_n}{n!}x^n\]

Si \(A(x)\) y \(B(x)\) son las funciones generadoras exponenciales de \(a_n\) y \(b_n\), su producto de Cauchy \(A(x)B(x)\) tiene coeficientes \(\sum_k \binom{n}{k}a_k b_{n-k}\) al multiplicar por \(n!\). Esta convolución binomial es la razón principal de su utilidad. Además, la serie \(e^x=\sum_{n\ge 0} x^n/n!\) es la función generadora de la sucesión constante igual a 1.

Considere las particiones de un conjunto de \(n\) elementos en subconjuntos no vacíos sin orden, es decir, los números de Bell \(B_n\). Usando que \(\exp(e^x-1)\) codifica estas particiones, se obtiene \(B_3=5\) al extraer el coeficiente de \(x^3\) multiplicado por \(3!\). El ejemplo muestra cómo la exponencial genera la estructura de conjuntos sin contar explícitamente cada partición.

Un error típico es tratar la función generadora exponencial como si los coeficientes fueran simplemente \(a_n\), olvidando dividir entre \(n!\). Con ello se obtienen sumas incorrectas en los productos. Conviene recordar siempre que el denominador factorial es parte de la definición.

Para pensar

¿Por qué dividir entre \(n!\) hace que el producto de dos series codifique subconjuntos etiquetados?

Porque el coeficiente de \(x^n/n!\) del producto es \(\sum_k \binom{n}{k}a_k b_{n-k}\), que reparte los n elementos etiquetados entre dos estructuras.

Ejercicios 10

  1. ¿Cuál es la función generadora exponencial de la sucesión constante \(a_n=1\)?
  2. Si \(a_n=n!\), ¿cuánto vale la función generadora exponencial?
  3. ¿Qué coeficiente de \(x^n\) define la función generadora exponencial de \(a_n\)?
  4. ¿Cuál es la serie de \(e^x\) expresada como suma?
  5. ¿Qué sucesión tiene función generadora exponencial \(e^{2x}\)?
  6. Calcula el coeficiente \(a_3\) de la sucesión cuya función generadora exponencial es \(\frac{1}{1-x}\).
  7. Si \(A(x)=e^{3x}\), ¿cuál es el coeficiente de \(x^2\) en \(A(x)\)?
  8. ¿Qué sucesión \(a_n\) tiene función generadora exponencial \(x e^x\)?
  9. Sea \(A(x)=e^{2x}\) y \(B(x)=e^{3x}\). ¿Cuál es el valor de \(c_4\), donde \(C(x)=A(x)B(x)\) y \(c_n\) es la sucesión asociada a \(C\)?
  10. Sea \(A(x)=\exp(e^x-1)\), que cuenta particiones de conjuntos. ¿Cuál es el número de Bell \(B_4\)?

Referencias

  • Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2012.
  • Herbert S. Wilf, generatingfunctionology, 3rd edition, A K Peters, 2006.