Tratar con precisión las funciones generadoras

Question

Actualmente estoy trabajando en "Mathematics of Choice" de Iven Niven. En el capítulo sobre funciones generadoras, los ejercicios incluyen problemas como:

¿Cuántas soluciones en enteros no negativos tiene la ecuación $2x+3y+7z+9r=20$ ¿tiene?

Esto, por supuesto, termina siendo lo mismo que encontrar el coeficiente de $x^{20}$ en $(1+x^2+x^4+x^6+\cdots+x^{20})(1+x^3+x^6+\cdots+x^{18})(1+x^7+x^{14})(1+x^9+x^{18})$ . Tal vez sea que soy un gran marica, pero tratar con polinomios tan grandes termina siendo realmente tedioso y propenso a errores.

Me he dado cuenta de que se puede dejar la multiplicación más complicada para el final, ya que es la que requiere menos detalles, y por supuesto no me molesto en llevar la cuenta de las potencias mayores que la que me interesa.

¿Algún consejo para que estos polinomios gigantes sean manejables?

Answer 1

Cuando sólo se puede evaluar razonablemente multiplicando los polinomios, has descrito lo que es prácticamente el único enfoque. Sólo hay que multiplicar, primero los factores más simples, y seguir eliminando todos los coeficientes superiores al que te interesa. En algunos casos esto es todo lo que se puede hacer, por desgracia. (O bien, utilizar un CAS para hacer el álgebra desordenado para usted).

Sin embargo, en ocasiones se puede simplificar la función generadora de forma que se puedan calcular los coeficientes por otros métodos, lo que a veces (aunque no siempre) resulta más fácil.

Tomemos tu caso como ejemplo. Los cuatro polinomios de tu producto se pueden escribir como $\displaystyle \frac{1-x^{22}}{1-x^2}$ , $\displaystyle \frac{1-x^{21}}{1-x^3}$ , $\displaystyle \frac{1-x^{21}}{1-x^7}$ y $\displaystyle \frac{1-x^{27}}{1-x^9}$ . Porque no nos importa lo que ocurra con los coeficientes de arriba $x^{20}$ podemos ignorar las potencias superiores a $x^{20}$ y tomar el producto de las funciones resultantes. Es decir, tu problema es encontrar el coeficiente de $x^{20}$ en $$g(x) = \frac{1}{(1-x^2)(1-x^3)(1-x^7)(1-x^9)}.$$

Se podría entonces utilizar fracciones parciales para descomponer el producto en la suma de funciones para las que ya se conoce una fórmula para la $n$ -ésimo coeficiente; así se obtiene la fórmula de Binet para los números de Fibonacci a partir de la función generadora $\displaystyle f(x) = \frac{x}{1-x-x^2}$ . Para este problema eso supondría mucho trabajo, quizás más que multiplicar los polinomios, pero en general esto es bastante potente. Otro método es tomar muchas derivadas, observando que el coeficiente de $x^n$ es $\frac{1}{n!}$ veces el $n$ -a derivada en $0$ Aunque en este caso espero que sea al menos tan complicado como hacer la multiplicación original.

Toda la potencia de las funciones generadoras no se expresa generalmente en la búsqueda de un solo coeficiente, sino en la forma en que permite trabajar de forma compacta con todos los coeficientes: por ejemplo, la misma función generadora $g(x)$ anterior le dará la solución (a través del coeficiente de $x^n$ ) a este problema cuando $20$ se sustituye por un número entero cualquiera $n$ .

También puede interesarle esta pregunta y sus respuestas. Si está interesado en aprender mucho más sobre la generación de funciones, la Generatingfunctionology de Wilf es el camino a seguir.

Answer 2

Francamente, siempre recurro a un sistema de álgebra computacional en este punto, pero aquí está cómo creo que Niven probablemente esperaba que se hiciera el problema.

Hay algunos trucos para ahorrar trabajo. En primer lugar, suele ser conveniente empezar con los polinomios más dispersos (los que tienen menos términos distintos de cero). En segundo lugar, sólo hay que trabajar hasta el grado más alto necesario para la respuesta. $x^{20}$ en este caso; se pueden descartar las potencias superiores. Por último, puede no ser necesario realizar la multiplicación final. En detalle, para este problema, dejemos que

$P_2 = 1 + x^2 + x^4 + x^6 + x^8 + x^{10} + x^{12} + x^{14} + x^{16} + x^{18} + x^{20}\\ P_3 = 1 + x^3 + x^6 + x^9 + x^{12} + x^{15} + x^{18} \\ P_7 = 1 + x^7 + x^{14} \\ P_9 = 1 + x^9 + x^{18} \\$

A continuación, se descartan los términos superiores a $x^{20}$ tenemos

$P_7 P_9 = 1 + x^7 + x^9+ x^{14} + x^{16} + x^{18} + \dots$

siguiente

$P_3 P_7 P_9 = 1 + x^3 + x^6 + x^7 + 2x^9 + x^{10} + 2x^{12} + x^{13} + x^{14} + 2x^{15} + 2x^{16} +x^{17} + 3x^{18} + 2x^{19} + x^{20} + \dots$

Ahora no es necesario calcular $P_2 P_3 P_7 P_9$ porque sólo nos interesa el coeficiente de $x^{20}$ en el producto final. Desde $P_2$ sólo tiene poderes pares de $x$ podemos simplemente leer los coeficientes de $1, x^2, x^4, \dots , x^{20}$ en $P_3 P_7 P_9$ (los términos pares) y sumarlos:

$1 + 1 + 1 + 2 + 1 + 2 + 3 + 1 = 12$

Así que la respuesta final al número de soluciones es 12.

Answer 3

El tratamiento de los coeficientes de las funciones generadoras se hace de forma sintética (aprendiendo de la experiencia cuál puede ser la fórmula de los coeficientes) o directamente manipulando los coeficientes de las gfs constitutivas (lo que ayuda a lo primero). Por lo general, esto último acaba resultando en la multiplicación de polimoniales.

Para multiplicar grandes polinomios complicados con el fin de obtener un solo coeficiente:

• tirar todo lo que esté por encima del grado que te interesa.

• utilizar el papel cuadriculado para gestionar los coeficientes de una matriz

• Desplazar las líneas sucesivas para poder sumar por columnas en lugar de por diagonales.

Por ejemplo, para $(1 + 3x^2 + x^4 + 2x^6)(1 + 5x^3 + x^6)$ :

$$ \begin{array}{c|cccccccc} \hline & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ \hline & 1 & 0 & 3 & 0 & 1 & 0 & 2 \\ \hline 1 & 1 & & 3 & & 1 & & 2 \\ 0 & & & & & & & \\ 0 & & & & & & & \\ 5 & & & & 5 & & 15& & 5 & & 10\\ 0 & & & & & & & \\ 0 & & & & & & & \\ 1 & & & & & & & 1 & & 3 & & 1 & & 2 \\ \hline & 1 & 0 & 3 & 5 & 1 & 15& 3 & 5 & 3 & 10& 1 & 0 & 2 \end{array} $$

para $1 + x^2 + 5x^3 + x^4 + 15 x^5 + 3 x^6 + ...$

Si todo lo que queríamos era el coeficiente de $x^6$ podríamos haber evitado cualquier columna más allá de la 6.

Answer 4

Intenté ver si la serie Taylor podía ser de ayuda. Lo son ya que sólo quieres obtener el coeficiente de grado 20. Pero puedes hacerlo de izquierda a derecha o de derecha a izquierda (me refiero a tu escritura de los productos). Me parece que de derecha a izquierda es más rápido (¡a mano!).