Courses  X.V.


Courses  Talca, Chile 2010/2011

Cours  Universidad de Talca

  (December 2010 - January  2011)

Combinatorics and interactions (with  physics)

        «The Cellular  Ansatz»   (24 h)

plan  of  the classes  (pdf)

some references:

A paper( in french) introducing enumerative, algebraic, bijective ... combinatorics from elementary to recent researches,    LMA3.Viennot.v4.pdf

“Enumérons ! (De la combinatoire énumérative classique aux nouvelles combinatoires : bijective, algébrique, expérimentale, quantique et … magique)”, article dans “Leçons de mathématiques d’aujourd’hui ”, vol 3,  éds. Eric Charpentier et Nicolas Nikolski,  Cassini, Paris, 2007, pp 165-238.

  1. -A complete text  (in french) with more informations, covering Ch1 and Ch2 of the Talca course. (160p), see my first website at the page «cours», the lecture Notes 1988  «séries génératrices énumératives»

  1. - A  survey (in 1984)  of the Robinson-Schensted correspondence: 

Chain and antichain families, grids and Young tableaux, Annals of Discrete Maths., 23 (1984) 409-464.

- A survey (in french) about combinatorial interpretations of Euler and Genocchi numbers, with some introduction to basic bijections for combinatorics:

   Interprétations combinatoires des nombres d’Euler et de Genocchi  (pdf, 9,2 Mo)  Séminaire de Théorie des nombres de Bordeaux, Publi. de l’Université Bordeaux I, 1982-83, 94p.

Ch 0  Introduction  

        1 december  2010  (pdf 4,1 Mo)

Ch1a  Ordinary  generating functions,  the Catalan garden

            1 december  2010  (pdf  6 Mo, 54 p.)

Binary trees p.2

ordinary generating functions, formal power series  p.11

formal power series algebra, formalisation  p.25

operations on combinatorial objects, example: binary trees  p.37

bijective combinatorics, example: Catalan numbers  p.44

Dyck paths  p.52

Ch1b  Ordinary  generating functions,  the Catalan garden      

            7 december  2010  (pdf  10,8 Mo, 81p.)

Leonhard Euler and Catalan numbers  p.4

from triangulations to binary trees  p.10

from binary trees to Dyck paths  p.17

binary trees, complete binary trees  p.21

chord diagrams  p.24

parallelogram polyominoes  (staircase polygons), 2-colored Motzkin paths  p.27

operations on combinatorial objects, example: integers partitions, q-series  p.33

operations on combinatorial objects: formalisation  p.49

bijective proof of an identity, the "bijective paradigm"  p.56

algebricity, decomposable structures, example: planar maps  p.67

directed animals  p.73

Ch1c  The Catalan garden,  algebraic complements in relation with physics

             7 december  2010  (pdf  2,8 Mo, 30 p.)

the associahedron  p.2

the Temperley-Lieb algebra  p.7

Ch 2a  Exponential generating functions, permutations         

        22 december 2010  (pdf  12,2 Mo, 40 p.)

permutations: classical combinatorics  p.2

inversion table, q-analogue  p.10

increasing binary trees  p.17

exponential generating functions, species and (exponential) structures  p. 29

operations on species, exponential structures  p.37

Ch 2b  Exponential generating functions, permutations

            4 january 2011 (pdf  8,2 Mo, 63 p.)

operations on species: exp, log, substitution  p.3

Striling numbers and binomial type polynomials  p.9

differential equations  p.12

weighted species  p.26

examples: orthogonal polynomials  p.30

Mehler identity for Hermite polynomials  p. 45

complements p.58

Ch 2c  Permutations and Laguerre histories

          4 january 2011  (pdf  2,5 Mo, 33 p.)

weighted paths  p.2

Laguerre histories  p.7

bijection Laguerre histories - permutations  p.12

Ch 3a  Permutations  and  Young tableaux:

        the Robinson-Schensted correspondence

               6 january 2011    (pdf  13,5 Mo, 117 p.)

Young tableaux  p.2

Hook length formula  p.7

Introduction to RSK p.16

RSK  with Schensted's insertions p.22

A geomeric version of RSK with "light" and "shadow lines" p.48

proof of the equivalence insertions - geometric construction p.716

"jeu de taquin"  p.78

increasing and decreasing subsequences  p.107

Ch 3b  The  Robinson-Schensted correspondence with operators

               6,  11  january 2011    (pdf  6,2 Mo, 121 p.)

"local" algorithms on a grid or "growth diagrams"  p.2

Heisenberg operators  UD = qDU + I, normal ordering   p.9

representation of the operators U and D  p.41

RSK with Fomin's "local rules"  p.55

local RSK and geometric RSK  p.64

alternating sign matrices (ASM) and a quadratic algebra  p.84

Ch 4a  Alternative tableaux and the PASEP          

             (partially asymmetric exclusion process)

              13  january 2011    (pdf  6 Mo, 98 p.)

The PASEP  p.2

The matrix Ansatz of  Derrida, Evans, Hakim, Pasquier  p.19

