CoursE  X.V.  IMSc  2016

 
 

Course  IMSc  Chennai, India 

January-March 2016

An introduction to enumerative, algebraic and

bijective combinatorics



Ch 4   The   n!  garden


        16  February 2016

                                slides_Ch4a    (pdf  18 Mo)       video Ch 4a     (1h 26mn)


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’’

                                             

          18  February 2016

                                    slides_Ch4b      (pdf  23 Mo)      video Ch4b    (1h 18mn)


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  1h  10’  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’’


23 February 2016

                    slides_Ch4c   (pdf  30Mo)               video_Ch4c       (1h 13mn)


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)  1h  8’  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


25 February 2016

                               slides_Ch4d     (pdf 14 Mo)           video Ch4d


«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’’  video

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  1h  12’  0’’  video

        stationary probabilities with alternative tableaux  10  1h  15’  50’’  video

        permutations tableaux  11  1h  17’  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’’



last update: 13  April 2016


return to:

courses  website

main Xavier Viennot  website