Funciones de generación de combinatoria

Question

Yo no tengo ninguna educación formal en las funciones de generación, pero, a partir de otra pregunta, he visto que pueden ser de gran alcance para la combinatoria.

Hay algunos principios generales para el uso de funciones de generación para la construcción de contar argumentos (por ejemplo, contar el número de subconjuntos o número total de órdenes) que puede ser reeditada para contar diferentes cantidades?

Si la respuesta no es susceptible a este foro, donde puedo obtener más información?

He estado tratando de leer Concreto de las Matemáticas (Graham, Knuth, Patashnik), pero el tema se extiende por varios capítulos y más de 100 páginas. Por el momento, sólo tengo paciencia para aprender la esencia de la combinatoria de las aplicaciones de generación de funciones. Tal vez más adelante voy a volver atrás y obtener una amplia educación de GKP.

Answer 1

También me gustaría recomendar Wilf del Generatingfunctionology. Está disponible en línea. Si te gusta, hacer Wilf la cortesía de la compra de una copia.

Answer 2

Hay una introducción muy básica disponible en línea en http://courses.csail.mit.edu/6.042/fall05/ln11.pdf

Usted también puede encontrar en el siguiente enlace útil http://www.mathdb.org/notes_download/elementary/algebra/ae_A11.pdf

Estas notas dan una idea básica de cómo generar funciones son útiles para la resolución de sencillos problemas de recuento. Wilf del Generatingfunctionology es muy recomendable si desea más avanzado, y en la profundidad de tratamiento de los sujetos.

Answer 3

Flajolet y Sedgewick de la Analítica de la Combinatoria es densa, pero equipa con increíbles herramientas para construir, manipular y extraer información de las funciones de generación. También encontré los capítulos pertinentes de Stanley Combinatoria Enumerativa (dos volúmenes) extremadamente útil.

Funciones de generación de pasar a ser un tema favorito de la mía, así que he escrito varios posts sobre el tema en mi blog. Es posible que desee comenzar en este post, que se construye para una explicación de la Polya enumeración teorema, y hace un par de años escribí estas notas que pueden ser útiles.

De hecho, hay algunos principios generales, pero tengo una enorme dificultad para describir de manera concisa.

Answer 4

Para agregar a las otras respuestas. La utilidad de la generación de funciones va más allá de contar-combinatoria. Ellos son una de las herramientas básicas para tratar con funciones discretas, en particular con el lineal de ecuaciones de diferencia - y estos aparecen con frecuencia, normalmente como recursiones, cuando la solución de muchos problemas de recuento, o cuando se trata de probabilidades discretas, etc.

Una nota para los que vienen de la ingeniería: la generación de funciones son muy conectado a la transformada en Z (una herramienta elemental en discretos de Procesamiento de la Señal) -podría decirse que son exactamente la misma cosa, sólo una terminología diferente - pero el de matemáticas y el concepto es el mismo. Y, para añadir más conexiones (quizás más confusión?), la transformada en Z puede ser pensado como la versión discreta de la transformada de Laplace - y también como una generalización de la transformada de Fourier discreta.