The Art of Bijective Combinatorics Part IV

Combinatorial theory of orthogonal polynomials and continued fractions

The Institute of Mathematical Sciences, Chennai, India (January-March 2019)

Chapter 1 Paths and moments

Chapter 1a Tchebychev I and II, Hermite and Laguerre polynomials as matching polynomials of graphs,

sign reversing involution for the linearization coefficients of Hermite and Laguerre polynomials

January 14, 2019

slides of Ch1a (pdf 18 Mo)

video Ch1a link to Ekalavya (IMSc Media Center)

video Ch1a link to YouTube (from IMSc Matsciencechanel Playlist)

video Ch1a link to bilibili

Tchebychev polynlomials 1st kind p.4 2:35

Fibonacci and Tchebychev polynomials 9 11:05

exercise: formula for the coefficients 15 20:03

Pascal triangle and Pingala 16-20 21:12

Tchebychev polynlomials 2nd kind 21 24:04

Lucas and Tchebychev polynomials 23 25:18

exercise: formula for the coefficients 29 31:55

Matching polynomials of a graph 30 33:31

definition of the matching polynomial 33 34:24

Hermite polynomials (as matching polynomial of the complete graph Kn 35 37:40

Hermite configurations 41 41:06

exercise: formula for the coefficients, 3-terms linear recurrence 44 46:15

Laguerre polynomials 45 48:04

exercise: formula for the coefficients 49 49:39

exercise: 3-terms linear recurrence 50 51:13

(formal) Orthogonal polynomials 51 52:08

definition of a sequence of (formal) orthogonal polynomials 54 56:10

moments of the Tchebychev polynomials 55 58:43

moments of the Hermite and Laguerre polynomials 56 1:00:46

Orthogonality and linearization coefficients of the Hermite polynomials 58 1:05:48

combinatorial interpretation of the linearization coefficients (Hermite) 61 1:09:06

expresssion for the linearization coefficients 67 1:14:22

the sign reversing involution phi 68-71 1:15:44

another "sign-reversing" proof without explicit construction of an involution 74-75 1:23:05

Orthogonality and linearization coefficients of the Laguerre polynomials 77 1:25:50

combinatoirial interpretation of the linearization coefficients (Laguerre) 79 1:26:13

The end 81 1:29:05

Chapter 1b Dyck paths and sign reversing involution for the linearization coefficients for Tchebychev polynomials II,

definition of formal orthogonality, moments and weighted Motzkin paths, Favard's theorem

January 17, 2019

slides of Ch1b (pdf 19 Mo)

video Ch1b link to Ekalavya (IMSc Media Center)

video Ch1b link to YouTube (from IMSc Matsciencechanel Playlist)

video Ch1b link to bilibili

Reminding Ch1a 3 0:30

More about linearization coefficients 17 8:39

generalized derangements 20 11:58

derangements 21 12:36

Complements. The power of bijective proof: the Askey-Wilson integral 23 15:24

Askey-Wilson polynomials 29 18:43

The Askey-Wilson integral 31 20:20

Linearization coefficients and orthogonality. Exemple: Tchebychev 2nd kind 34 24:39

paths: some notations 36 25:27

Dyck path: definition 37 26:31

The "essence" of the fundamental sign-reversing involutions 38 28:12

combinatorial interpretation of the integral of a product of Tchebychev polynomials 2nd kind 39 29:32

proof with the construction of a sign-reversing involution 42-58 33:34

Problem: linearization coefficients for the Tchebychef 1st kind ? 61 51:10

Orthogonal polynomials: some elementary lemma 61 53:07

Moments of some classical orthogonal polynomials 68 1:00:14

Favard's theorem, 3-terms linear recurrence relation and pavages 70 1:04:38

Favard's theorem 77 1:08:56

interpretation of the term linear recurrence with pavages of the segment graph 80-82 1:10:41

Moments and weighted Motzkin paths 83 1:14:46

weighted path: definition 85 1:15:35

weighted Motzkin paths: definition 86 1:16:19

Combinatorial proof of Favard's theorem 90 1:19:10

the main theorem 91 1:19:36

(proof in the next lecture Ch1c)

The end 96

Chapter 1c Bijective proof of Favard's theorem, the "main theorem", positivity of linearization coefficients with

De Médicis-Stanton's methodology, tridiagonal matrices

slides of Ch1c (pdf 13 Mo)

video Ch1c link to Ekalavya (IMSc Media Center)

video2 Ch1c (new) link to YouTube (from IMSc Matsciencechanel Playlist)

video Ch1c link to bilibili

Reminding Ch1b 2 0:24

Combinatorial proof of Favard's theorem: 3-terms recurrence relation implies orthogonality 9 5:52

the main theorem 10 5:58

corollary: Favard's therem 11 7:25

another version of the main theorem 13 8:04

bijective proof of the main theorem 16 10:54

construction of the sign-reversing involution theta 19 14:25

construction of the first sign-reversing involution theta1 25-42 16:50

the second involution theta2 43 30:57

end of the proof of the main theorem 47 32:07

the "essence" of the fundamental sign-reversing involutions 48-49 33:07

corollary: evaluation of the coefficients b_k and lamda_k 50-52 34:40

A bijective proof for the positivity of linearization coefficients 53 39:32

Askey positivity theorem 55 40:09

de Médicis - Stanton's theorem 59 40:59

definition of the map psi 60-64 48:38

two lemmae 67 52:41

definition: marked paths 68 53:10

an example of a weighted path 71-74 57:37

end of the proof of the de Médicis - Stanton's theorem 75 1:01:05

end of the bijective proof of Askey positivity theorem 76-80 1:02:25

Back to the proof of the main theorem 81 1:09:07

comparison between the proof with the sign-reversing involution theta1 and de Médicis-Stanton's theorem 87 1:10:24

Tridiagonal matrices 91 1:12:32

orthogonal polynomials as a determinant 98 1:18:54

The end 99 1:20:14

Chapter 1d Inverse polynomials, bijective proof of the inversion theorem, inverse relations for Tchebychev I, II,

first steps with the notion of histories: inverse relations for Stirling numbers I, II and Hermite polynomials, paths duality

January 24, 2019

slides of Ch1d (pdf 23 Mo) (version 2, with some corrections after the video: slides 21, 25, 127, 130)

video Ch1d link to Ekalavya (IMSc Media Center)

video Ch1d link to YouTube (from IMSc Matsciencechanel Playlist)

video Ch1d link to bilibili

Reminding Ch1c 3 0:27

Favard paths 18 8:15

Complements: other interpretation of the moments with heaps of monomers and dimers 22 13:11

Inverse polynomials 26 15:24

inverse polynomials: definition 28 16:04

vertical polynomials: definition 30 17:44

the inversion theorem 31 19:23

classical proof 32 20:22

bijective proof 34 23:38

Inverse relations: examples, Tchebychev I and II 37 26:37

some Riordan's inverse relations from "Combinatorial identities" (1968), ch2 38-40 26:51

inverse relations for Tchebychev polynomials 1st kind 42 30:02

nverse relations for Tchebychev polynomials 2nd kind 45 33:17

Inverse relations: exemples, Stirling numbers I and II 50 37:04

(idea) of histories for Stirling numbers 1st kind: bijection with partitions 52-62 38:32

(idea) of histories for Stirling numbers 2nd kind: bijection with permutations 64-74 42:55

Inverse relations: examples, symmetric functions 75 47:17

homogeneous (complete) symmetric functions 77-78 48:08

elementary symmetric functions 79-80 49:08

Duality of paths 81 51:40

Inverse relations: examples, Hermite polynomials and two kind of Hermite histories 91 56:07

Hermite histories II 94-103 59:08

Hermite histories I 109-121 1:03:06

Complements: some remarks about q-Hermite polynomials I and II 123 1:08:12

Complements: "beta-analogue" of Tchebychev 2nd kind 126 1:12:50

The end 131 1:18:57