The PASEP algebra DE = qED + E + D,  p.26

alternative tableaux  p.50

stationary probabilities for the PASEP  p.61

permutation tableaux  p.64

PASEP  and orthogonal polynomials  p.89

references  p.92

Ch 4b   Alternative tableaux and the PASEP 

            the bijection alternative tableaux -- permutations

            13,  18  january 2011    (pdf  9,8 Mo, 102 p.)

the "exchange-fusion" algorithm p.2

the inverse "exchange-fusion" algorithm  p.21

Genocchi sequence of a permutation  p.36

some parameters  p.43

"q-analogue" of Laguerre histories  p.53

the cellular Ansatz: from the PASEP algebra DE = ED + E +D  to bijections  p.61

representation of the operators E and D with DE = ED + E +D  p.63

the cellular Ansatz: bijection permutations - alternative tableaux  p.74

the inverse bijection permutations - alternative tableaux  p.90

two bijections, one theorem  p.98

Ch 4c   Alternative tableaux and the PASEP

                complements  18  january 2011    (pdf  2,2 Mo, 81 p.)

the "exchange-deletion" algorithm  p.2

an alternative "jeu de taquin" p.20

the same example denoted with the inverse permutation  p.37

proof of the main theorem  p.52

Postnikov's bijection permutation tableaux - permutations  p.76

The seminal paper of Derrida, Evans, Hakim and Pasquier on the Matrix Ansatz for the PASEP


            A   «video-preprint»  by XGV  introducing Alternative tableaux 

                (Isaac Newton Institute, 23 April 2008)

Ch 5    Combinatorial  theory  of orthogonal  polynomials  

            20 january 2011  (pdf  11,7 Mo, 110 p.)  

some trigonometry  p.2

combinatorial interpretations of some orthogonal polynomials  p.9

formal orthogonal polynomials: definition, moments  p.15

Favard theorem  p.25

3-terms recurrence relation and pavages  p.27

moments and weigthed Motzkin paths  p.32

Laguerre histories  p.38

data structures histories  p.48

quadratic algebra operators and orthogonal polynomials  p.56

q-analogues of Hermite and Laguerre polynomials  p.78

PASEP and orthogonal polynomials  p.84

combinatorial proof of identities  p.89

the Askey-Wilson integral  p.91

continued fractions  p.97


Ch 6a   Jeu de taquin for binary trees, Catalan tableaux and the TASEP

            24  january 2011    (pdf  7,1 Mo, 98 p.)  

Catalan alternative tableaux  p.2

bijection Catalan alternative tableaux - binary trees  p.11

TASEP and Catalan alternative tableaux  p.29

Catalan permutation tableaux  p.42

caracterisation of  Catalan alternative tableaux  p.47

TASEP with Catalan tableaux, realtion with Shapiro-Zeilberger interpretation  p.60

other description of the bijection binary trees - pair of paths  p.80

Ch 6b   Tableaux and increasing / alternative binary trees

            24  january 2011    (pdf  6,3 Mo, 111p.) 

increasing binary trees: canopy and up-down sequence  p.2

"jeu de taquin" for increasing binary trees  p.13

from "jeu de taquin" for increasing binary trees to Catalan alternative tableaux p.30

alternative binary trees p.50

"jeu de taquin" for alternative binary trees  p.57

the twisted symmetric order  p.82

complements  p.86

the "exchange-fusion" algorithm in the Catalan case  p.87

Bernardi permutations  p.103

Ch 6c    Catalan tableaux and the Loday-Ronco algebra

            24  january 2011    (pdf  2,1 Mo, 21 p.) 

Hopf algebras: Malvenuto-Reutenauer, Loday-Ronco, descents algebra  p.2

Loday-Ronco product of binary trees with Catalan alternative tableaux  p.4

proof of the equivalence of the two products  p.10

the # product for binary trees  p.18


    2 talks by J.-C. Aval on Hopf algebra, alternative Catalan tableaux and Loday-Ronco algebra

   LR1.pdf            LR2.pdf

Ch 7a    The cellular  Ansatz

            25  january 2011    (pdf  8,7 Mo, 117 p.)

Q-tableaux  p.2

Q-tableaux: exemples  p.11

planar automata  p.32

"figures" accepted by planar automata ?  p.38

the 8-vertex algebra  (or Z-algebra, or  XYZ-algebra)  p.43

rhombus tiling  p.46

Aztec diamond  p.61

geometric interpretation of Z-tableaux  p.68

non-intersecting paths  p.72

bijection plane partitions -- non-intersecting paths  p.75

osculating paths  p.83

fully packed loops  (FPL)  p.90

configurations B.A.BA  p.105

Z-tableaux  and configurations B.A.BA  p.113

Ch 7b    The cellular Ansatz

            complements   25  january 2011    (pdf  4,7 Mo, 49 p.)

symmetries for plane partitions  p.3

totaly symmetric sef-complementary plane partitions (TSSCPP) p.12

Razumov-Stroganov (ex)-conjecture  p.20

8-vertex model , analog of Razumov-Stroganov conjecture ?  p.35

some bijections p.36