1 / 28
On permutation tableaux of type A and B
Jang Soo Kim
(Joint work with Sylvie Corteel) University of Paris 7 64th SLC, Lyon, March 30, 2010
2 / 28
Permutation tableaux
First introduced by Postnikov in his study of totally nonnegative Grassmanian.
2 / 28
Permutation tableaux
First introduced by Postnikov in his study of totally nonnegative Grassmanian.
There are many bijections between permutation tableaux and permutations.
2 / 28
Permutation tableaux
First introduced by Postnikov in his study of totally nonnegative Grassmanian.
There are many bijections between permutation tableaux and permutations.
A connection with partially asymmetric exclusion process (PASEP)
2 / 28
Permutation tableaux
First introduced by Postnikov in his study of totally nonnegative Grassmanian.
There are many bijections between permutation tableaux and permutations.
A connection with partially asymmetric exclusion process (PASEP) TypeBPermutation tableaux defined by Lam and Williams
3 / 28
Ferrers diagram
1 32
54
6 87
109
3 / 28
Ferrers diagram
1 32
54
6 87
109
3 5 8 10
9 7 6 4 2 1
4 / 28
Permutation tableau
Each column has at least one1.
4 / 28
Permutation tableau
Each column has at least one1.
There isnoconfiguration like
1 ... 1 · · · 0
4 / 28
Permutation tableau
Each column has at least one1.
There isnoconfiguration like
1 ... 1 · · · 0
4 / 28
Permutation tableau
Each column has at least one1.
There isnoconfiguration like
1 ... 1 · · · 0
0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 0 1 1
0
NO
4 / 28
Permutation tableau
Each column has at least one1.
There isnoconfiguration like
1 ... 1 · · · 0
0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 0 1 1
0
NO
0 0 1 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 0 1 1
0
NO
4 / 28
Permutation tableau
Each column has at least one1.
There isnoconfiguration like
1 ... 1 · · · 0
0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 0 1 1
0
NO
0 0 1 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 0 1 1
0
NO
0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1
0
YES!
4 / 28
Permutation tableau
Each column has at least one1.
There isnoconfiguration like
1 ... 1 · · · 0
0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 0 1 1
0
NO
0 0 1 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 0 1 1
0
NO
0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1
0
YES!
Arestricted0is
1 ... 0
4 / 28
Permutation tableau
Each column has at least one1.
There isnoconfiguration like
1 ... 1 · · · 0
0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 0 1 1
0
NO
0 0 1 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 0 1 1
0
NO
0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1
0
YES!
Arestricted0is
1 ... 0 Anunrestricted rowhas no restricted0.
5 / 28
The alternative representation
Topmost1is
5 / 28
The alternative representation
Topmost1is
Rightmost restricted0is
0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 0
12 9 8 6 5 3 1
2 4 7 10 11 13
12 9 8 6 5 3 1
2 4 7 10 11 13
5 / 28
The alternative representation
Topmost1is
Rightmost restricted0is
0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 0
12 9 8 6 5 3 1
2 4 7 10 11 13
12 9 8 6 5 3 1
2 4 7 10 11 13 In the alternative representation,
5 / 28
The alternative representation
Topmost1is
Rightmost restricted0is
0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 0
12 9 8 6 5 3 1
2 4 7 10 11 13
12 9 8 6 5 3 1
2 4 7 10 11 13 In the alternative representation,
Each column has exactly one
5 / 28
The alternative representation
Topmost1is
Rightmost restricted0is
0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 0
12 9 8 6 5 3 1
2 4 7 10 11 13
12 9 8 6 5 3 1
2 4 7 10 11 13 In the alternative representation,
Each column has exactly one No arrow points to another.
5 / 28
The alternative representation
Topmost1is
Rightmost restricted0is
0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 0
12 9 8 6 5 3 1
2 4 7 10 11 13
12 9 8 6 5 3 1
2 4 7 10 11 13 In the alternative representation,
Each column has exactly one No arrow points to another.
Unrestricted row⇔row without
5 / 28
The alternative representation
Topmost1is
Rightmost restricted0is
0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 0
12 9 8 6 5 3 1
2 4 7 10 11 13
12 9 8 6 5 3 1
2 4 7 10 11 13 In the alternative representation,
Each column has exactly one No arrow points to another.
Unrestricted row⇔row without
First introduced by Viennot (alternative tableau) and studied more by Nadeau
6 / 28
The bijection Φ of Corteel and Nadeau
12 9 8 6 5 3 1
2 4 7 10 11 13
1, 10, 11, 13
6 / 28
The bijection Φ of Corteel and Nadeau
12 9 8 6 5 3 1
2 4 7 10 11 13
1,12,10,11,13
6 / 28
The bijection Φ of Corteel and Nadeau
12 9 8 6 5 3 1
2 4 7 10 11 13
9,1,12,10,11,13
6 / 28
The bijection Φ of Corteel and Nadeau
12 9 8 6 5 3 1
2 4 7 10 11 13
9,2,7,8,1,12,10,11,13
6 / 28
The bijection Φ of Corteel and Nadeau
12 9 8 6 5 3 1
2 4 7 10 11 13
9,4,6,2,7,8,1,12,10,11,13
6 / 28
The bijection Φ of Corteel and Nadeau
12 9 8 6 5 3 1
2 4 7 10 11 13
9,4,6,5,2,7,8,1,12,10,11,13
6 / 28
The bijection Φ of Corteel and Nadeau
12 9 8 6 5 3 1
2 4 7 10 11 13
9,4,6,5,2,7,8,3,1,12,10,11,13
7 / 28
Statistics
Decomposeπasσ1τ.
π= σ z }| { 4,6,5,2,8,3,1,
τ
z }| {
9,7,12,10,11,13
12 9 8 6 5 3 1
2 4 7 10 11 13
7 / 28
Statistics
Decomposeπasσ1τ.
π= σ z }| { 4,6,5,2,8,3,1,
τ
z }| {
9,7,12,10,11,13 TheRL-minima(right-to-left mimina) ofπ:
4,6,5,2,8,3,1,9,7,12,10,11,13
12 9 8 6 5 3 1
2 4 7 10 11 13
7 / 28
Statistics
Decomposeπasσ1τ.
π= σ z }| { 4,6,5,2,8,3,1,
τ
z }| {
9,7,12,10,11,13 TheRL-minima(right-to-left mimina) ofπ:
4,6,5,2,8,3,1,9,7,12,10,11,13 TheRL-maxima(right-to-left maxima) ofσ:
σ z }| {
4,6,5,2,8,3,1,9,7,12,10,11,13
12 9 8 6 5 3 1
2 4 7 10 11 13
7 / 28
Statistics
Decomposeπasσ1τ.
π= σ z }| { 4,6,5,2,8,3,1,
τ
z }| {
9,7,12,10,11,13 TheRL-minima(right-to-left mimina) ofπ:
4,6,5,2,8,3,1,9,7,12,10,11,13 TheRL-maxima(right-to-left maxima) ofσ:
σ z }| {
4,6,5,2,8,3,1,9,7,12,10,11,13
12 9 8 6 5 3 1
2 4 7 10 11 13
Proposition (Corteel & Nadeau, Nadeau) Letπ=σ1τandΦ(π) =T. Then
7 / 28
Statistics
Decomposeπasσ1τ.
π= σ z }| { 4,6,5,2,8,3,1,
τ
z }| {
9,7,12,10,11,13 TheRL-minima(right-to-left mimina) ofπ:
4,6,5,2,8,3,1,9,7,12,10,11,13 TheRL-maxima(right-to-left maxima) ofσ:
σ z }| {
4,6,5,2,8,3,1,9,7,12,10,11,13
12 9 8 6 5 3 1
2 4 7 10 11 13
Proposition (Corteel & Nadeau, Nadeau) Letπ=σ1τandΦ(π) =T. Then
the unrestricted rows ofT⇔the RL-minima ofπ
7 / 28
Statistics
Decomposeπasσ1τ.
π= σ z }| { 4,6,5,2,8,3,1,
τ
z }| {
9,7,12,10,11,13 TheRL-minima(right-to-left mimina) ofπ:
4,6,5,2,8,3,1,9,7,12,10,11,13 TheRL-maxima(right-to-left maxima) ofσ:
σ z }| {
4,6,5,2,8,3,1,9,7,12,10,11,13
12 9 8 6 5 3 1
2 4 7 10 11 13
Proposition (Corteel & Nadeau, Nadeau) Letπ=σ1τandΦ(π) =T. Then
the unrestricted rows ofT⇔the RL-minima ofπ
the columns with1in the first row ofT⇔the RL-maxima ofσ
8 / 28
Nadeau’s bijective proof of a theorem of Corteel and Nadeau
TheoremX
T∈PT(n)
xurr(T)−1ytopone(T)= (x+y)n−1= (x+y)(x+y+1)· · ·(x+y+n−2).
8 / 28
Nadeau’s bijective proof of a theorem of Corteel and Nadeau
TheoremX
T∈PT(n)
xurr(T)−1ytopone(T)= (x+y)n−1= (x+y)(x+y+1)· · ·(x+y+n−2).
c(n,k): the numberπ∈Snwithkcycles
(x+y)n−1=X
i,j
c(n−1,i+j) i+j i
! xiyj
#{T ∈ PT(n) :urr(T)−1=i, topone(T) =j}=c(n−1,i+j) i+j i
!
8 / 28
Nadeau’s bijective proof of a theorem of Corteel and Nadeau
TheoremX
T∈PT(n)
xurr(T)−1ytopone(T)= (x+y)n−1= (x+y)(x+y+1)· · ·(x+y+n−2).
c(n,k): the numberπ∈Snwithkcycles
(x+y)n−1=X
i,j
c(n−1,i+j) i+j i
! xiyj
#{T ∈ PT(n) :urr(T)−1=i, topone(T) =j}=c(n−1,i+j) i+j i
!
IfT ↔π=σ1τ,
urr(T)−1=RLmin(τ) =i topone(T) =RLmax(σ) =j
8 / 28
Nadeau’s bijective proof of a theorem of Corteel and Nadeau
TheoremX
T∈PT(n)
xurr(T)−1ytopone(T)= (x+y)n−1= (x+y)(x+y+1)· · ·(x+y+n−2).
c(n,k): the numberπ∈Snwithkcycles
(x+y)n−1=X
i,j
c(n−1,i+j) i+j i
! xiyj
#{T ∈ PT(n) :urr(T)−1=i, topone(T) =j}=c(n−1,i+j) i+j i
!
IfT ↔π=σ1τ,
urr(T)−1=RLmin(τ) =i topone(T) =RLmax(σ) =j τ is a set oficycles andσis a set ofjcycles.
8 / 28
Nadeau’s bijective proof of a theorem of Corteel and Nadeau
TheoremX
T∈PT(n)
xurr(T)−1ytopone(T)= (x+y)n−1= (x+y)(x+y+1)· · ·(x+y+n−2).
c(n,k): the numberπ∈Snwithkcycles
(x+y)n−1=X
i,j
c(n−1,i+j) i+j i
! xiyj
#{T ∈ PT(n) :urr(T)−1=i, topone(T) =j}=c(n−1,i+j) i+j i
!
IfT ↔π=σ1τ,
urr(T)−1=RLmin(τ) =i topone(T) =RLmax(σ) =j τ is a set oficycles andσis a set ofjcycles.
τ∪σis a permutation of{2,3, . . . ,n}withi+jcycles.
9 / 28
Another bijective proof
Theorem We have
X
T∈PT(n)
xurr(T)−1ytopone(T)= (x+y)n−1.
9 / 28
Another bijective proof
Theorem We have
X
T∈PT(n)
xurr(T)−1ytopone(T)= (x+y)n−1.
Letx,ybe any positive integers and letN=n+x+y−2.
9 / 28
Another bijective proof
Theorem We have
X
T∈PT(n)
xurr(T)−1ytopone(T)= (x+y)n−1.
Letx,ybe any positive integers and letN=n+x+y−2.
GivenT∈ PT(n), we constructT′∈ PT(N)as follows.
{
x−1
}
y−110 / 28
Another bijective proof
{
x−1
}
y−1T′satisfies the following.
10 / 28
Another bijective proof
{
x−1
}
y−1T′satisfies the following.
1 The firstysteps are south and the firstyrows are unrestricted.
10 / 28
Another bijective proof
{
x−1
}
y−1T′satisfies the following.
1 The firstysteps are south and the firstyrows are unrestricted.
2 The lastx−1steps are west and the lastx−1columns have↑’s in the first row.
10 / 28
Another bijective proof
{
x−1
}
y−1T′satisfies the following.
1 The firstysteps are south and the firstyrows are unrestricted.
2 The lastx−1steps are west and the lastx−1columns have↑’s in the first row.
π′= Φ(T′)satisfies the following. (π′=σ1τ)
10 / 28
Another bijective proof
{
x−1
}
y−1T′satisfies the following.
1 The firstysteps are south and the firstyrows are unrestricted.
2 The lastx−1steps are west and the lastx−1columns have↑’s in the first row.
π′= Φ(T′)satisfies the following. (π′=σ1τ)
1 1,2, . . . ,yare RL-minima ofπ′
10 / 28
Another bijective proof
{
x−1
}
y−1T′satisfies the following.
1 The firstysteps are south and the firstyrows are unrestricted.
2 The lastx−1steps are west and the lastx−1columns have↑’s in the first row.
π′= Φ(T′)satisfies the following. (π′=σ1τ)
1 1,2, . . . ,yare RL-minima ofπ′
2 N,N−1, . . . ,N−x+2are RL-maxima ofσ
10 / 28
Another bijective proof
{
x−1
}
y−1T′satisfies the following.
1 The firstysteps are south and the firstyrows are unrestricted.
2 The lastx−1steps are west and the lastx−1columns have↑’s in the first row.
π′= Φ(T′)satisfies the following. (π′=σ1τ)
1 1,2, . . . ,yare RL-minima ofπ′
2 N,N−1, . . . ,N−x+2are RL-maxima ofσ
N,N−1, . . . ,N−x+2,1,2, . . . ,yare arranged in this order inπ′.
11 / 28
Unrestricted Columns
Anunrestricted columnofT ∈ PT(n)is a column without 0 as follows.
1 · · · 0
11 / 28
Unrestricted Columns
Anunrestricted columnofT ∈ PT(n)is a column without 0 as follows.
1 · · · 0 urc(T): the number of unrestricted columns ofT.
11 / 28
Unrestricted Columns
Anunrestricted columnofT ∈ PT(n)is a column without 0 as follows.
1 · · · 0 urc(T): the number of unrestricted columns ofT. Let
Pt(x) =X
n≥0
0
@ X
T∈PT(n)
turc(T) 1 Axn.
11 / 28
Unrestricted Columns
Anunrestricted columnofT ∈ PT(n)is a column without 0 as follows.
1 · · · 0 urc(T): the number of unrestricted columns ofT. Let
Pt(x) =X
n≥0
0
@ X
T∈PT(n)
turc(T) 1 Axn.
Theorem We have
Pt(x) = 1+Et(x) 1+ (t−1)xEt(x), where
Et(x) =X
n≥1
n(t)n−1xn.
12 / 28
The case t = 2 : connected permutations
CorollaryX
n≥0
X
T∈PT(n)
2urc(T)xn =1
x 1− 1
P
n≥0n!xn
! .
12 / 28
The case t = 2 : connected permutations
CorollaryX
n≥0
X
T∈PT(n)
2urc(T)xn =1
x 1− 1
P
n≥0n!xn
! .
π=π1· · ·πn∈Snis aconnected permutationif there is nok<n satisfyingπ1· · ·πk∈Sk.
12 / 28
The case t = 2 : connected permutations
CorollaryX
n≥0
X
T∈PT(n)
2urc(T)xn =1
x 1− 1
P
n≥0n!xn
! .
π=π1· · ·πn∈Snis aconnected permutationif there is nok<n satisfyingπ1· · ·πk∈Sk.
CP(n): the set of connected permutations inSn
X
n≥0
#CP(n)xn=1− 1 P
n≥0n!xn
12 / 28
The case t = 2 : connected permutations
CorollaryX
n≥0
X
T∈PT(n)
2urc(T)xn =1
x 1− 1
P
n≥0n!xn
! .
π=π1· · ·πn∈Snis aconnected permutationif there is nok<n satisfyingπ1· · ·πk∈Sk.
CP(n): the set of connected permutations inSn
X
n≥0
#CP(n)xn=1− 1 P
n≥0n!xn
Corollary
X
T∈PT(n)
2urc(T)= #CP(n+1).
12 / 28
The case t = 2 : connected permutations
CorollaryX
n≥0
X
T∈PT(n)
2urc(T)xn =1
x 1− 1
P
n≥0n!xn
! .
π=π1· · ·πn∈Snis aconnected permutationif there is nok<n satisfyingπ1· · ·πk∈Sk.
CP(n): the set of connected permutations inSn
X
n≥0
#CP(n)xn=1− 1 P
n≥0n!xn
Corollary
X
T∈PT(n)
2urc(T)= #CP(n+1).
Combinatorial proof?
13 / 28
Shift-connected permutations
Ashift-connected permutationisπ=π1· · ·πn∈Snwithπj=1for somej∈[n]such that
13 / 28
Shift-connected permutations
Ashift-connected permutationisπ=π1· · ·πn∈Snwithπj=1for somej∈[n]such that
there is no integeri<jwith
πiπi+1· · ·πj∈Sj−i+1
13 / 28
Shift-connected permutations
Ashift-connected permutationisπ=π1· · ·πn∈Snwithπj=1for somej∈[n]such that
there is no integeri<jwith
πiπi+1· · ·πj∈Sj−i+1
SCP(n): the set of shift-connected permutations inSn
13 / 28
Shift-connected permutations
Ashift-connected permutationisπ=π1· · ·πn∈Snwithπj=1for somej∈[n]such that
there is no integeri<jwith
πiπi+1· · ·πj∈Sj−i+1
SCP(n): the set of shift-connected permutations inSn
Proposition
#CP(n) = #SCP(n)
14 / 28
A bijection between S
n\ CP(n) and S
n\ SCP(n)
Givenπ=π1· · ·πn∈Sn\CP(n), defineπ′∈Sn\SCP(n)as follows.
14 / 28
A bijection between S
n\ CP(n) and S
n\ SCP(n)
Givenπ=π1· · ·πn∈Sn\CP(n), defineπ′∈Sn\SCP(n)as follows.
Find the smallest integerk<nsuch that σ=π1· · ·πk∈Sk
14 / 28
A bijection between S
n\ CP(n) and S
n\ SCP(n)
Givenπ=π1· · ·πn∈Sn\CP(n), defineπ′∈Sn\SCP(n)as follows.
Find the smallest integerk<nsuch that σ=π1· · ·πk∈Sk
Decomposeπas
π=στ(k+1)ρ
14 / 28
A bijection between S
n\ CP(n) and S
n\ SCP(n)
Givenπ=π1· · ·πn∈Sn\CP(n), defineπ′∈Sn\SCP(n)as follows.
Find the smallest integerk<nsuch that σ=π1· · ·πk∈Sk
Decomposeπas
π=στ(k+1)ρ Define
σ+=σ1+· · ·σk+, σ+i =σi+1 π′=τ σ+1ρ
14 / 28
A bijection between S
n\ CP(n) and S
n\ SCP(n)
Givenπ=π1· · ·πn∈Sn\CP(n), defineπ′∈Sn\SCP(n)as follows.
Find the smallest integerk<nsuch that σ=π1· · ·πk∈Sk
Decomposeπas
π=στ(k+1)ρ Define
σ+=σ1+· · ·σk+, σ+i =σi+1 π′=τ σ+1ρ
Example
14 / 28
A bijection between S
n\ CP(n) and S
n\ SCP(n)
Givenπ=π1· · ·πn∈Sn\CP(n), defineπ′∈Sn\SCP(n)as follows.
Find the smallest integerk<nsuch that σ=π1· · ·πk∈Sk
Decomposeπas
π=στ(k+1)ρ Define
σ+=σ1+· · ·σk+, σ+i =σi+1 π′=τ σ+1ρ
Example
Letπ∈Sn\CP(n)be
π= σ z }| { 4,2,5,1,3,
τ z}|{7 ,
k+1 z}|{6 ,
ρ z}|{9,8
14 / 28
A bijection between S
n\ CP(n) and S
n\ SCP(n)
Givenπ=π1· · ·πn∈Sn\CP(n), defineπ′∈Sn\SCP(n)as follows.
Find the smallest integerk<nsuch that σ=π1· · ·πk∈Sk
Decomposeπas
π=στ(k+1)ρ Define
σ+=σ1+· · ·σk+, σ+i =σi+1 π′=τ σ+1ρ
Example
Letπ∈Sn\CP(n)be
π= σ z }| { 4,2,5,1,3,
τ z}|{7 ,
k+1 z}|{6 ,
ρ z}|{9,8
Thenπ′∈Sn\SCP(n)is
π′= τ z}|{7 ,
σ+ z }| { 5,3,6,2,4,
1 z}|{1 ,
ρ z}|{9,8
15 / 28
A combinatorial proof of X
T∈PT(n)
2
urc(T)= #CP(n + 1)
Proposition P
T∈PT(n)2urc(T)is the number ofT∈ PT(n+1)without a column containing 1only in the first row.
15 / 28
A combinatorial proof of X
T∈PT(n)
2
urc(T)= #CP(n + 1)
Proposition P
T∈PT(n)2urc(T)is the number ofT∈ PT(n+1)without a column containing 1only in the first row.
Proposition
15 / 28
A combinatorial proof of X
T∈PT(n)
2
urc(T)= #CP(n + 1)
Proposition P
T∈PT(n)2urc(T)is the number ofT∈ PT(n+1)without a column containing 1only in the first row.
Proposition Forπ= Φ(T),
15 / 28
A combinatorial proof of X
T∈PT(n)
2
urc(T)= #CP(n + 1)
Proposition P
T∈PT(n)2urc(T)is the number ofT∈ PT(n+1)without a column containing 1only in the first row.
Proposition Forπ= Φ(T),
Thas a column which has a1only in the first row if and only if
15 / 28
A combinatorial proof of X
T∈PT(n)
2
urc(T)= #CP(n + 1)
Proposition P
T∈PT(n)2urc(T)is the number ofT∈ PT(n+1)without a column containing 1only in the first row.
Proposition
Forπ= Φ(T),
Thas a column which has a1only in the first row if and only if π6∈SCP(n)
15 / 28
A combinatorial proof of X
T∈PT(n)
2
urc(T)= #CP(n + 1)
Proposition P
T∈PT(n)2urc(T)is the number ofT∈ PT(n+1)without a column containing 1only in the first row.
Proposition
Forπ= Φ(T),
Thas a column which has a1only in the first row if and only if π6∈SCP(n)
Proposition
X
T∈PT(n)
2urc(T)= #SCP(n+1) = #CP(n+1)
16 / 28
The case t = −1 : sign-imbalance
CorollaryP−1(x) =X
n≥0
X
T∈PT(n)
(−1)urc(T)xn= 1−x 1−2x+2x2
= 1 2·
„ 1
1−(1+i)x+ 1 1−(1−i)x
«
16 / 28
The case t = −1 : sign-imbalance
CorollaryP−1(x) =X
n≥0
X
T∈PT(n)
(−1)urc(T)xn= 1−x 1−2x+2x2
= 1 2·
„ 1
1−(1+i)x+ 1 1−(1−i)x
«
Definition
ForT∈ PT(n), define thesignofT by
sgn(T) = (−1)urc(T).
16 / 28
The case t = −1 : sign-imbalance
CorollaryP−1(x) =X
n≥0
X
T∈PT(n)
(−1)urc(T)xn= 1−x 1−2x+2x2
= 1 2·
„ 1
1−(1+i)x+ 1 1−(1−i)x
«
Definition
ForT∈ PT(n), define thesignofT by
sgn(T) = (−1)urc(T).
Corollary
X
T∈PT(n)
sgn(T) = (1+i)n+ (1−i)n
2 =
8
<
:
(−1)k·22k, ifn=4korn=4k+1, 0, ifn=4k+2,
(−1)k+1·22k+1, ifn=4k+3.
17 / 28
Relation between the sign-imbalance of SYT
Thesignof a standard Young tableau is defined as follows.
sgn 1 2 5 3 4
!
=sgn(12534) =1
17 / 28
Relation between the sign-imbalance of SYT
Thesignof a standard Young tableau is defined as follows.
sgn 1 2 5 3 4
!
=sgn(12534) =1
Stanley conjectured
X
T∈SYT(n)
sgn(T) =2⌊n2⌋
17 / 28
Relation between the sign-imbalance of SYT
Thesignof a standard Young tableau is defined as follows.
sgn 1 2 5 3 4
!
=sgn(12534) =1
Stanley conjectured
X
T∈SYT(n)
sgn(T) =2⌊n2⌋
Proved by Lam and Sjöstrand independently
17 / 28
Relation between the sign-imbalance of SYT
Thesignof a standard Young tableau is defined as follows.
sgn 1 2 5 3 4
!
=sgn(12534) =1
Stanley conjectured
X
T∈SYT(n)
sgn(T) =2⌊n2⌋
Proved by Lam and Sjöstrand independently Generalized to skew SYTs by Kim
17 / 28
Relation between the sign-imbalance of SYT
Thesignof a standard Young tableau is defined as follows.
sgn 1 2 5 3 4
!
=sgn(12534) =1
Stanley conjectured
X
T∈SYT(n)
sgn(T) =2⌊n2⌋
Proved by Lam and Sjöstrand independently Generalized to skew SYTs by Kim
Ifn6≡2 mod 4,
˛˛
˛˛
˛˛ X
T∈PT(n)
sgn(T)
˛˛
˛˛
˛˛
=
˛˛
˛˛
˛˛ X
T∈SYT(n)
sgn(T)
˛˛
˛˛
˛˛
=2⌊n2⌋.
18 / 28
Shifted Ferrers diagram
3 5 8 10
9 7 6 4 2 1
−9
−7
−6
−4
−2
−1 3 5 8 10
9 7 6 4 2 1
The yellow cells are thediagonalcells.
18 / 28
Shifted Ferrers diagram
3 5 8 10
9 7 6 4 2 1
−9
−7
−6
−4
−2
−1 3 5 8 10
9 7 6 4 2 1
The yellow cells are thediagonalcells.
The row containing the diagonal cell in Columndis labeled with−d.
19 / 28
Type B permutation tableaux
Each column has at least one1.
19 / 28
Type B permutation tableaux
Each column has at least one1.
There isnoconfiguration like 1
... 1 · · · 0
or 1 · · · 0
19 / 28
Type B permutation tableaux
Each column has at least one1.
There isnoconfiguration like 1
... 1 · · · 0
or 1 · · · 0
19 / 28
Type B permutation tableaux
Each column has at least one1.
There isnoconfiguration like 1
... 1 · · · 0
or 1 · · · 0
0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 1 0 0 1
NO
19 / 28
Type B permutation tableaux
Each column has at least one1.
There isnoconfiguration like 1
... 1 · · · 0
or 1 · · · 0
0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 1 0 0 1
NO
0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 1 0 1 1
NO
19 / 28
Type B permutation tableaux
Each column has at least one1.
There isnoconfiguration like 1
... 1 · · · 0
or 1 · · · 0
0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 1 0 0 1
NO
0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 1 0 1 1
NO
0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 1 0 1 1
YES!
20 / 28
The alternative representation
Topmost1is
20 / 28
The alternative representation
Topmost1is
Rightmost restricted0is
20 / 28
The alternative representation
Topmost1is
Rightmost restricted0is Cut off the diagonal cells.
20 / 28
The alternative representation
Topmost1is
Rightmost restricted0is Cut off the diagonal cells.
20 / 28
The alternative representation
Topmost1is
Rightmost restricted0is Cut off the diagonal cells.
0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 1 0 1 1
−10
−9
−8
−6
−3
−2 1 4 5 7 11
10 9 8 6 3 2
−10
−9
−8
−6
−3
−2 1 4 5 7 11
10 9 8 6 3 2
No arrow points to another.
20 / 28
The alternative representation
Topmost1is
Rightmost restricted0is Cut off the diagonal cells.
0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 1 0 1 1
−10
−9
−8
−6
−3
−2 1 4 5 7 11
10 9 8 6 3 2
−10
−9
−8
−6
−3
−2 1 4 5 7 11
10 9 8 6 3 2
No arrow points to another.
The diagonal line acts like a mirror!
21 / 28
A theorem of Lam and Williams
Theorem (Lam and Williams)
X
T∈PTB(n)
xurr(T)−1zdiag(T)= (1+z)n(x+1)n−1
21 / 28
A theorem of Lam and Williams
Theorem (Lam and Williams)
X
T∈PTB(n)
xurr(T)−1zdiag(T)= (1+z)n(x+1)n−1
diag(T): the number of diagonal cells with 1
21 / 28
A theorem of Lam and Williams
Theorem (Lam and Williams)
X
T∈PTB(n)
xurr(T)−1zdiag(T)= (1+z)n(x+1)n−1
diag(T): the number of diagonal cells with 1 urr(T): the number of unrestricted rows, i.e. without
1 ... 0
and 0
21 / 28
A theorem of Lam and Williams
Theorem (Lam and Williams)
X
T∈PTB(n)
xurr(T)−1zdiag(T)= (1+z)n(x+1)n−1
diag(T): the number of diagonal cells with 1 urr(T): the number of unrestricted rows, i.e. without
1 ... 0
and 0
Theorem
X
T∈PTB(n)
xurr(T)−1ytop0,1(T)zdiag(T)= (1+z)n(x+y)n−1
22 / 28
Generalization of a theorem of Lam and Williams
ForT∈ PTB(n)with the topmost nonzero row labeledm, top0,1(T) =(#1s in Rowmexcept in the diagonal)
+(#rightmost restricted 0s in Column−m)
= #arrows in Rowmand Column−m
0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 1 0 1 1
−10
−9
−8
−6
−3
−2 1 4 5 7 11
10 9 8 6 3 2
−10
−9
−8
−6
−3
−2 1 4 5 7 11
10 9 8 6 3 2
23 / 28
A type B extension of Corteel and Nadeau’s bijection
−10
−9 –8
−6
−3
−2 1 4 5 7 11
10 9 8 6 3 2
–8,4,11
23 / 28
A type B extension of Corteel and Nadeau’s bijection
−10
−9
−8
−6
−3
−2 1 4 5 7 11
10 9 8 6 3 2
7,10,−8,4,11
23 / 28
A type B extension of Corteel and Nadeau’s bijection
−10
−9
−8
−6
−3
−2 1 4 5 7 11
10 9 8 6 3 2
9,7,10,−8,4,11
23 / 28
A type B extension of Corteel and Nadeau’s bijection
−10
−9
−8
−6
−3
−2 1 4 5 7 11
10 9 8 6 3 2
9,7,10,–3,5−8,4,11
23 / 28
A type B extension of Corteel and Nadeau’s bijection
−10
−9
−8
−6
−3
−2 1 4 5 7 11
10 9 8 6 3 2
9,7,10,−3,5−8,6,4,11
23 / 28
A type B extension of Corteel and Nadeau’s bijection
−10
−9
−8
−6
−3
−2 1 4 5 7 11
10 9 8 6 3 2
9,7,10,1,−3,5−8,6,4,11
23 / 28
A type B extension of Corteel and Nadeau’s bijection
−10
−9
−8
−6
−3
−2 1 4 5 7 11
10 9 8 6 3 2
9,7,10,2,1,−3,5−8,6,4,11
24 / 28
Some properties of the type B bijection
PropositionThen,
−10
−9
−8
−6 –3
−2 1 4 5 7 11
10 9 8 6 3 2
π= σ z }| { 9,7,10,
τ z }| { 6,2,1,–3,5,
m z}|{−8,
ρ z }| { 4,11
24 / 28
Some properties of the type B bijection
Proposition π= ΦB(T)
Then,
−10
−9
−8
−6 –3
−2 1 4 5 7 11
10 9 8 6 3 2
π= σ z }| { 9,7,10,
τ z }| { 6,2,1,–3,5,
m z}|{−8,
ρ z }| { 4,11
24 / 28
Some properties of the type B bijection
Proposition
π= ΦB(T)
Rowmis the topmost nonzero row ofT
Then,
−10
−9
−8
−6 –3
−2 1 4 5 7 11
10 9 8 6 3 2
π= σ z }| { 9,7,10,
τ z }| { 6,2,1,–3,5,
m z}|{−8,
ρ z }| { 4,11
24 / 28
Some properties of the type B bijection
Proposition
π= ΦB(T)
Rowmis the topmost nonzero row ofT
Decomposeπ=στmρ
Then,
−10
−9
−8
−6 –3
−2 1 4 5 7 11
10 9 8 6 3 2
π= σ z }| { 9,7,10,
τ z }| { 6,2,1,–3,5,
m z}|{−8,
ρ z }| { 4,11
24 / 28
Some properties of the type B bijection
Proposition
π= ΦB(T)
Rowmis the topmost nonzero row ofT
Decomposeπ=στmρ min(π) =m
Then,
−10
−9
−8
−6 –3
−2 1 4 5 7 11
10 9 8 6 3 2
π= σ z }| { 9,7,10,
τ z }| { 6,2,1,–3,5,
m z}|{−8,
ρ z }| { 4,11
24 / 28
Some properties of the type B bijection
Proposition
π= ΦB(T)
Rowmis the topmost nonzero row ofT
Decomposeπ=στmρ min(π) =m
the last element ofσis>|m|
Then,
−10
−9
−8
−6 –3
−2 1 4 5 7 11
10 9 8 6 3 2
π= σ z }| { 9,7,10,
τ z }| { 6,2,1,–3,5,
m z}|{−8,
ρ z }| { 4,11
24 / 28
Some properties of the type B bijection
Proposition
π= ΦB(T)
Rowmis the topmost nonzero row ofT
Decomposeπ=στmρ min(π) =m
the last element ofσis>|m|
each element ofτis<|m|
Then,
−10
−9
−8
−6 –3
−2 1 4 5 7 11
10 9 8 6 3 2
π= σ z }| { 9,7,10,
τ z }| { 6,2,1,–3,5,
m z}|{−8,
ρ z }| { 4,11
24 / 28
Some properties of the type B bijection
Proposition
π= ΦB(T)
Rowmis the topmost nonzero row ofT
Decomposeπ=στmρ min(π) =m
the last element ofσis>|m|
each element ofτis<|m|
Then,
1 Columns without
↔negative integers inπ
−10
−9
−8
−6 –3
−2 1 4 5 7 11
10 9 8 6 3 2
π= σ z }| { 9,7,10,
τ z }| { 6,2,1,–3,5,
m z}|{−8,
ρ z }| { 4,11
24 / 28
Some properties of the type B bijection
Proposition
π= ΦB(T)
Rowmis the topmost nonzero row ofT
Decomposeπ=στmρ min(π) =m
the last element ofσis>|m|
each element ofτis<|m|
Then,
1 Columns without
↔negative integers inπ
2 Unrestricted rows ofT
↔RL-minima ofπ
−10
−9
−8
−6 –3
−2 1 4 5 7 11
10 9 8 6 3 2
π= σ z }| { 9,7,10,
τ z }| { 6,2,1,–3,5,
m z}|{−8,
ρ z }| { 4,11
24 / 28
Some properties of the type B bijection
Proposition
π= ΦB(T)
Rowmis the topmost nonzero row ofT
Decomposeπ=στmρ min(π) =m
the last element ofσis>|m|
each element ofτis<|m|
Then,
1 Columns without
↔negative integers inπ
2 Unrestricted rows ofT
↔RL-minima ofπ
3 Columns with in Rowm
↔RL-maxima ofσ
−10
−9
−8
−6 –3
−2 1 4 5 7 11
10 9 8 6 3 2
π= σ z }| { 9,7,10,
τ z }| { 6,2,1,–3,5,
m z}|{−8,
ρ z }| { 4,11
24 / 28
Some properties of the type B bijection
Proposition
π= ΦB(T)
Rowmis the topmost nonzero row ofT
Decomposeπ=στmρ min(π) =m
the last element ofσis>|m|
each element ofτis<|m|
Then,
1 Columns without
↔negative integers inπ
2 Unrestricted rows ofT
↔RL-minima ofπ
3 Columns with in Rowm
↔RL-maxima ofσ
4 Rows with in Column|m|
↔RL-minima ofτ
−10
−9
−8
−6 –3
−2 1 4 5 7 11
10 9 8 6 3 2
π= σ z }| { 9,7,10,
τ z }| { 6,2,1,–3,5,
m z}|{−8,
ρ z }| { 4,11
25 / 28
Generalization
TheoremX
T∈PTB(n)
xurr(T)−1ytop0,1(T)zdiag(T)= (1+z)n(x+y)n−1
25 / 28
Generalization
TheoremX
T∈PTB(n)
xurr(T)−1ytop0,1(T)zdiag(T)= (1+z)n(x+y)n−1
25 / 28
Generalization
TheoremX
T∈PTB(n)
xurr(T)−1ytop0,1(T)zdiag(T)= (1+z)n(x+y)n−1
m
|m| y−
{
1{
x−126 / 28
Zigzag maps
0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 0
12 9 8 6 5 3 1
2 4 7 10 11 13
26 / 28
Zigzag maps
0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 0
12 9 8 6 5 3 1
2 4 7 10 11 13
12 9 8 6 5 3 1
2 4 7 10 11 13
26 / 28
Zigzag maps
0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 0
12 9 8 6 5 3 1
2 4 7 10 11 13
12 9 8 6 5 3 1
2 4 7 10 11 13
12 9 8 6 5 3 1
2 4 7 10 11 13
26 / 28
Zigzag maps
0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 0
12 9 8 6 5 3 1
2 4 7 10 11 13
12 9 8 6 5 3 1
2 4 7 10 11 13
12 9 8 6 5 3 1
2 4 7 10 11 13
Theorem
The zigzag map on the alternative representation is the same asϕ◦Φ.
26 / 28
Zigzag maps
0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 0
12 9 8 6 5 3 1
2 4 7 10 11 13
12 9 8 6 5 3 1
2 4 7 10 11 13
12 9 8 6 5 3 1
2 4 7 10 11 13
Theorem
The zigzag map on the alternative representation is the same asϕ◦Φ.
Example
26 / 28
Zigzag maps
0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 0
12 9 8 6 5 3 1
2 4 7 10 11 13
12 9 8 6 5 3 1
2 4 7 10 11 13
12 9 8 6 5 3 1
2 4 7 10 11 13
Theorem
The zigzag map on the alternative representation is the same asϕ◦Φ.
Example
Φ(T) =4,6,5,2,8,3,1,9,7,11,12,10
26 / 28
Zigzag maps
0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 0
12 9 8 6 5 3 1
2 4 7 10 11 13
12 9 8 6 5 3 1
2 4 7 10 11 13
12 9 8 6 5 3 1
2 4 7 10 11 13
Theorem
The zigzag map on the alternative representation is the same asϕ◦Φ.
Example
Φ(T) =4,6,5,2,8,3,1,9,7,11,12,10 ϕ◦Φ(T) = (4,6,5,2,8,3,1)(9,7)(11,12,10)
27 / 28
The zigzag map on the type B alternative representation
−10
−9
−8
−6
−3
−2 1 4 5 7 11
10 9 8 6 3 2
Theorem
The zigzag map on the typeBalternative representation isϕ◦ΦB.
27 / 28
The zigzag map on the type B alternative representation
−10
−9
−8
−6
−3
−2 1 4 5 7 11
10 9 8 6 3 2
Theorem
The zigzag map on the typeBalternative representation isϕ◦ΦB. Example
27 / 28
The zigzag map on the type B alternative representation
−10
−9
−8
−6
−3
−2 1 4 5 7 11
10 9 8 6 3 2
Theorem
The zigzag map on the typeBalternative representation isϕ◦ΦB. Example
ΦB(T) =9,7,10,6,2,1,−3,5,–8,4,11