En la entrada anterior presentábamos como un artificio sustituir los elementos de un producto cartesiano condicionado de conjuntos numéricos por polinomios en una indeterminada con exponentes idénticos a los números a combinar.
Hoy lo convertiremos en un desarrollo teórico.
Función generatriz de un conjunto numérico
Dado un conjunto ordenado de números reales o complejos (aquí usaremos casi exclusivamente los enteros positivos) {a0, a1, a2, a3,…an} llamaremos función generatriz (ordinaria) o generadora del mismo al polinomio de la forma
Si el conjunto tiene infinitos términos sustituiremos el polinomio por una serie de potencias, pero en este caso la igualdad
sólo tendrá sentido si dicha serie posee un radio de convergencia no nulo y la función está definida dentro de ese radio. No obstante, aquí no trataremos la convergencia, sino las relaciones entre coeficientes. Si no converge, P(x) no será una función, pero las técnicas siguen valiendo.
Casos sencillos
El caso más sencillo de función generatriz es la que corresponde al conjunto {1,1,1,1,…1}
Si este es finito con n elementos, sabemos que su función generatriz se puede obtener mediante la fórmula de la suma de una progresión geométrica
Ya usamos esta fórmula en la entrada anterior
Si el conjunto es infinito {1,1,1,1,…}también es sencillo verificar que
Aquí nos encontramos con la potencia que tiene este método. Si derivamos miembro a miembro (omitimos detalles y también la cuestión de la convergencia) nos encontraremos con que
Por tanto esta es la función generatriz del conjunto {1,2,3,4,….}
La fórmula del binomio de Newton nos proporciona otro ejemplo de función generatriz. Los números combinatorios para un n dado tienen por función generatriz (1+x)n ya que
Podíamos seguir dando ejemplos hasta llenar páginas enteras, pero destacaremos especialmente dos técnicas
Manipulación algebraica
Con las técnicas algebraicas y sin plantearnos ahora el problema de la convergencia podemos encontrar la función generatriz de muchos conjuntos de coeficientes.
Por ejemplo, es fácil encontrarla para los números de Fibonacci F0, F1, F2, F3, F4…, de los que suponemos se conocen sus valores y propiedades. Observa estas manipulaciones:
F(x)=F0+F1x+F2x2+ F3x3+ F4x4+…=
F0+F1x+(F0+F1)x2+(F1+F2)x3+(F2+F3)x4+… =
F0+F1x+(F0 x2+ F1 x3+ F2 x4+…) + (F1 x2+ F2 x3+ F3 x4+…)
Pero en los paréntesis se está reconstruyendo F(x) de alguna forma, por lo que podemos escribir (pon tú los detalles)
F(x)= F0+F1x+F(x) x2+(F(x)- F0)x
Despejamos F(x), sustituimos F0 por su valor 0 (a veces se toma 1) y F1 por 1 y ya la tenemos:
Sólo hemos usado técnicas algebraicas sencillas. Más adelante comprobaremos este resultado.
Manipulación analítica
Si consideramos la derivación e integración formales podemos encontrar fácilmente funciones generatrices. Ya hemos considerado un ejemplo de derivación.
De la misma forma podemos usar la integración. Por ejemplo en la geométrica podemos integrar
Nos resultaría entonces
En cualquier manual puedes encontrar muchos ejemplos similares de este tipo de manipulación. No olvides que podemos mezclar las dos técnicas, analítica y algebraica, así como sumar, multiplicar y otras.
Problema inverso
Si la serie que define la función generatriz converge y conocemos esta, encontrar los coeficientes de la serie siempre es posible por la fórmula de McLaurin
Es un camino muy pesado, pero seguro. Sin embargo el problema contrario de dar los coeficientes y encontrar la expresión de P(x) quizás no lo puedas resolver. Es el clásico problema de la suma de series.
Con la ayuda de un ordenador se puede simplificar el proceso. Damos un ejemplo:
Antes vimos que los números de Fibonacci tenían como función generatriz (si se toma F0=0. A veces se toma F0=1 y entonces tiene una expresión ligeramente distinta)
Si tuviéramos posibilidad de desarrollar por McLaurin en algún lenguaje o programa, nos ahorraríamos mucho trabajo. Nosotros lo hemos hecho con el lenguaje PARI. Se entiende fácilmente aunque no se haya usado nunca:
{write("final.txt",taylor(x/(1-x-x^2), x,12))}
Ordenamos que escriba en el archivo “final.txt” 12 términos del desarrollo de Taylor (es en x=0) de la función dada. El resultado es:
0+x + x^2 + 2*x^3 + 3*x^4 + 5*x^5 + 8*x^6 + 13*x^7 + 21*x^8 + 34*x^9 + 55*x^10 + 89*x^11 + O(x^12)
Como vemos, los coeficientes son los números de Fibonacci. Si quisiéramos hacer F0=1 nos daría otro resultado, pues la función generatriz seria 1/(1-x-x2) (intenta demostrarlo)
Programaríamos en PARI esta variante:
{write("final.txt",taylor(1/(1-x-x^2), x,12))}
Obtendríamos la sucesión comenzando en 1:
1 + x + 2*x^2 + 3*x^3 + 5*x^4 + 8*x^5 + 13*x^6 + 21*x^7 + 34*x^8 + 55*x^9 + 89*x^10 + 144*x^11 + O(x^12)
Lo podemos intentar con el ejemplo de la entrada anterior, el de las bolas de colores, cuya función generatriz sin desarrollar era
Deberíamos escribir en PARI
{write("final.txt",taylor(x^5*(x^4-1)^2*(x^5-1)/(x-1)^3, x,20))}
Obtendríamos
x^5 + 3*x^6 + 6*x^7 + 10*x^8 + 13*x^9 + 14*x^10 + 13*x^11 + 10*x^12 + 6*x^13 + 3*x^14 + x^15 + O(x^20)
Identificamos los resultados de la entrada anterior: Con grado 9 el coeficiente es el esperado, 13. Para el grado 14 sólo 3 y para el grado 7 los 6 que ya se obtuvieron.
En otra entrada posterior veremos las funciones generatrices de combinaciones, variaciones y demás. Hoy seguiremos con ejemplos:
¿De cuántas formas se puede descomponer el número 28 como suma de primos distintos?
Los primos inferiores a 28 son 2, 3, 5, 7, 11, 13, 17, 19, 23. Cada uno de ellos o está en la suma una vez o no está. Entonces podemos usar términos del tipo (1+x^7) o (1+x^11) para combinarlos en la función generatriz:
F(x)= (1+x2) (1+x3) (1+x5) (1+x7) (1+x11) (1+x13) (1+x17) (1+x19) (1+x23)
Desarrollamos con wxMmaxima y nos da (hemos recortado la imagen):
Vemos que para el exponente 28 el coeficiente es 6, luego existen 6 formas distintas de expresar 28 como suma de primos distintos
Lo comprobamos con nuestra herramienta PARTLISTA (http://hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#reprenum)
Con ella vemos las seis sumas: 28=11+17=5+23=3+5+7+13=2+7+19=2+3+23=2+3+5+7+11
Con la función generatriz hemos conseguido también otros muchos coeficientes, pero cuidado con la lista de primos 2, 3, 5, 7, 11, 13, 17, 19, 23. Este desarrollo sólo valdría hasta el 28. Para números mayores deberíamos añadir (1+x^29)(1+x^31)…
Luego con la función generatriz podemos resolver varios problemas a la vez.
Estos desarrollos algebraicos son pesados incluso con ayuda de los CAS. Sería bueno elegir un solo coeficiente en ellos. El lenguaje PARI que estamos usando últimamente (es gratuito aunque de gestión poco amigable) posee la función POLCOEFF(P(x),E) en la que P(x) es un polinomio y E un exponente dado, y nos devuelve el coeficiente de ese polinomio correspondiente al grado E. Nuestro problema del 28 se calcularía así:
print(polcoeff((x^2+1)*(x^3+1)*(x^5+1)*(x^7+1)*(x^11+1)*(x^13+1)*(x^17+1)*(x^19+1)*(x^23+1),28))
Daría un resultado de 6. Si cambiamos 28 por un número inferior obtendremos más resultados. Para números superiores deberíamos incrementar los primos.
No hay comentarios:
Publicar un comentario