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)

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)

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

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