8.6: Funciones generadoras exponenciales
- Page ID
- 118328
Si hubiéramos querido ser absolutamente precisos antes en el capítulo, nos habríamos referido a las funciones generadoras que estudiamos como funciones generadoras ordinarias o incluso funciones generadoras de series de potencia ordinarias. Esto se debe a que existen otros tipos de funciones generadoras, basadas en otros tipos de series de potencia. En esta sección, presentamos brevemente otro tipo de función generadora, la función generadora exponencial. Mientras que una función generadora ordinaria tiene la forma\(\sum_n a_nx^n\), una función generadora exponencial se basa en la serie de potencia para la función exponencial\(e^x\). Así, la función generadora exponencial para la secuencia\(\{a_n:n \geq 0\}\) es\(\sum_n a_nx^n/n!\). En esta sección, veremos algunas formas en las que podemos usar funciones generadoras exponenciales para resolver problemas que no podríamos abordar con funciones generadoras ordinarias. Sin embargo, solo rayaremos la superficie del potencial de este tipo de función generadora. Comenzamos con la función generadora exponencial más fundamental, en analogía con la función generadora ordinaria\(1/(1−x)\) del Ejemplo 8.1.
Considere la secuencia constante\(1,1,1,1,….\) Entonces la función generadora exponencial para esta secuencia es
\(E(x) = \displaystyle \sum_{n=0}^{\infty} \dfrac{x^n}{n!}\).
A partir del cálculo, probablemente recuerdes que esta es la serie de potencias para la función exponencial\(e^x\), razón por la cual llamamos a este tipo de función generadora una función generadora exponencial. A partir de este ejemplo, podemos reconocer rápidamente que la función generadora exponencial para el número de cadenas binarias de longitud\(n\) es\(e^{2x}\) desde
\(e^{2x} = \displaystyle \sum_{n=0}^{\infty} \dfrac{(2x)^n}{n!} = \sum_{n=0}^{\infty} 2^n \dfrac{x^n}{n!}\).
En nuestro estudio de las funciones generadoras ordinarias anteriormente en este capítulo, consideramos ejemplos donde la cantidad (número de manzanas, etc.) importaba pero el orden no. Una de las áreas donde las funciones de generación exponencial son preferibles a las funciones generadoras ordinarias es en aplicaciones donde el orden importa, como contar cadenas. Por ejemplo, aunque las cadenas de bits 10001 y 011000 contienen ambas tres ceros y dos unos, no son las mismas cadenas. Por otro lado, dos canastas de frutas que contienen dos manzanas y tres naranjas se considerarían equivalentes, independientemente de cómo organizara la fruta. Consideramos ahora un par de ejemplos para ilustrar esta técnica.
Supongamos que deseamos encontrar el número de cadenas ternarias en las que el número de 0s es par. (No hay restricciones en el número de 1s y 2s.) Al igual que con las funciones generadoras ordinarias, determinamos una función generadora para cada uno de los dígitos y los multiplicamos. Para 1s y 2s, ya que podemos tener cualquier número de cada uno de ellos, introducimos un factor de\(e^x\) para cada uno. Para un número par de 0, necesitamos
\(1 + \dfrac{x^2}{2!} + \dfrac{x^4}{4!} + \dfrac{x^6}{6!} + \cdot \cdot \cdot = \displaystyle \sum_{n=0}^{\infty} \dfrac{x^{2n}}{(2n)!}\).
A diferencia de las funciones generadoras ordinarias, no podemos representar esta serie en una forma más compacta simplemente sustituyendo una función de\(x\) en la serie por\(e^y\). Sin embargo, con una pequeña cantidad de astucia, somos capaces de lograr el resultado deseado. Para ello, primero nota que
\(e^{-x} = 1 - x + \dfrac{x^2}{2!} - \dfrac{x^3}{3!} + \cdot \cdot \cdot = \displaystyle \sum_{n=0}^{\infty} \dfrac{(-1)^nx^n}{n!}\).
Así, cuando añadimos la serie para\(e^{−x}\) a la serie para\(e^x\) todos los términos con poderes impares de ¡\(x\)cancelará! Así encontramos
\(e^x + e^{-x} = 2+2 \dfrac{x^2}{2!} + 2 \dfrac{x^4}{4!} + \cdot \cdot \cdot\),
que es exactamente el doble de lo que necesitamos. Por lo tanto, el factor que introducimos para 0s es\((e^x+e^{-x})/2\).
Ahora tenemos una función generadora exponencial de
\(\dfrac{e^x+e^{-x}}{2}e^xe^x = \dfrac{e^{3x}+e^x}{2} = \dfrac{1}{2}(\displaystyle \sum_{n=0}^{\infty} \dfrac{3^nx^n}{n!} + \sum_{n=0}^{\infty} \dfrac{x^n}{n!})\).
Para encontrar el número de cadenas ternarias en las que el número de 0s es par, por lo tanto, necesitamos mirar el coeficiente encendido\(x^n/n!\) en la expansión de la serie. Al hacer esto, encontramos que el número de cadenas ternarias con un número par de 0s es\((3^n+1)/2\).
También podemos usar funciones de generación exponencial cuando hay límites en el número de veces que aparece un símbolo, como en el siguiente ejemplo.
¿Cuántas cadenas ternarias de longitud\(n\) tienen al menos un 0 y al menos un 1?
- Solución
-
Para asegurar que un símbolo aparezca al menos una vez, necesitamos la siguiente función generadora exponencial
\(x+\dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \cdot \cdot \cdot = \displaystyle \sum_{n=1}^{\infty} \dfrac{x^n}{n!}\).
Deberías notar que esta es casi la serie para\(e^x\), excepto que le falta el primer término. Por lo tanto,\(\sum_{n=1}^{\infty} x^n/n! = e^x-1\). Usando esto, ahora tenemos
\((e^x-1)(e^x-1)e^x = e^{3x}-2e^{2x}+e^x\)
como la función generadora exponencial para este problema. Al encontrar la expansión de la serie, tenemos
\(\displaystyle \sum_{n=0}^{\infty} \dfrac{3^nx^n}{n!} - 2 \sum_{n=0}^{\infty} \dfrac{2^nx^n}{n!} + \sum_{n=0}^{\infty} \dfrac{x^n}{n!}\).
Ahora podemos responder a la pregunta leyendo el coeficiente encendido\(x^n/n!\), que es\(3^n - 2 \cdot 2^n +1\).
Antes de proceder a un ejemplo adicional, tomemos un minuto para ver otra forma de responder a la pregunta del ejemplo anterior. Para contar el número de cadenas ternarias de longitud n con al menos un 0 y al menos un 1, podemos contar todas las cadenas ternarias de longitud n y usar el principio de inclusión-exclusión para eliminar las cadenas indeseables que carecen de un 0 y/o un 1. Si una cadena ternaria carece de un 0, estamos contando todas las cadenas compuestas por 1s y 2s, así que hay\(2^n\) cadenas. De igual manera por carecer de un 1. Sin embargo, si restamos\(2 \cdot 2^n\), entonces hemos restado las cadenas a las que les falta tanto un 0 como un 1 dos veces. Una cadena ternaria que no tiene 0s y no 1s consiste solo en 2s. Hay una sola cadena ternaria de longitud que\(n\) satisface este criterio. Así, obtenemos\(3^n−2 \cdot 2^n+1\) de otra manera.
Alice necesita establecer un código de acceso de ocho dígitos para su teléfono móvil. Las restricciones sobre el código de acceso son un poco peculiares. Específicamente, debe contener un número par de 0s, al menos un 1, y como máximo tres 2s. Bob señala que aunque las restricciones son inusuales, no hacen mucho para reducir el número de posibles códigos de acceso del número total de cadenas de\(10^8\) ocho dígitos. Carlos no está convencido de que ese sea el caso, por lo que trabaja una función generadora exponencial de la siguiente manera. Para los siete dígitos sobre los que no hay restricciones,\(e^{7x}\) se introduce un factor de. Para dar cuenta de un número par de 0s, usa\((e^x+e^{−x})/2\). Para al menos un 1,\(e^x−1\) se requiere un factor de. Por último,\(1+x+x^2/2!+x^3/3!\) da cuenta de la restricción de como máximo tres 2s. Por lo tanto, la función de generación exponencial para el número de\(n\) códigos de acceso de -dígito es
\(e^{7x} \dfrac{e^x + e^{-x}}{2}(e^x - 1) (1+x+\dfrac{x^2}{2!}+ \dfrac{x^3}{3!})\).
Dave ve este lío escrito en la pizarra y gime. Él calcula que estarán ahí todo el día multiplicándose y cometiendo errores de álgebra al tratar de encontrar el coeficiente deseado. Alice señala que en realidad no necesitan encontrar el coeficiente encendido\(x^n/n!\) para todos\(n\). En cambio, sugiere que usen SaeMath para simplemente encontrar el coeficiente encendido\(x^8/8!\).
//código
Ya que\(8!=40320\), esto les dice que hay\(33847837\) códigos de acceso válidos para el teléfono móvil. Un cálculo rápido muestra que Bob estaba totalmente desbasado al afirmar que no hubo una reducción significativa en el número de cadenas posibles para usar como código de acceso. ¡El número total de códigos de acceso válidos es solo 33.85% del número total de cadenas de ocho dígitos!
Las funciones de generación exponencial son útiles en muchas otras situaciones más allá de enumerar cadenas. Por ejemplo, se pueden usar para contar el número de gráficos n-vértices, conectados, etiquetados. Sin embargo, hacerlo está más allá del alcance de este libro. Si estás interesado en aprender mucho más sobre la generación de funciones, el libro Generarfuncionología de Herbert S. Wilf está disponible en línea en http://www.math.upenn.edu/~wilf/DownldGF.html.