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 - abandoned) 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.
NEW updated: version 5 of June 7. Next update: June 10.
Complete list of seven exam qestions. 1. Outline the three proofs of the formula C_n=(1/n)B(2n-2, n-1) and give in detail
one of them (Chapters 1 and 2). 2. Prove that a FPS is D-finite iff its coefficients are
P-recursive (Proposition 2.7). 3. Outline the four proofs
that (C_n) is not a LRS (linear recurrence sequence) and give in detail one of them (Chapters 4 and 5). 4. Prove the asymptotics
C_n~c.n^{-3/2}.4^n (for n->oo) of Catalan numbers (Corollary 3.3). 5. Outline the proof of the Marcus-Tardos theorem 1
(Chapter 8, Theorem 8.1) 6. Enumerate (1,2,3)-avoiding and (1,3,2)-avoiding permutations (Chapter 9).
7. NEW Prove lower and upper exponential bounds on numbers of (1,2,...,m)-avoiding permutations
(Chapter 10, the previous version of this question was too hard).
Lecture 1: February 23, 2024; L2: March 1, 2024; L3: March 8, 2024; L4: March 15, 2024; L5: March 22, 2024;
L6: April 5, 2024; L7: April 12, 2024; L8: April 19, 2024; L9: April 26, 2024; L10: May 3, 2024; L11: May 10, 2024;
L12: May 17, 2024; L13: May 24, 2024. All these lectures took place and their content is (or will be) reflected in the above lecture notes.
June 2024