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

ProgCAnalitica-2024-I.pdf

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.

Semana1Introduccion.pdf

Semana1.pdf

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.

Semana2.pdf

Semana2Catalan.pdf

Semana 3: Clase Combinatoria de los Poliominós. Inversión de Lagrange.

Semana3.pdf

Semana3Poliomino.pdf

Lecturas recomendadas: Counting Polyominoes, Revisited.

1.9781611977929.10.pdf

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.

Semana4.pdf

Semana 5: Otras construcciones combinatorias MSET. Particiones de Enteros. Demostración combinatoria del Teorema de los Números Pentagonales.

Semana5.pdf

Semana 6: Contando por simetrías.

Semana6.pdf

Semana 7: Clase cíclos. Clases etiquetadas.

Semana7.pdf

Semana 8-9-10***: Clases etiquetadas y de segundo orden.

Semana89.pdf

Lecturas para el método de Wilf-Zeilberger:

M . Petkovsek, H. Wilf D. Zeilberger. A=B.

J. L. Ramírez, F. Velandia. Métodos computacionales para demostrar identidades combinatorias. Lecturas Matemáticas, 43(2)(2022), 73-88. (pdf)

Semana 9-10***: Clases de segundo orden. Teorema de Cayley (Demo. 1: Egecioglu-Garcia, Demo. 2 Prufer). Grafos funcionales.

Semana910.pdf

Semana 11-12***: Conteo de Grafos Sin cíclos. Funciones de Parqueo. Problemas de teselaciones.

Semana1011.pdf

PresentacionDiscreMath2024.pdf

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

Referencias

P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009.

M. Mishna. Analytic Combinatorics, A Multidimensional Approach. CRC Press, 2020

H. Wilf. generatingfunctionology. Academic Press, Inc. 1994.

R. P. Stanley. Catalan numbers. Cambridge University Press, 2015.

Lectura recomendad: Combinatorial aspects of continued fractions P.Flajolet