Combinatorial Counting, NDMI015, summer term 2023/24
My plan is to begin with an introduction on the Catalan numbers, then to give a survey of the proof
of the Bombieri--Pila theorem (see lecture 1) and in the third part to go through Chapters 4 and 5
on enumeration of permutations with forbidden patterns in the
textbook
Combinatorics of Permutations (Third Edition) by M. Bóna. I will produce lecture notes to my lectures.
Lecture 1 (updated February 19) - February 23, 2024. Two proofs of the formula C_n=(1/n)binom(2n-2, n-1)
for the Catalan numbers.
Lecture 2 (updated March 1, 2024) - March 1, 2024. The right GF proof of the formula
C_n=(1/n)binom(2n-2, n-1). D-finite and algebraic FPS
Lecture 3 (updated March 15, 2024) - March 8, 2024. C_n=O(c^n) from first primciples.
M. Artin's Approximation Theorem (no proof)
Lecture 4 (updated March 22, 2024) - March 15, 2024. Three proofs that (C_n) is not a LRS
(linear recurrence sequence)
Lecture 5 (to be updated) - March 22, 2024. Fourth proof that (C_n) is not a LRS
March 29 - Good Friday --> no lecture
Lecture 6 (to be updated) - April 5, 2024. The article of R. Pierzchala: On roots of polynomials
with power series coefficients, Annales Polonici Mathematici 80 (2003), 211-217
April 2024