¿Por qué son útiles las funciones generadoras?

Question

Yo estaba bajo la impresión errónea de que si se podía encontrar a la generación de la función de una secuencia de números, usted podría simplemente conecte un número natural $n$ para encontrar el n-ésimo término de la secuencia. Ahora me doy cuenta de que me estaba confundiendo esto con una forma cerrada de la fórmula.

Así que si ese no es el caso, entonces ¿cuál es el punto de generar funciones? ¿Cómo hacer entender a contar de las secuencias más fácil? Por ejemplo, supongamos que tuve un problema en el que yo quería contar cuántas maneras se podía comprar $n$ trozos de manzanas, naranjas, peras, dado que quiero un número par de manzanas, un número impar de naranjas, y en la mayoría de los 3 peras. Esta sería la número de número entero no negativo soluciones a $a+b+c=n$ con $un$ incluso, $b$ impar, y $0\leq c\leq 3$. Este es el mismo que el coeficiente de $x^n$ en el producto $$ (1+x^2+x^4+\cdots)(x+x^3+x^5+\cdots)(1+x+x^2+x^3) = \frac{1}{1-x^2}\cdot\frac{x}{1-x^2}\cdot\frac{1-x^4}{1-x}$$

Pero lo bueno es que? No veo cómo esto es mucho mejor. También, con el uso de exponenciales funciones de generación, parece que la elección de monomials utilizamos como marcadores de posición para los términos de la secuencia puede ser arbitraria. Entonces $n$ésimo término de la secuencia es sólo el coeficiente de la $n$th monomio que has elegido para construir la generación de función. ¿Cuál es la ventaja real de hacer cosas como esta? Muchos de los problemas que veo tienden a hacer que me encuentre la generación de función, pero yo soy rara vez se le pedirá que haga algo con ella.

Answer 1

La forma cerrada fórmulas están sobrevalorados. Cuando existen, la generación de la función de las técnicas a menudo puede ayudar a encontrar; cuando no, la generación de la función es la siguiente mejor cosa, y resulta ser mucho más poderoso de lo que parece a primera vista. Por ejemplo, la mayoría de la generación de funciones de meromorphic funciones, y esto significa que uno puede deducir asintótica información acerca de una secuencia a partir de las localizaciones de los polos de la generación de la función. Este es, por ejemplo, cómo se deduce la asintótica de los números de partición.

En tu ejemplo, la generación de la función es racional, por lo que tiene un número finito de polos. Eso significa que usted puede utilizar parcial fracción de descomposición en él para obtener de inmediato una forma cerrada.

Usted podría estar interesado en leer mis notas en la generación de funciones, que tienen varios ejemplos y que espero ser esclarecedor. La primera cosa básica a entender es que la manipulación de funciones de generación es mucho más fácil que la manipulación de secuencias, pero el poder de la generación de funciones va mucho más profundo que esto. Para un debate en profundidad recomiendo Flajolet y Sedgewick de la Analítica de la Combinatoria, que está disponible de forma gratuita en línea.

Answer 2

Has leído Generatingfunctionology por Herbert Wilf? El libro está cargado con métodos y técnicas que se basan en la generación de funciones para resolver una serie de problemas diferentes. Supongo que el libro pueda responder a su pregunta mejor que yo.

Siento que la generación de funciones son de gran alcance, ya que permite el uso de herramientas de cálculo y análisis para resolver problemas en áreas como la matemática discreta y combinatoria, donde tales herramientas no parecen fácilmente aplicable.

Edit: yo sólo quería añadir un punto más. Supongamos que se han traducido en el problema de la secuencia para la generación de la función, y no lo veo cualquier simple de la forma cerrada de soluciones, se podría usar Wolfram Alpha, para estar absolutamente seguro. Wolfram alpha puede fácilmente ampliar expresiones que involucran a grandes términos polinomiales y a menudo te dará una expansión de la serie, si es que existe en forma cerrada.

Answer 3

Para responder a su pregunta para el ejemplo de estado:

$$ \frac{1}{1-x^2} \cdot \frac{x}{1-x^2} \cdot \frac{1-x^4}{1-x} = (x + x ^ 2 + x ^ 3 + x ^ 4) (1-x ^ 2) ^ {-2} $

Por el teorema del binomio (sí, es válida para exponentes negativos demasiado) conseguimos que esto es igual a

$$ (x + x ^ 2 + x ^ 3 + x ^ 4) \left (\sum_ {j = 0} ^ {\infty} (-1) ^ j {-2 \choose j} x ^ {2j} \right) $$

¿Puede ahora calcular una fórmula para el coeficiente de \displaystyle $ x ^ n$, resolviendo su problema?

Answer 4

Me gusta el libro "Analítica de la Combinatoria" de Philippe Flajolet y Robert Sedgewick la Parte A. no Se trata sólo de mostrar una manera de cómo traducir combinatorical problemas en términos de relaciones funcionales de la generación de funciones (el espectáculo que sin etiquetar estructuras se refieren a simples funciones de generación, y etiquetados estructuras se relacionan exponencial funciones de generación), sino que también proporciona una forma (asintótica de expansión, ...), que en realidad se puede calcular algo.

Answer 5

Cuando se trata de comprender una situación de conteo, lo mejor es tener una forma cerrada de la fórmula, una función que es fácilmente calculable por los métodos conocidos ('cerradas' es un poco resbaladizo en el significado, pero por lo general significa, sin ningún tipo de recursividad, pero hay espacio para el desacuerdo sobre si las sumas o productos que están permitidos (aunque factorial a menudo está permitido). A partir de tales funciones, es generalmente sencillo para determinar aproximaciones y asymptotics y combinar con otras funciones.

La mejor cosa siguiente es una recurrencia. Permite el cálculo a menudo en una muy manera directa con ninguna aproximación necesaria. Pero las recurrencias son un poco inescrutable; es muy difícil para simplificar o leer directamente a las propiedades de la recurrencia (mientras que la forma cerrada es muy fácil de entender).

En algún lugar entre estos dos, la generación de funciones permite la facilidad en la combinatoria de manipulación (la multiplicación de dos ogfs significa que uno es obtener un par ordenado de los objetos de la gfs describir). También hay técnicas analíticas que permiten la extracción de asymptotics de gfs. Y, aparentemente uno puede obtener valores por $f(n)$ de la gf distinguiéndolo $$ n veces y evaluar a 0.

Wilf del generatingfunctionology, como se ha mencionado en los comentarios, es el lugar para ir para la obtención de estas técnicas para la gfs.