Colección completa de preguntas de prueba de función
La función generadora (también llamada "función generadora") consiste en construir una función polinómica g(x) tal que el coeficiente de la enésima potencia de x sea f(n).
Lo más sorprendente de generar funciones es que algunas funciones generadoras se pueden reducir a una función muy simple. Es decir, no todas las funciones generadoras están representadas por una larga lista de polinomios. Por ejemplo, esta función f(n)=1 (n es por supuesto un número natural), entonces su función generadora debería ser g(x)= 1 x x ^ 2 x ^ 3 x ^ 4...(cada término es uno , incluso si n = 0, también hay x ^ 0. Mirando con atención, esta es una suma de series geométricas de términos infinitos si -1
Damos un ejemplo para ilustrar que esto también se puede usar en. algunos problemas prácticos de combinación. Una función simple de representar.
Considere esta pregunta: ¿Cuántas formas hay de seleccionar N MM de la Clase 2? Los estudiantes que han aprendido permutaciones simples saben que la respuesta es C(4, n). Digamos que a partir de n=0, la respuesta a la pregunta es 1, 4, 6, 4, 1, 0, 0,... (Por supuesto, el número de opciones para elegir más de 4 personas entre 4). MM es 0). g(x) debería ser G (x) = 1 4x 6x 2 4x 3 x 4. ¿No es esta la expansión binomial? Entonces g (x) = (1 x) 4. Probablemente deberías saber eso. (1 x) k = c (k, 0) x 0 c (k, 1) x 1 ... c (k, k) Cuando , se llega a una conclusión similar: (1 x) k = c (k, 0 ) x 0 c (k, 1) x 1 ... c (k, k) x La fórmula parece incómoda, así que la escribí en el papel borrador. Adelante, después de todo, es problemático ingresar la fórmula matemática aquí. Entre ellos, el número de combinación generalizada C(k, I) es igual a k(k-1)(k-2)(k-I 1)/I! =0, o c (-1.4, 2) = (-1.4) * (-2.4)/2! =1.68 Cuando k es un número entero, todos los términos i gt "0" deben intersectarse en C(k,. I) en k, por lo que el siguiente C(k, k 1), C(k, k 2), etc. es 0, que es lo mismo que nuestro teorema binomial clásico. La diferencia es que el exponente k en el teorema binomial de Newton. puede ser cualquier número real.
Demos otro ejemplo para ilustrar algunos detalles más. Función generadora compleja ¿Cuántas soluciones enteras no negativas hay para N=x1 x2? permutaciones Sumar 1 a cada conjunto de soluciones se convierte en n k=x1 x2. El número de soluciones enteras positivas para "Partición". La respuesta que siempre hemos sabido es C (n k-1, k-1). para n es g (x) = 1/(1- x) k, ¿de dónde viene esta función generativa? En realidad es la potencia -k de (1-x). Según la expansión binomial de Newton (1-x). (-k), obtenemos que el coeficiente de x n es exactamente C(n k-1,n), ya que c (-k,n) * (-x) n = [(-65438). Está bien sentirse mareado aquí. Hay otra manera de derivar la misma fórmula más adelante. De hecho, tenemos un método de explicación más simple de la matemática combinatoria pura. Debido a que nuestra serie geométrica 1 x x ^ 2 x ^ 3 x ^ 4 ... = 1/(1-x), entonces (1 X ^ 2 X ^ 3 X ^ 4 ...) multiplicación.
En la expansión de (1 hecha.
Citemos ahora un ejemplo clásico de combinatoria. Muchos libros tendrán esta pregunta.
Necesitamos escoger algunas frutas entre manzanas, plátanos, naranjas y peras. Se requiere que la cantidad de manzanas solo pueda ser un número par, la cantidad de plátanos debe ser múltiplo de 5, la. La cantidad de naranjas puede ser hasta 4 y la cantidad de peras solo puede ser una o ninguna. Preguntar por el número de opciones para obtener n resultados según este requisito.
También podemos combinar la multiplicación de K(1 X
g(x)=(1 x^2 x^4 ...)(1 x^5 x^10 ..)( 1 x x^2 x^3 x^4)(1 x)
=[1/(1-x ^ 2)]*[1/(1-x ^ 5)]*[(1 -x ^ 5)/(1-x)]
El tercero, (1 x x 2 x 3 x 4) * (1-x) es 1-x 5).
= 1/(1-x) 2
= (1-x) (-2) = c (1,0) c (2,1) x c (3, 2) x 2 c (4, 3) x 3...
=1 2x 3x^2 4x^3 5x^4....
Entonces hay n tipos de frutas n 1 formas de tomar. ¡Utilizamos funciones generadoras y obtuvimos la respuesta de forma completamente algebraica!
Si no estás familiarizado con la expansión de 1/(1-x) K, te presentaremos una forma más sencilla y sutil de explicar 1/(1-x)2 = 1 2x 2 4x 3 .
1/(1-x)= 1 x x2 x3 x4 ...como se mencionó antes. Tomamos la derivada de esta fórmula a ambos lados del signo igual. Entonces, 1/(1-x)2 = 1 2x 3x 2 4x 3 5x 4… ¡obteniendo lo que necesitamos en un solo paso! A través de la derivación continua, también puede obtener la conclusión a la que acaba de llegar utilizando el complejo teorema del binomio de Newton (pruébelo usted mismo). Hay muchas otras formas de generar funciones, como multiplicar ambos lados de la ecuación por una constante y dividir por una constante (equivalente a multiplicar cada término del lado derecho de la ecuación por una constante y dividir por una constante), multiplicar ambos lados de la ecuación por una x y dividir por una x (equivalente a Mover el coeficiente en el lado derecho de la ecuación una posición) y encontrar el diferencial y la integral. Función de generación mágica.
Obtuvimos dicha fórmula mediante dos métodos: 1/(1-x)n = 1 c(n, 1) x 1 c (n 1, 2) x. es una poderosa herramienta para simplificar una función generadora en una secuencia. Y armas nucleares.
A continuación, demostraremos cómo utilizar funciones generadoras para encontrar la fórmula general de la secuencia de Fibonacci.
La secuencia de Fibonacci es una secuencia recursiva: f(n)=f(n-1) f(n-2). Ahora necesitamos encontrar su función principal g(x). G(x) debería ser una función como esta:
g(x)=x x^2 2x^3 3x^4 5x^5 8x^6 13x^7...
Multiplicando ambos lados de la ecuación por x, obtenemos:
x*g(x)=x^2 x^3 2x^4 3x^5 5x^6 8x^7...
Dijimos antes que esto equivale a que todos los coeficientes del lado derecho de la ecuación se desplacen una posición hacia la derecha.
Ahora sumamos la fórmula anterior a la última fórmula, obtenemos:
g(x) x*g(x)=x 2x^2 3x^3 5x^ 4 8x ^5...
Compara la última fórmula con la primera fórmula. Si el coeficiente de la primera fórmula se desplaza una posición hacia la izquierda y se elimina el "1" adicional, se convierte en la última fórmula.
Debido a la naturaleza de las funciones recursivas, mágicamente obtenemos: g(x) x*g(x)=g(x)/x-1. Es decir, g (x)* x ^ 2 G(x)* x-G(x)=-x Sacando el G(x) de la izquierda, tenemos: G(x)(x ^ 2 x-. 1) =-x. Entonces, obtenemos G(x)= x/(1-x-x ^ 2).
La tarea actual es simplificar x/(1-x-x ^ 2) en una fórmula general. Esto no está en la forma 1/(1-x) n, debemos cambiarlo a esta forma. Encontramos que 1-x-x2 =[1-(1-√5)x/2]*[1-(1 √5)x/2]((65438) Obviamente, deberían ser x 2-x-1 = Dos raíces de 0. Entonces x/(1-x-x ^ 2) debe expresarse como? /[1-(1-√5)x/2] Nuevamente, perdón por la molestia de ingresar la fórmula matemática, simplemente míralo). Seguramente esto es posible, ya que es apropiado que el valor de ? sume exactamente un valor después de dividir las dos fracciones. ¿Cuál es? Supongamos que el primero es c1 y el segundo es c2. el numerador después de la división general es c 1 *[1-(1 √5)x/2] C2 *[1-(1-√5)x/ . Obtenemos dos fórmulas: término constante c1 c2=0, término lineal -c. 1 *(1 √5)/2-C2 *(1-√5)/2 = 1. Estas dos fórmulas son suficientes para resolver c1 y . No es necesario que entiendas. Estoy usando Mathematica 5.0. La solución es c1=-1/√5, c2=1/√5. Ahora, podemos resolverlo con X/(1-X-X. ^ 2) se convierte en -(1/√5)/[. 1-(1-√5)X/2] (1/√5) Ya sabemos que 1/[1-(1-√5)x/2] es una serie geométrica con (1-√5). /2 como la razón común, 1/[1-(65438). Luego, multiplicamos cada uno por una constante, los sumamos y obtenemos la fórmula general de la secuencia de Fibonacci: f(n)=-(1). /√5)*[(1-√5)/2]n (1/√5)*[Quizás te preguntes, qué complicada La fórmula de y el signo raíz ¿No son todos los números de Fibonacci enteros? Lo importante es que esta fórmula llena de raíces es un número entero para cualquier número natural n. Los estudiantes que estén familiarizados con el uso de ecuaciones características para resolver ecuaciones lineales recursivas deben saber lo anterior. El proceso para encontrar las raíces características es esencialmente el mismo. Usando el método anterior, podemos encontrar la fórmula general de cualquier ecuación recursiva lineal homogénea. ¿Cuál es la ecuación recursiva? f(n) es igual a cuántos F(n-1) más cuántos F(n-2) más cuántos. muchos F (n-3), etc. La relación de recurrencia de la secuencia de Fibonacci es una relación de recurrencia lineal homogénea.
Finalmente, hablemos del intercambio de monedas: tengo 1 punto, 2 puntos y 5. Considerando el resultado de ahora, ¿de cuántas maneras podemos resolver este problema? Generando la función de: g (x) = (1 x x 2 x 3...)(1 x 2 x 4...)(1 x 5). Ahora, necesitamos convertirlo en una fórmula general. Nuestros pasos son exactamente los mismos que antes. Expandimos (1-x)(1-x 2)(1-x 5) y obtenemos 1-x-x 2 x 3-. x 5 x 6 x 7- Hallamos -1 x x ^ 2-x ^ Para la solución de 3 x ^ 5-x ^ 6-x ^ 7 x ^ 8 = 0, se obtienen las siguientes ocho soluciones: -1. , 1, 1. Esto no se calculó, por lo que se utilizó Mathematica 5.0. No es que no quiera resolverla, es que no sé cómo resolver esta ecuación de octavo orden en absoluto. Esta es también la razón por la que la sociedad de la información involucra estas cosas: el número de veces es ligeramente mayor, por lo que se deben usar computadoras para resolverlo. Entonces, (1-x)(1-x ^ 2)(1-x ^ 5)=(1 x)(1-x)3(1 (-). Tenga en cuenta que (1-x) 3.
Debido a la aparición de raíces iguales, tenemos que escribir temporalmente los factores (1-x) 2 y (1-x)2 contenidos en (1-x) 3 en el denominador; de lo contrario, no podremos resolver una adecuado c. Puedes ver muchos números imaginarios. Pero no importa, estos números imaginarios también están involucrados en la operación, al igual que la fórmula para encontrar raíces de ahora, y no afectarán la racionalidad del resultado final. Luego, encontramos que la constante satisface 1/(1-x)(1-x ^ 2)(1-x ^ 5)= c 1/() C2/(1-x ^ 5). Esta solución es demasiado complicada. Utilicé Mathematica para resolverlo durante unos minutos e imprimí una fórmula de al menos decenas de KB. Aunque complicado, entendí la fórmula general. Aquellos que estén interesados pueden intentar usar Mathematica para resolver 1/[(1-x)(1-x 3)] (sólo monedas de 1 y 3 céntimos). Puedes usar la función SolveAlways[] para resolver el valor de c. Puedes ver con tus propios ojos que una fórmula de cuatro o cinco líneas llena de números imaginarios siempre obtendrá la respuesta entera correcta al final.
Hay muchas cosas sobre funciones generadoras, como la derivación de series catalanas, funciones generadoras exponenciales, etc. Hablaré de ello más tarde cuando esté libre. Más de 5.000 palabras.
Hu Yichen ha estado haciendo esa pregunta. Obviamente, ese tema está relacionado con el intercambio de monedas mencionado anteriormente. De hecho, muchas preguntas similares están relacionadas con funciones generadoras. Pero la función generadora no se usó en esa pregunta (tal vez no me lo esperaba). Tal vez haya alguna forma de resolver cada máximo mediante una función generadora, pero es poco probable que todo el problema pueda resolverse mediante una función generadora.
Recientemente hubo una publicación preguntando sobre el tema del "escarabajo DP". Lo mismo ocurre con ese tema, muchos temas similares están relacionados con el PD, pero es poco probable que ese tema cambie las reglas. Siempre siento que se puede atribuir al problema del embalaje (considerando el volumen, se necesitan al menos unas cuantas cajas para guardar todos los artículos), y este último parece pertenecer a NPC. Quizás me equivoque. Sólo estoy trabajando en cosas teóricas en este momento. No he pensado en OI durante mucho tiempo y mi habilidad en esta área ha comenzado a deteriorarse.