Combinatoria Analítica 2024-I (Posgrado)
G1 - Código 2028824
(Ver el programa como archivo adjunto)
Horario:
Lunes 6-8 pm
Miércoles 6-8 pm
Lugar: Edifio 405, Salón 310.
Inicio de clases 6 de Febrero de 2024
Link para subir las tareas (Deben entregarse en los grupos de trabajo el Viernes de la siguente semana)
Temas Proyectos
Demostración Combinatoria del Teorema de la Inversión de Lagrange. (Pueden seguir el libro de Martin Aigner o el Vol. 2 de Stanley).
Introducir las Parking Functions y sus generalizaciones. (De hesto hay mucho, por ejemplo, link1, video, link2, link3)
Introducir el método de Gessel–Viennot. (Pueden seguir el libro de Martin Aigner (Sec. 5.4) o el Vol. 1 de Stanley (Sec. 2.7) y la ref. (link))
Introducir el Matrix-Transfer Method. (Pueden seguir el Vol. 1 de Stanley (Sec. 4.7) y la ref. (link))
Logarithms of Catalan Generating Functions: A Combinatorial Approach. The Electronic Journal of Combinatorics 31(1) (2024), #P1.4 (link).
Analytic models and ambiguity of context-free languages. Theoretical Computer Science Volume 49, Issues 2–3, 1987, Pages 283-309 (link)
The number of directed k-convex polyominoes. Discrete Mathematics 343 (2020) 111731. (link)
Fixed Points in Compositions and Words. Journal of Integer Sequences, Vol. 23 (2020), Article 20.11.1. (link)
k-Protected vertices in binary search trees. Advances in Applied Mathematics, Vol. 53,(2014), 1-11 (link)
Pick two points in a tree. J. Korean Math. Soc. 56 (2019), 1247–1263 (link)
Refined enumeration of 2-noncrossing trees. Notes on Number Theory and Discrete Mathematics 27 (2021), 201–210 (link)
Enumerating regular expressions and their languages (link).
Random walks with absorbing points. Discrete Applied Mathematics 39, (1992), 57-67. (link)
Self-avoiding walks of specified lengths on rectangular grid graphs. Aequationes Mathematicae (link)
Domino Tilings of 2 X n Grids (or Perfect Matchings of Grid Graphs) on Surfaces. Journal of Integer Sequences, Vol. 26 (2023), Article 23.5.6 (link)
Convex Domino Towers. Journal of Integer Sequences, Vol. 20 (2017), Article 17.3.1 (link)
Semana 1: Una primera mirada a la Combinatoria Analítica. Clases combinatorias. Suma, Multiplicación y Sucesión de Clases Combinatorias.
A propósito de esta tarea, les puede interesar la siguiente referencia: Further Results on Paths in an n-Dimensional Cubic Lattice.
Semana 2: Clases isomorfas. Estrcuturas enumeradas por los números de Catalan (Argumentos biyectivos). Composiciones de enteros via el método simbólico.
Semana 3: Clase Combinatoria de los Poliominós. Inversión de Lagrange.
Lecturas recomendadas: Counting Polyominoes, Revisited.
Lecturas recomendadas: La demostración del Teorema de la Inversión de Lagrange que hicimos en clase la pueden enconrar en el Volúmen 2 del libro de Richard Stanley (Enumerative Combinatorics) (Theore 5.4.2). Otro libro con la demostración combinatoria es el de Martin Aigner (A Course in Enumeration) (Theorem 3.8).
I. M. Gessel. Lagrange Inversion. Journal of Combinatorial Theory, Series 144, (2016) 212-249.
D. Merlini, R. Sprugnoli, M.C. Verri. Lagrange inversion: When and How. Acta Applicandae Mathematica 94 (2006), 233–249.
Semana 4: Aplicaciones Inversión de Lagrange. Otras construcciones combinatorias PSET.
Semana 5: Otras construcciones combinatorias MSET. Particiones de Enteros. Demostración combinatoria del Teorema de los Números Pentagonales.
Semana 6: Contando por simetrías.
Semana 7: Clase cíclos. Clases etiquetadas.
Semana 8-9-10***: Clases etiquetadas y de segundo orden.
Semana 9-10***: Clases de segundo orden. Teorema de Cayley (Demo. 1: Egecioglu-Garcia, Demo. 2 Prufer). Grafos funcionales.
Semana 11-12***: Conteo de Grafos Sin cíclos. Funciones de Parqueo. Problemas de teselaciones.
Lecturas recomendadas:
J. Carlos Martınez Mori. What is a Parking Function. https://arxiv.org/pdf/2404.15372#page11
Philippe Flajolet, Patricio Poblete , Alfredo Viola. On the analysis of linear probing hashing
Semana 13-14***: Funciones generatrices en varias variablesy parámetros combinatorios. F.g de probabilidad. Valor esperado y varianza. Parámetros heredados.
Semana 14-15***: Otras ecuaciones funcionales. Composiciones de Carlitz. Principio de Inc-Exc. (simbólico). Funciones generatrices como objetos anlíticos. Análisis de la funciones racionales.
Artículos que les puede interesar:
Lectura recomendada: Combinatorial aspects of continued fractions P.Flajolet
Referencias
M. Mishna. Analytic Combinatorics, A Multidimensional Approach. CRC Press, 2020
R. P. Stanley. Catalan numbers. Cambridge University Press, 2015.