Introduction Our work
Counting smaller trees in the Tamari order
Gr´ egory Chatel, Viviane Pons
March 25, 2013
Introduction Our work
1 Introduction Basic definitions Tamari lattice Goal
2 Our work Main result Example
Sketch of our proof
Introduction Our work
Basic definitions Tamari lattice Goal
Permutations and the weak order
Permutations
A permutation σ is a word of size n where every letter of {1, . . . , n} appear only once.
Ex : 1234, 15234, 4231.
Weak order: partial order on permutations
At each step, we exchange two increasing consecutives values.
123 213 132
231
312
Introduction Our work
Basic definitions Tamari lattice Goal
Binary trees
Binary trees
•
•
•
• •
•
•
•
•
• •
• •
Canonical labelling
x
5 1
3
1 7
Introduction Our work
Basic definitions Tamari lattice Goal
From permutations to binary trees
The binary search tree insertion
15324 →
4
2
1 3
5
Introduction Our work
Basic definitions Tamari lattice Goal
From permutations to binary trees
The binary search tree insertion
15324 →
4 2
1 3
5
Introduction Our work
Basic definitions Tamari lattice Goal
From permutations to binary trees
The binary search tree insertion
15324 →
4 2
1
3
5
Introduction Our work
Basic definitions Tamari lattice Goal
From permutations to binary trees
The binary search tree insertion
15324 →
4 2
1
3
5
Introduction Our work
Basic definitions Tamari lattice Goal
From permutations to binary trees
The binary search tree insertion
15324 →
4 2
1 3
5
Introduction Our work
Basic definitions Tamari lattice Goal
Order relation
Right rotation
x y
A B
C →
x A y
B C
This gives an order relation on binary trees.
Example
4 4
4
Introduction Our work
Basic definitions Tamari lattice Goal
The Tamari lattice
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
• •
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
• •
•
•
• •
•
•
•
•
•
•
•
Figure: The Tamari lattices of size 3 and 4.
Introduction Our work
Basic definitions Tamari lattice Goal
The Tamari lattice as a quotient of the weak order
123 213 132
231 312
1 2
3
1 2
3 1
2 3
1
2 3
1 2
2 4
5
13254
31254 13524
31524 15324
35124 51324
Introduction Our work
Basic definitions Tamari lattice Goal
Our objective
Goal
We want a formula that computes, for any given tree T the number of trees smaller than T in the Tamari order.
Example : how many trees are smaller than or equal to this one ?
1 2 3
4
5
6
Introduction Our work
Main result Example Sketch of our proof
1 Introduction Basic definitions Tamari lattice Goal
2 Our work Main result Example
Sketch of our proof
Introduction Our work
Main result Example Sketch of our proof
Tamari polynomials
Tamari polynomials
Given a binary tree T , we define:
B ∅ := 1 (1)
B T (x ) := x B L (x ) x B R (x ) − B R (1)
x − 1 (2)
with T =
L
•
R
Introduction Our work
Main result Example Sketch of our proof
Main theorem
Theorem
Let T be a binary tree. Its Tamari polynomial B T (x) counts
the trees smaller than or equal to T in the Tamari order
according to the number of nodes on their left border. In
particular, B T (1) is the number of trees smaller than T .
Introduction Our work
Main result Example Sketch of our proof
Example
B ∅ := 1
B T (x ) := x B L (x ) x B R (x ) − B R (1) x − 1
1 2 3
4
5
6
Introduction Our work
Main result Example Sketch of our proof
Example
B ∅ := 1
B T (x ) := x B L (x ) x B R (x ) − B R (1) x − 1
1 2 3
4
5 6
• B T (x ) = B 4 (x) = xB 3 (x ) xB
6(x)−B x−1
6(1)
• B 3 (x ) = x B 1 (x )
• B 1 (x ) = x xB
2(x)−B x−1
2(1)
• B 2 (x ) = x
• B 1 (x ) = x (1 + x ) = x + x 2
• B 3 (x ) = x (x + x 2 ) = x 2 + x 3
Introduction Our work
Main result Example Sketch of our proof
Example
B ∅ := 1
B T (x ) := x B L (x ) x B R (x ) − B R (1) x − 1
1 2 3
4
5 6
• B T (x ) = B 4 (x) = xB 3 (x ) xB
6(x)−B x−1
6(1)
• B 3 (x ) = x B 1 (x )
• B 1 (x ) = x xB
2(x)−B x−1
2(1)
• B 2 (x ) = x
• B 1 (x ) = x (1 + x ) = x + x 2
• B 3 (x ) = x (x + x 2 ) = x 2 + x 3
Introduction Our work
Main result Example Sketch of our proof
Example
B ∅ := 1
B T (x ) := x B L (x ) x B R (x ) − B R (1) x − 1
1 2 3
4
5 6
• B T (x ) = B 4 (x) = xB 3 (x ) xB
6(x)−B x−1
6(1)
• B 3 (x ) = x B 1 (x )
• B 1 (x ) = x xB
2(x)−B x−1
2(1)
• B 2 (x ) = x
• B 1 (x ) = x (1 + x ) = x + x 2
• B 3 (x ) = x (x + x 2 ) = x 2 + x 3
Introduction Our work
Main result Example Sketch of our proof
Example
B ∅ := 1
B T (x ) := x B L (x ) x B R (x ) − B R (1) x − 1
1 2 3
4
5 6
• B T (x ) = B 4 (x) = xB 3 (x ) xB
6(x)−B x−1
6(1)
• B 3 (x ) = x B 1 (x )
• B 1 (x ) = x xB
2(x)−B x−1
2(1)
• B 2 (x ) = x
• B 1 (x ) = x (1 + x ) = x + x 2
• B 3 (x ) = x (x + x 2 ) = x 2 + x 3
Introduction Our work
Main result Example Sketch of our proof
Example
B ∅ := 1
B T (x ) := x B L (x ) x B R (x ) − B R (1) x − 1
1 2 3
4
5 6
• B T (x ) = B 4 (x) = xB 3 (x ) xB
6(x)−B x−1
6(1)
• B 3 (x ) = x B 1 (x )
• B 1 (x ) = x xB
2(x)−B x−1
2(1)
• B 2 (x ) = x
• B 1 (x ) = x (1 + x ) = x + x 2
• B 3 (x ) = x (x + x 2 ) = x 2 + x 3
Introduction Our work
Main result Example Sketch of our proof
Example
B ∅ := 1
B T (x ) := x B L (x ) x B R (x ) − B R (1) x − 1
1 2 3
4
5 6
• B T (x ) = B 4 (x) = xB 3 (x ) xB
6(x)−B x−1
6(1)
• B 3 (x ) = x B 1 (x )
• B 1 (x ) = x xB
2(x)−B x−1
2(1)
• B 2 (x ) = x
• B 1 (x ) = x (1 + x ) = x + x 2
• B 3 (x ) = x (x + x 2 ) = x 2 + x 3
Introduction Our work
Main result Example Sketch of our proof
Example
B ∅ := 1
B T (x ) := x B L (x ) x B R (x ) − B R (1) x − 1
1 2 3
4
5
6 • B T (x ) = B 4 (x) = x(x 2 + x 3 ) xB
6(x)−B x−1
6(1)
• B 6 (x ) = x B 5 (x )
• B 5 (x ) = x
• B 6 (x ) = x · x = x 2
Introduction Our work
Main result Example Sketch of our proof
Example
B ∅ := 1
B T (x ) := x B L (x ) x B R (x ) − B R (1) x − 1
1 2 3
4
5
6 • B T (x ) = B 4 (x) = x(x 2 + x 3 ) xB
6(x)−B x−1
6(1)
• B 6 (x ) = x B 5 (x )
• B 5 (x ) = x
• B 6 (x ) = x · x = x 2
Introduction Our work
Main result Example Sketch of our proof
Example
B ∅ := 1
B T (x ) := x B L (x ) x B R (x ) − B R (1) x − 1
1 2 3
4
5
6 • B T (x ) = B 4 (x) = x(x 2 + x 3 ) xB
6(x)−B x−1
6(1)
• B 6 (x ) = x B 5 (x )
• B 5 (x ) = x
• B 6 (x ) = x · x = x 2
Introduction Our work
Main result Example Sketch of our proof
Example
B ∅ := 1
B T (x ) := x B L (x ) x B R (x ) − B R (1) x − 1
1 2 3
4
5
6 • B T (x ) = B 4 (x) = x(x 2 + x 3 ) xB
6(x)−B x−1
6(1)
• B 6 (x ) = x B 5 (x )
• B 5 (x ) = x
• B 6 (x ) = x · x = x 2
Introduction Our work
Main result Example Sketch of our proof
Example
B ∅ := 1
B T (x ) := x B L (x ) x B R (x ) − B R (1) x − 1
1 2 3
4
5 6
• B 4 (x ) = x (x 2 + x 3 )(1 + x + x 2 )
• B 4 (x ) = x 6 + 2x 5 + 2x 4 + x 3
Introduction Our work
Main result Example Sketch of our proof
Example
B ∅ := 1
B T (x ) := x B L (x ) x B R (x ) − B R (1) x − 1
1 2 3
4
5 6
• B 4 (x ) = x (x 2 + x 3 )(1 + x + x 2 )
• B 4 (x ) = x 6 + 2x 5 + 2x 4 + x 3
Introduction Our work
Main result Example Sketch of our proof
Example
1 2 3
4
5 6
•
••
•
••
••
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
••
•
••
•
••
•
••
Introduction Our work
Main result Example Sketch of our proof
Sketch of our proof
Increasing and decreasing forests
4
2 5
1 3 9
7
6 8
Introduction Our work
Main result Example Sketch of our proof
Sketch of our proof
Increasing and decreasing forests
4
2 5
1 3 9
7
6 8
Introduction Our work
Main result Example Sketch of our proof
Sketch of our proof
Increasing and decreasing forests
4
2 5
1 3 9
7
6 8
1 2
3
4 5
6 7 9
8
Introduction Our work
Main result Example Sketch of our proof
Sketch of our proof
Increasing and decreasing forests
4
2 5
1 3 9
7
6 8
4
2 3
1
5 9
7 8
6
Introduction Our work
Main result Example Sketch of our proof
Initial and final intervals as linear extensions
1 2
3
1 2
3 1
2 3
1
2 3
1 2
3
1
2 3
123 213 132
231 312
321
Introduction Our work
Main result Example Sketch of our proof
Initial and final intervals as linear extensions
1 2
3
1 2
3 1
2 3
1
2 3
1 2
3
1 2 3
123 213 132
231 312
321
Introduction Our work
Main result Example Sketch of our proof
Initial and final intervals as linear extensions
1 2
3
1 2
3 1
2 3
1
2 3
1 2
3
1
2 3
123 213 132
231 312
321
Introduction Our work
Main result Example Sketch of our proof
Linear extensions of any interval
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
• •
•
•
•
•
•
Introduction Our work
Main result Example Sketch of our proof
Linear extensions of any interval
•
•
•
•
•
•
•
•
•
•
•
• •
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
• •
•
•
• •
•
•
•
•
•
•
•
1
2 3
4
Introduction Our work
Main result Example Sketch of our proof
Linear extensions of any interval
•
•
•
•
•
•
•
•
•
•
•
• •
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
• •
•
•
• •
•
•
•
•
•
•
•
1 2
3
4
Introduction Our work
Main result Example Sketch of our proof
Linear extensions of any interval
•
•
•
•
•
•
•
•
•
•
•
• •
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
• •
•
•
• •
•
•
•
•
•
•
•
1
2 3
4
Introduction Our work
Main result Example Sketch of our proof
Sketch of proof
Back to the functional equation
B T (x ) = xB L (x) x B R (x ) − B R (1) x − 1
Since it is defined on binary trees, see it as bilinear map.
B(f , g ) = xf (x ) xg(x ) − g(1)
x − 1
Introduction Our work
Main result Example Sketch of our proof
Sketch of proof
Combinatorial interpretation of B
Lift the bilinear map to take intervals as arguments.
X
T
0≤T
[T 0 , T ] = B ( X
L
0≤L
[L 0 , L], X
R
0≤R
[R 0 , R ])
with T =
L
•
R
Introduction Our work
Main result Example Sketch of our proof
Definition of B on an example
B (
1 2
3
, 2
1 3
) =
1 2
3
4
1 2
3
+ 1 2
3 4
5 6
7
+ 1 2
3 4
5 6
7
Introduction Our work
Main result Example Sketch of our proof
Definition of B on an example
B (
1 2
3
, 2
1 3
) =
1 2
3 4
5 6
7
+ 1 2
3 4
5 6
7
+ 1 2
3 4
5 6
7
Introduction Our work
Main result Example Sketch of our proof
Definition of B on an example
B (
1 2
3
, 2
1 3
) =
1 2
3 4
5 6
7
+ 1 2
3 4
5 6
7
+ 1 2
3 4
5 6
7
Introduction Our work
Main result Example Sketch of our proof
Definition of B on an example
B (
1 2
3
, 2
1 3
) =
1 2
3 4
5 6
7
+ 1 2
3 4
5 6
7
+ 1 2
3 4
5 6
7
Introduction Our work
Main result Example Sketch of our proof
Definition of B on an example
B (
1 2
3
, 2
1 3
) =
1 2
3 4
5 6
7
+ 1 2
3 4
5 6
7
+ 1 2
3 4
5 6
7
Introduction Our work
Main result Example Sketch of our proof
1 2 3
4 5
6
B ( 3
1 2 +
3 1
2
, 2
1 )
[
3 2 1
, 3
2
1 ] [
3
2
1 ,
3
2
1 ] [ 2
1
, 2
1 ]
Introduction Our work
Main result Example Sketch of our proof
B ( 3
1 2 +
3 1
2
, 2
1 ) = 4
3 1 2
6 5
+
4 3 1 2
6 5
+
4 3 1 2
6 5
4 3 6
4 3 6
4
3 6
Introduction Our work
Main result Example Sketch of our proof
4 3 1 2
6 5
+
4 3 1 2
6 5
+
4 3 1 2
6 5
+ 4 3 1 2
6
5 +
4 3 1 2
6
5 +
4 3 1 2
6
5
Introduction Our work
Main result Example Sketch of our proof
