Aquí tienes algunos recursos para empezar a generar funciones. Con una excepción, que está claramente designada, cualquiera de los elementos mencionados aquí debería ser adecuado para proporcionar una suave introducción a las GFs para los novatos totales.
-
Generación de funciones de Herbert S. Wilf es probablemente el mejor texto introductorio. Puedes encontrar este libro en formato pdf de forma gratuita, en línea, pero creo que vale la pena añadir una copia impresa a tu biblioteca. El estilo de escritura es ágil y entretenido. Primera frase: "Una función generadora es un tendedero en el que colgamos una secuencia de números para mostrarla".
-
Introducción al análisis de algoritmos de Robert Sedgewick y Philippe Flajolet es otra buena introducción. A pesar de su título, el libro trata principalmente sobre la generación de funciones. Coursera tiene un curso online gratuito de la Universidad de Princeton basado en este libro, con el profesor Sedgewick como instructor, así que aquí tienes la oportunidad de sentarte a los pies del Maestro, figurativamente: Coursera Análisis de Algoritmos . También hay un curso de seguimiento sobre Combinatoria Analítica: Coursera Combinatoria Analítica . El curso de combinatoria analítica se basa en el libro Combinatoria analítica de los mismos dos autores, que es un buen libro, pero no creo que sea el mejor punto de partida para la mayoría de los principiantes. (Por supuesto, usted podría ser la excepción, y realmente es un libro maravilloso con una cobertura enciclopédica). Ambos cursos de Coursera son selectivos en su cobertura y no intentan cubrir todo el contenido de sus respectivos libros, especialmente el curso sobre combinatoria analítica.
-
Ya que estamos hablando de materiales gratuitos en línea, Bogart's Introductory Combinatorics (pdf) incluye una introducción a las funciones generadoras. Bogart lleva al lector a descubrir por sí mismo ideas y métodos a través de una serie de problemas. De hecho, el libro está compuesto casi en su totalidad por problemas.
-
Esquema de teoría y problemas de combinatoria de Schaum de V.K. Balakrishnan incluye una buena introducción a las funciones generadoras y destaca por ser barato en comparación con otros textos (alrededor de 20 dólares en Amazon la última vez que lo comprobé). Este libro me parece útil como referencia y como recurso de aprendizaje. Incluye algunos temas relativamente avanzados, como los polinomios de Rook y el Teorema de Enumeración de Polya, pero puedes saltarte esas partes en una primera lectura.
-
¿Se siente abrumado por la cantidad de material sobre la generación de funciones en los libros anteriores? Tal vez desee una introducción breve y práctica, sólo lo básico. En ese caso, puede que le guste el capítulo 6 de Combinatoria aplicada por Alan Tucker.
-
Y seguro que hay muchos más. Muchos libros de combinatoria incluyen secciones sobre funciones generadoras.
En cuanto a los prerrequisitos, muchas aplicaciones de los GF sólo requieren un conocimiento de los polinomios. Pero muchas otras requieren series infinitas, por lo que se necesita cierta exposición a series como las series geométricas infinitas, las series para $e^x$ y el Teorema del Binomio para exponentes negativos y fraccionarios. Curiosamente, a menudo (pero no siempre) podemos ignorar las cuestiones de convergencia, porque vemos las series como objetos formales y no nos preocupamos de evaluarlas. A menudo es útil diferenciar o integrar una función generadora, por lo que se necesitan conocimientos de cálculo. (De hecho, parte de la fascinación de las funciones generadoras es que toman un problema de matemáticas discretas, donde las herramientas normales son la suma, la multiplicación, la resta y la división, y transforman el problema en el ámbito de lo continuo, donde se aplican herramientas como el cálculo diferencial e integral). Algunas aplicaciones utilizan ecuaciones diferenciales o análisis complejo, pero se puede llegar muy lejos sin ellas.
Un sistema de álgebra computacional, como Wolfram Alpha, aunque no es esencial, a veces es útil para eliminar la pesadez de los cálculos que de otro modo serían tediosos. Solía sentirme culpable cuando utilizaba un ordenador para multiplicar dos polinomios largos, pero he superado la culpa y ahora siento que para el combinador, el álgebra computacional es una herramienta básica como una calculadora.
Para despertar su interés por los GF, he aquí cómo el estadístico Frederick Mosteller describió su exposición inicial a las funciones de generación.
Un momento clave en mi vida ocurrió en una de esas clases durante mi segundo año. Teníamos la pregunta: Cuando se tiran tres dados, ¿cuál es la probabilidad de que la suma de las caras sea 10? Los alumnos de este curso eran muy buenos, pero todos obtuvimos la respuesta en gran parte contando con los dedos. Cuando llegamos a clase, le dije al profesor "Está muy bien, hemos obtenido la respuesta, pero si nos hubieran preguntado sobre seis dados y la probabilidad de obtener 18, todavía estaríamos en casa contando. ¿Cómo se hacen problemas así?". Dijo: "No lo sé, pero sé, pero conozco a un hombre que probablemente lo haga y le preguntaré". Un día yo estaba en la biblioteca y el profesor Edwin G Olds del Departamento de Matemáticas Departamento de Matemáticas. Me gritó: "He oído que estás interesado en el problema de los tres dados". Tenía una voz enorme, y ya sabes cómo son las bibliotecas son. Me sentí avergonzado. "Bueno, ven a verme", dijo, y te enseñarte sobre ello". "Claro", dije. Pero me decía a mí mismo: "Nunca nunca iré". Entonces me dijo: "¿Qué estás haciendo?" Le mostré. "Eso no es nada importante", dijo. "Vamos ahora".
Así que fuimos a su oficina y me mostró una función generadora. Es era la cosa más maravillosa que había visto en las matemáticas. Utilizaba matemáticas que, hasta ese momento, en mi corazón de corazones, había creía que era algo que los matemáticos hacían para crear problemas problemas para estudiantes inocentes en la escuela secundaria y la universidad. No sé no sé de dónde había sacado esas ideas sobre varias partes de las las matemáticas. De todos modos, me quedé atónito cuando vi cómo Olds utilizaba esta matemáticas en las que yo no había creído. La utilizó de una manera tan inusualmente de una manera tan escandalosa. Era una retraducción total del significado de los números. [Albers, Más gente de matemáticas ].
** Edición añadida el 13 de febrero de 2021 **
Mathologer tiene un vídeo en YouTube en el que desarrolla la función generadora del número de formas de hacer el cambio con monedas estadounidenses, y utiliza la GF para encontrar una fórmula del número de formas de hacer el cambio para $k$ dólares. A continuación, utiliza esa fórmula para explicar por qué vemos un patrón extraño en el número de formas de hacer el cambio para varios números de dólares. El vídeo no presupone ningún conocimiento previo de las funciones generadoras, por lo que puede ser una buena introducción al tema. Explicando el extraño patrón de hacer el cambio por un googol de dólares
3 votos
También cabe destacar que la función generadora es prácticamente lo mismo que la (muy utilizada en el procesamiento de señales) transformada Z, que a su vez es el análogo discreto de la transformada de Laplace. math.stackexchange.com/questions/137178/