XAVIER VIENNOT
  • Preface
    • Preface
    • Introduction
    • Lectures for wide audience
  • PART I
    • Preface
    • Abstract
    • Contents
    • Ch0 Introduction to the course
    • Ch1 Ordinary generating functions
    • Ch2 The Catalan garden
    • Ch3 Exponential structures and genarating functions
    • Ch4 The n! garden
    • Ch5 Tilings, determinants and non-intersecting paths
    • Lectures related to the course
    • List of bijections
    • Index
  • PART II
    • Preface
    • Abstract
    • Contents
    • Ch1 Commutations and heaps of pieces: basic definitions
    • Ch2 Generating functions of heaps of pieces
    • Ch3 Heaps and paths, flows and rearrangements monoids
    • Ch4 Linear algebra revisited with heaps of pieces
    • Ch5 Heaps and algebraic graph theory
    • Ch6 Heaps and Coxeter groups
    • Ch7 Heaps in statistical mechanics
    • Lectures related to the course
  • PART III
    • Preface
    • Abstract
    • Contents
    • Ch0 overview of the course
    • Ch1 RSK The Robinson-Schensted-Knuth correspondence
    • Ch2 Quadratic algebra, Q-tableaux and planar automata
    • Ch3 Tableaux for the PASEP quadratic algebra
    • Ch4 Trees and tableaux
    • Ch5 Tableaux and orthogonal polynomials
    • Ch6 Extensions: tableaux for the 2-PASEP quadratic algebra
    • Lectures related to the course
    • References, comments and historical notes
  • PART IV
    • Preface
    • Introduction
    • Contents
    • Ch0 Overview of the course
    • Ch1 Paths and moments
    • Ch2 Moments and histories
    • Ch3 Continued fractions
    • Ch4 Computation of the coefficients b(k) lambda(k)
    • Ch5 Orthogonality and exponential structures
    • Ch6 q-analogues
    • Lectures related to the course
    • Complements
    • References
  • Epilogue

The Art of Bijective Combinatorics    

Introduction 

Some lectures for a wide audience as an introduction to the Art of Bijective Combinatorics 

 

An introduction to enumerative and bijective combinatorics with binary trees

 

conference given for TESSELATE - STEMS 2021, CMI, Chennai, India, 9 January 2021 (via Zoom Internet)

abstract:

Trees and branching structures are everywhere in nature. Their mathematical abstraction leads to the notion of binary trees, a basic notion in computer science. The simple question "how many binary trees with n nodes", will give us the opportunity to travel from old and classical combinatorics to nowadays enumerative combinatorics. 

    Its « philosophy » can be summarized in the following:

« replacing calculus by figures and bijections, or conversely making calculus from the visual figures ».

 

 

slides_STEMS21  

slides_part I  (pdf, 36Mo)     slides_part II (pdf 22Mo)

video  link to YouTube  (1h35)

 

solutions to the 12 exercises  (pdf 6,8 Mo)

animation for exercise 7  (pdf  1,7 Mo)

animation for exercise 10  (pdf less than 1 Mo)

animation for exercise 11  (pdf les than 1 Mo)

  

 Description of the conference in details, with the page number of the slides and corresponding links sending directly in the video

First part of the talk 

 

Presentation by Aniruddhan Ganesaraman (CMI)     0:29

Trees in Nature   2     2:32   

From trees in Nature to mathematical trees   12     3:34

 trees everywhere in computer science with D; Knuth  20

Binary tree   21     4:26

definition

enumeration of binary trees: 1, 2, 5, 14

exercise 1   27     6:04

Some sequences ...  30     7:54

Fibonacci numbers, n! and permutations, prime numbers sequence

experimental combinatorics, guess a formula  35

the on-line encyclopedia of integer sequenes (oeis.org)   38

formula for Catalan numbers, Eugene Catalan   40

The arithmetical triangle (binomial coefficients)   43     13:53

"Pascal triangle", "Yang Hui triangle", Pingala in ancient  India

Bijective combinatorics, Catalan numbers   51     17:58

Injections, surjections, bijections ...   59     19:21

definitions, one-to-one correspondence, reverse bijection

Permutations   70     22:04

sub-exedante function, bijection with permutations

exercise 2   73     25:06

Binomial coefficient   76     25:33

proof of the formula for binomial coefficient

Increasing binary trees   80     27:06

exercise 3   83     27:43

Binomials coefficiens with paths   84     28:13

A bijective proof with binomial coefficients   91     32:04

exercise 4   94

Another bijective proof with binomial coefficients   95     33:57

matchings, Fibonacci numbers and binomials coefficients

exercise 5  a)  98     35:37   b)   99     36:01  

Pingala and meters in Sanskrit

At the primary school .... additions, subtractions, divisions   101     37:26

playing with the arithmetical triangle

exercise 6   109     40:56

At the primary school: additions   109     41:20

"the Catalan triangle"

Binary trees and Dyck paths   114

the bijection binary trees --- Dyck paths (with violins)  118     43:34

exercise 7   121     45:06

At the prilmary school: subtractions, the reflexion principle   122     45:35

exercise 8 "ballot numbers"  128-129     49:08

Arbogast triangle (1800)   130

At the primary school: divisions   131     51:08

execise 9   multiplicative recurrence relation for Catalan numbers 135   52:19

Bijective proof for the multiplicative recurrence relation of Catalan numbers   136

exercise 10   144     55:30

images of random binary tree and increasing binary tree  145    56:25

 

Second part of the talk

 

Analytic proof   2     58:37

Formal power series   6     1:01:57

Analytic proof with formal power series   18     1:04:46

Modern combinatorics: operations on combinatorial objects   23     1:07:49

The bijective paradigm   28     1:10:00

Lagrange and figures   

"replacing calculus by figures and bijections"

an identity with Ramanujan continued fraction   32   1:11:25

bijection Dyck paths --- heaps of dimers (pyramids)  (with violin)  36  1:13:24

conversely, "making calculus from the visual figures"   38

Feynman diagrams and binary trees   42    1:14:56

Triangulations of a convex polygon   45     1:15:30

A letter from Leonhard Euler to Christian Goldbach (1751)   49     1:15:59

bijection triangulations --- binary trees (with violins)  54     1:17:13

exercise 11 reverse bijection   61     1:18:44

Relation with physics of dynamical systems: the TASEP   62     1:18:48

execise 12   75     1:22:14

A final surprise ...

molecular biology, computer science, hydrogeology  76     1:22:34

molecular biology: trees in RNA secondary structures        

forest of planar trees

complexity of the forest of planar trees underlhying the RNA molecule

minimum number of registers needed to commpute an arithmetical 

expression

hydrogeology: Strahler number of a binary tree

3 identical generating functions, relation with the arithmetical triangle and Fibonacci numbers

Thank you !   94     1:27:44

Saraswati, the godess of knowledge, art and science   95     1:28:17

some questions     1:28:34

the end     1:35:23