The Art of Bijective Combinatorics Part I
An introduction to enumerative, algebraic and bijective combinatorics
The Institute of Mathematical Sciences, Chennai, India (January-March 2016)
Ch 4 The n! garden
Ch 4a
16 February 2016
slides_Ch4a (pdf 18 Mo)
video Ch4a link to youTube (1h 26mn)
video Ch4a link to bilibili
permutations (very) classic 3 0’ 28’‘ video
the bijection cycles -- left to right minimum elements 7 3’ 30’‘ video
exercise: analysis of the algorithm finding the minimum of a sequence 12 8’ 7’‘ video
rises and descents 16 12‘ 31’‘ video
exercise: Frobenius formula relating Eulerian polynomials and Stirling numbers 17 14’ 32’‘ video
excedances 18 16’ 2’‘ video
up-down sequences of a permutation 21 19’ 32’‘ video
exercise: algorithm computing the number of permutation with given up-down sequence 22 20’ 33’‘ video
inversion table, q-analogue 23 24’ 29’‘ video
sub-excedant functions 24 24’ 42’‘ video
q-analogue of n! 25 25’ 51’‘ video
Rothe diagram 28 29‘ 1’‘ video
inversion table of a permutation 29 29’ 50’‘ video
reverse bijection and q-analogue of histories 33 32’ 47’‘ video
the maj index 50 38’ 51’‘ video
q-histories for the maj index 52-72 40’ 34’‘ video
the philosophy of «histories» and its q-analogs 46’ 11’‘ video
increasing binary trees 74 48’ 05’‘ video
projection of an increasing binary tree 75 48’ 23’‘ video
«déployé» of a permutation 76 49’ 24’‘ video
x-factorisation 77 50’ 24’‘ video
peaks, valleys, double-rises, double-descents 79 54’ 13’‘ video
lr-min, rl-min elements and left and right branches in increasing binary trees 86 56’ 39’‘ video
exercise: hook length formula for increasing binary trees 90 58’ 15’‘ video
exercise: déployé of uv from the knowledge of the déployés of u and v 91 59‘ 55’‘ video
exercise: canopy and up-down sequence 92 1h 1’ 33’‘ video
assemblée of increasing arborescences 95 1h 3’ 35’‘ video
exercise: 1-2 increasing arborescences 97 1h 6’ 52’‘ video
exercise: Jacobi permutations 98 1h 8’ 5’‘ video
computer science: binary search trees 103 1h 13’ 27’‘ video
from a permutation to a binary search tree 104-112 1h 13’ 40’‘ video
analysis of the insertion in a binary search tree 115 1h 16’ 47’‘ video
the end 121 1h 26’ 38’’
Ch 4b
18 February 2016
slides_Ch4b (pdf 23 Mo)
video Ch4b link to YouTube (1h 18mn)
video Ch4b link to bilibili
Laguerre histories 3 0’ 26’‘ video
Laguerre histories: definition 0’ 32’’ video
bijection Laguerre histories -- permutations: description with binary trees 11-21 4’ 29’’ video
bijection Laguerre histories -- permutations: description with with words 23-33 9’ 0’’ video
reciprocal bijection permutations -- Laguerre histories 34 12’ 57’‘ video
x-decomposition of a permutation 36 14‘ 25’’ video
description with the pattern (31-2) 40 18‘ 52’‘ video
relation with (formal) orthogonal polynomials 41 24’ 53’’ video
definition of a sequence of orthogonal polynomials 42 25’ 21’’ video
moments 43 26’ 59’’ video
Favard theorem 44 27’ 43’‘ video
interpretation of the moments with weighted Motzkin paths 45-47 29’ 51’’ video
Laguerre histories and moments of Laguerre polynomials 48 31’ 57’’ video
weighted Laguerre histories 54 35’ 37’’ video
Laguerre polynomials with weight alpha 55 36’ 10’’ video
restricted Laguerre histories 60 41’ 16’’ video
moments with weight beta 66 43’ 53’’ video
bijection for beta=2 67 44’ 04’‘ video
Hermite histories 68 44’ 27’’ video
moments for Hermite polynomials 69 44’ 47’’ video
Hermite histories: definition 70 45’ 44’‘ video
bijection Hermite histories -- chord diagrams 72-77 47’ 36’‘ video
q-analogues of Hermite histories 78 50’ 31’’ video
nestings 80-84 51’ 49’‘ video
crossings 85-86 52’ 58’’ video
exercise: symmetry of the (q,t) polynomials crossings-nestings 89 54’ 51’‘ video
q-analogues of Laguerre histories 90 55’ 30’‘ video
complements: q-Hermite and q-Laguerre II 95 59’ 9’’ video
moments of q-Laguerre II 96 59’ 17’’ video
moments of q-Laguerre I 98 1h 1’ 33’‘ video
relation with the PASEP model in physics 99 1h 1’ 52’’ video
moments of q-Hermite I 100 1h 3’ 30’’ video
moments of q-Hermite II 101 1h 4’ 12’’ video
the philosophy of «histories» and its q-analogues 1h 4’ 37’’ video
complements: Laguerre histories and Scheffer orthogonal polynomials 103 1h 6‘ 48’’ video
complements: Baxter permutations107 1h10’ 8’’ video
bijective proof for the number of Baxter permutations using Laguerre histories 111-116 1h 12’ 22’’ video
triple of non-intersecting paths 117-122 1h 15’ 25’’ video
the end 124 1h 18’ 48’’
Ch 4c
23 February 2016
slides_Ch4c (pdf 30Mo)
video Ch4c link to YouTube (1h 13mn)
video Ch4c link to bilibili
Young tableaux 3 50’’ (image is coming only after 1’ 10’’) video
Hook-length formula 8 2’ 34’’ video
An introduction to RSK 17 5’ 7’’ video
RSK with Schensted insertions 23 10’ 18’’ video
the group of permutations 48 16’ 16’’ video
a geometric version of RSK with «light» and «shadow lines» 52 17’ 35’’ video
some exercises 76 24’ 59’’ video
more about group theory (representation theory) 82 30’ 47’’ video
proof of the equivalence insertion -- geometric construction 88 35’ 55’’ video
jeu de taquin 95 (see Ch4c complements 2) 39’ 36’’ video
duality 96 (see Ch4c complements 9) 47’ 16’’ video
increasing and decreasing sequences 97 53‘ 54’’ video
Knuth’s transposition 107 (see Ch4c complements 55) 59’ 48’’ video
plactic monoid 108 (see Ch4c complements 60) 1h 2’ 40’‘ video
Schur fonctions 109 (see Ch4c complements 68) 1h8’ 35’‘ video
the end 110 1h 13 14
complements to Ch 4c
slides_Ch4c-complements (pdf 17 Mo)
jeu de taquin 2 40’ 7’’ video
duality 9 47’16’’ video
dual of a Young tableau 19 49’ 48’’ video
Knuth’s transpositions 55 59’ 48’’ video
plactic monoid 60 1h 2’ 40’’ video
Schur functions 68 1h 8’ 35’’ video
the end 74 1h 13 14
Ch 4d
25 February 2016
slides_Ch4d (pdf 14 Mo)
video Ch4d link to YouTube
video Ch4d link to bilibili
«local» algorithms on a grid or «growth diagrams» 3 0’ 35’’ video
posets and the Young lattice 12-15 11’ 56’’ video
proof of the equivalence local RSK and geometric RSK 28 19’ 57’‘ video
complement: combinatorial representation of the algebra UD=DU+Id 45 30’ 30’’ video
oscillating tableaux 51 37’ 16’’ video
bijection oscillating tableaux - rook placements - Hermite histories - chords diagram 52-55 38’ 1’’ video
«2-colored oscillating tableaux» 56 49’ 57’’ video
rooks placements on a staircase and set partitions 58 56’ 10’’ video
vacillating and hesitating tableaux 62 59’ 16’’ video
RS to RSK, extensions to matrices 63 1h 2’ 17’’ vide
some bibliography about RSK 73 1h 9’ 49’’ video
the end 76 1h 10’ 43’’ video
complements to Ch 4d
slides_Ch4d-complements (pdf 17 Mo)
the PASEP (Partially asymmetric exclusion model) 2 1h 10’ 43’’ video
alternative tableaux 4-5 1h12’ 0’’ video
stationary probabilities with alternative tableaux 10 1h15’ 50’’ video
permutations tableaux 11 1h17’ 25’’ video
q-Laguerre 14 1h 20’ 31’‘ video
(the philosophy of) the cellular ansatz 18 1h 22’ 52’’ video
complements for Ch 2 and Ch 4:
posets and lattices: 2^n, Catalan, n! 19 1h 24’ 2’‘ video
Boolean lattice 22 1h 24’ 22’’ video
Canopy, increasing binary tree, permutations and up-down sequences 23 1h 24‘ 50’‘ video
weak Bruhat order on permutations 24 1h 25’ 9’’ video
Tamari lattice 26 1h 26’ 41’’ video
definition with binary trees 27 1h 26’ 45’’ video
Boolean, Tamari and permutations lattice 30-33 1h 28’ 35’’ video
Tamari lattice with Dyck paths 34 1h 29’ 44’’ video
Tamari lattice with triangulations 41 1h 30’ 26’’ video
realization of the associahedron (as a convex polytope) 44 1h 30’ 58’‘ video
Loday’s realisation with binary trees 46 1h 31’ 32’‘ video
3 geometric structures: hypercube, associahedron and permutahedron 51 1h 33’ 41’’ video
the end 58 1h 34’ 42’’