• 検索結果がありません。

On permutation tableaux of type A and B

N/A
N/A
Protected

Academic year: 2022

シェア "On permutation tableaux of type A and B"

Copied!
140
0
0

読み込み中.... (全文を見る)

全文

(1)

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)

2 / 28

Permutation tableaux

First introduced by Postnikov in his study of totally nonnegative Grassmanian.

(3)

2 / 28

Permutation tableaux

First introduced by Postnikov in his study of totally nonnegative Grassmanian.

There are many bijections between permutation tableaux and permutations.

(4)

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)

(5)

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

(6)

3 / 28

Ferrers diagram

1 32

54

6 87

109

(7)

3 / 28

Ferrers diagram

1 32

54

6 87

109

3 5 8 10

9 7 6 4 2 1

(8)

4 / 28

Permutation tableau

Each column has at least one1.

(9)

4 / 28

Permutation tableau

Each column has at least one1.

There isnoconfiguration like

1 ... 1 · · · 0

(10)

4 / 28

Permutation tableau

Each column has at least one1.

There isnoconfiguration like

1 ... 1 · · · 0

(11)

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

(12)

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

(13)

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!

(14)

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

(15)

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.

(16)

5 / 28

The alternative representation

Topmost1is

(17)

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

(18)

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,

(19)

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

(20)

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.

(21)

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

(22)

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

(23)

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

(24)

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

(25)

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

(26)

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

(27)

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

(28)

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

(29)

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

(30)

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

(31)

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

(32)

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

(33)

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

(34)

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 ofTthe RL-minima ofπ

(35)

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 ofTthe RL-minima ofπ

the columns with1in the first row ofTthe RL-maxima ofσ

(36)

8 / 28

Nadeau’s bijective proof of a theorem of Corteel and Nadeau

Theorem

X

T∈PT(n)

xurr(T)−1ytopone(T)= (x+y)n−1= (x+y)(x+y+1)· · ·(x+y+n−2).

(37)

8 / 28

Nadeau’s bijective proof of a theorem of Corteel and Nadeau

Theorem

X

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

!

(38)

8 / 28

Nadeau’s bijective proof of a theorem of Corteel and Nadeau

Theorem

X

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

(39)

8 / 28

Nadeau’s bijective proof of a theorem of Corteel and Nadeau

Theorem

X

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.

(40)

8 / 28

Nadeau’s bijective proof of a theorem of Corteel and Nadeau

Theorem

X

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.

(41)

9 / 28

Another bijective proof

Theorem We have

X

T∈PT(n)

xurr(T)−1ytopone(T)= (x+y)n−1.

(42)

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.

(43)

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

}

y1

(44)

10 / 28

Another bijective proof

{

x−1

}

y1

Tsatisfies the following.

(45)

10 / 28

Another bijective proof

{

x−1

}

y1

Tsatisfies the following.

1 The firstysteps are south and the firstyrows are unrestricted.

(46)

10 / 28

Another bijective proof

{

x−1

}

y1

Tsatisfies the following.

1 The firstysteps are south and the firstyrows are unrestricted.

2 The lastx1steps are west and the lastx1columns have↑’s in the first row.

(47)

10 / 28

Another bijective proof

{

x−1

}

y1

Tsatisfies the following.

1 The firstysteps are south and the firstyrows are unrestricted.

2 The lastx1steps are west and the lastx1columns have↑’s in the first row.

π= Φ(T)satisfies the following. (π=σ1τ)

(48)

10 / 28

Another bijective proof

{

x−1

}

y1

Tsatisfies the following.

1 The firstysteps are south and the firstyrows are unrestricted.

2 The lastx1steps are west and the lastx1columns have↑’s in the first row.

π= Φ(T)satisfies the following. (π=σ1τ)

1 1,2, . . . ,yare RL-minima ofπ

(49)

10 / 28

Another bijective proof

{

x−1

}

y1

Tsatisfies the following.

1 The firstysteps are south and the firstyrows are unrestricted.

2 The lastx1steps are west and the lastx1columns have↑’s in the first row.

π= Φ(T)satisfies the following. (π=σ1τ)

1 1,2, . . . ,yare RL-minima ofπ

2 N,N1, . . . ,Nx+2are RL-maxima ofσ

(50)

10 / 28

Another bijective proof

{

x−1

}

y1

Tsatisfies the following.

1 The firstysteps are south and the firstyrows are unrestricted.

2 The lastx1steps are west and the lastx1columns have↑’s in the first row.

π= Φ(T)satisfies the following. (π=σ1τ)

1 1,2, . . . ,yare RL-minima ofπ

2 N,N1, . . . ,Nx+2are RL-maxima ofσ

N,N−1, . . . ,Nx+2,1,2, . . . ,yare arranged in this order inπ.

(51)

11 / 28

Unrestricted Columns

Anunrestricted columnofT ∈ PT(n)is a column without 0 as follows.

1 · · · 0

(52)

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.

(53)

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.

(54)

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.

(55)

12 / 28

The case t = 2 : connected permutations

Corollary

X

n≥0

X

T∈PT(n)

2urc(T)xn =1

x 1− 1

P

n≥0n!xn

! .

(56)

12 / 28

The case t = 2 : connected permutations

Corollary

X

n≥0

X

T∈PT(n)

2urc(T)xn =1

x 1− 1

P

n≥0n!xn

! .

π=π1· · ·πnSnis aconnected permutationif there is nok<n satisfyingπ1· · ·πkSk.

(57)

12 / 28

The case t = 2 : connected permutations

Corollary

X

n≥0

X

T∈PT(n)

2urc(T)xn =1

x 1− 1

P

n≥0n!xn

! .

π=π1· · ·πnSnis aconnected permutationif there is nok<n satisfyingπ1· · ·πkSk.

CP(n): the set of connected permutations inSn

X

n≥0

#CP(n)xn=1− 1 P

n≥0n!xn

(58)

12 / 28

The case t = 2 : connected permutations

Corollary

X

n≥0

X

T∈PT(n)

2urc(T)xn =1

x 1− 1

P

n≥0n!xn

! .

π=π1· · ·πnSnis aconnected permutationif there is nok<n satisfyingπ1· · ·πkSk.

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).

(59)

12 / 28

The case t = 2 : connected permutations

Corollary

X

n≥0

X

T∈PT(n)

2urc(T)xn =1

x 1− 1

P

n≥0n!xn

! .

π=π1· · ·πnSnis aconnected permutationif there is nok<n satisfyingπ1· · ·πkSk.

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?

(60)

13 / 28

Shift-connected permutations

Ashift-connected permutationisπ=π1· · ·πnSnwithπj=1for somej∈[n]such that

(61)

13 / 28

Shift-connected permutations

Ashift-connected permutationisπ=π1· · ·πnSnwithπj=1for somej∈[n]such that

there is no integeri<jwith

πiπi+1· · ·πjSj−i+1

(62)

13 / 28

Shift-connected permutations

Ashift-connected permutationisπ=π1· · ·πnSnwithπj=1for somej∈[n]such that

there is no integeri<jwith

πiπi+1· · ·πjSj−i+1

SCP(n): the set of shift-connected permutations inSn

(63)

13 / 28

Shift-connected permutations

Ashift-connected permutationisπ=π1· · ·πnSnwithπj=1for somej∈[n]such that

there is no integeri<jwith

πiπi+1· · ·πjSj−i+1

SCP(n): the set of shift-connected permutations inSn

Proposition

#CP(n) = #SCP(n)

(64)

14 / 28

A bijection between S

n

\ CP(n) and S

n

\ SCP(n)

Givenπ=π1· · ·πnSn\CP(n), defineπSn\SCP(n)as follows.

(65)

14 / 28

A bijection between S

n

\ CP(n) and S

n

\ SCP(n)

Givenπ=π1· · ·πnSn\CP(n), defineπSn\SCP(n)as follows.

Find the smallest integerk<nsuch that σ=π1· · ·πkSk

(66)

14 / 28

A bijection between S

n

\ CP(n) and S

n

\ SCP(n)

Givenπ=π1· · ·πnSn\CP(n), defineπSn\SCP(n)as follows.

Find the smallest integerk<nsuch that σ=π1· · ·πkSk

Decomposeπas

π=στ(k+1)ρ

(67)

14 / 28

A bijection between S

n

\ CP(n) and S

n

\ SCP(n)

Givenπ=π1· · ·πnSn\CP(n), defineπSn\SCP(n)as follows.

Find the smallest integerk<nsuch that σ=π1· · ·πkSk

Decomposeπas

π=στ(k+1)ρ Define

σ+1+· · ·σk+, σ+ii+1 π=τ σ+

(68)

14 / 28

A bijection between S

n

\ CP(n) and S

n

\ SCP(n)

Givenπ=π1· · ·πnSn\CP(n), defineπSn\SCP(n)as follows.

Find the smallest integerk<nsuch that σ=π1· · ·πkSk

Decomposeπas

π=στ(k+1)ρ Define

σ+1+· · ·σk+, σ+ii+1 π=τ σ+

Example

(69)

14 / 28

A bijection between S

n

\ CP(n) and S

n

\ SCP(n)

Givenπ=π1· · ·πnSn\CP(n), defineπSn\SCP(n)as follows.

Find the smallest integerk<nsuch that σ=π1· · ·πkSk

Decomposeπas

π=στ(k+1)ρ Define

σ+1+· · ·σk+, σ+ii+1 π=τ σ+

Example

Letπ∈Sn\CP(n)be

π= σ z }| { 4,2,5,1,3,

τ z}|{7 ,

k+1 z}|{6 ,

ρ z}|{9,8

(70)

14 / 28

A bijection between S

n

\ CP(n) and S

n

\ SCP(n)

Givenπ=π1· · ·πnSn\CP(n), defineπSn\SCP(n)as follows.

Find the smallest integerk<nsuch that σ=π1· · ·πkSk

Decomposeπas

π=στ(k+1)ρ Define

σ+1+· · ·σk+, σ+ii+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

(71)

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.

(72)

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

(73)

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),

(74)

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

(75)

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)

(76)

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)

(77)

16 / 28

The case t = −1 : sign-imbalance

Corollary

P−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

«

(78)

16 / 28

The case t = −1 : sign-imbalance

Corollary

P−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).

(79)

16 / 28

The case t = −1 : sign-imbalance

Corollary

P−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.

(80)

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

(81)

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

(82)

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

(83)

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

(84)

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⌋.

(85)

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.

(86)

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.

(87)

19 / 28

Type B permutation tableaux

Each column has at least one1.

(88)

19 / 28

Type B permutation tableaux

Each column has at least one1.

There isnoconfiguration like 1

... 1 · · · 0

or 1 · · · 0

(89)

19 / 28

Type B permutation tableaux

Each column has at least one1.

There isnoconfiguration like 1

... 1 · · · 0

or 1 · · · 0

(90)

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

(91)

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

(92)

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!

(93)

20 / 28

The alternative representation

Topmost1is

(94)

20 / 28

The alternative representation

Topmost1is

Rightmost restricted0is

(95)

20 / 28

The alternative representation

Topmost1is

Rightmost restricted0is Cut off the diagonal cells.

(96)

20 / 28

The alternative representation

Topmost1is

Rightmost restricted0is Cut off the diagonal cells.

(97)

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.

(98)

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!

(99)

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

(100)

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

(101)

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

(102)

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

(103)

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

(104)

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

(105)

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

(106)

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

(107)

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

(108)

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

(109)

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

(110)

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

(111)

24 / 28

Some properties of the type B bijection

Proposition

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

(112)

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

(113)

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

(114)

24 / 28

Some properties of the type B bijection

Proposition

π= ΦB(T)

Rowmis the topmost nonzero row ofT

Decomposeπ=στ

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

(115)

24 / 28

Some properties of the type B bijection

Proposition

π= ΦB(T)

Rowmis the topmost nonzero row ofT

Decomposeπ=στ 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

(116)

24 / 28

Some properties of the type B bijection

Proposition

π= ΦB(T)

Rowmis the topmost nonzero row ofT

Decomposeπ=στ 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

(117)

24 / 28

Some properties of the type B bijection

Proposition

π= ΦB(T)

Rowmis the topmost nonzero row ofT

Decomposeπ=στ 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

(118)

24 / 28

Some properties of the type B bijection

Proposition

π= ΦB(T)

Rowmis the topmost nonzero row ofT

Decomposeπ=στ 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

(119)

24 / 28

Some properties of the type B bijection

Proposition

π= ΦB(T)

Rowmis the topmost nonzero row ofT

Decomposeπ=στ 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

(120)

24 / 28

Some properties of the type B bijection

Proposition

π= ΦB(T)

Rowmis the topmost nonzero row ofT

Decomposeπ=στ 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

(121)

24 / 28

Some properties of the type B bijection

Proposition

π= ΦB(T)

Rowmis the topmost nonzero row ofT

Decomposeπ=στ 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

(122)

25 / 28

Generalization

Theorem

X

T∈PTB(n)

xurr(T)−1ytop0,1(T)zdiag(T)= (1+z)n(x+y)n−1

(123)

25 / 28

Generalization

Theorem

X

T∈PTB(n)

xurr(T)−1ytop0,1(T)zdiag(T)= (1+z)n(x+y)n−1

(124)

25 / 28

Generalization

Theorem

X

T∈PTB(n)

xurr(T)−1ytop0,1(T)zdiag(T)= (1+z)n(x+y)n−1

m

|m| y

{

1

{

x−1

(125)

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

(126)

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

(127)

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

(128)

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ϕ◦Φ.

(129)

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

(130)

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

(131)

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)

(132)

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.

(133)

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

(134)

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

参照

関連したドキュメント

One can regard a mosaic as a crooked drawing of a puzzle with some extra rhombi in the corners; in fact, there is a straightforward bijection (see Section 2.4) between mosaics

We find the criteria for the solvability of the operator equation AX − XB = C, where A, B , and C are unbounded operators, and use the result to show existence and regularity

Showing the compactness of Poincar´e operator and using a new generalized Gronwall’s inequality with impulse, mixed type integral operators and B-norm given by us, we

Skew orthogonal tableaux are the combinatorial objects analogous to the admissible skew tableaux introduced by Sheats in [16] for type C.. To overcome this problem we are going to

We show that formulae of Gessel for the generating functions for Young standard tableaux of height bounded by k (see [2]) satisfy linear differential equations, with

The question posed after Theorem 2.1, whether there are 2 ℵ 0 closed permutation classes with counting functions mutually incomparable by the eventual dominance, has a positive

Section 7 compares Theorem 2 with another characterisation of (α, θ) partition structures provided by Pitman [13] in terms of a size-biased random permutation of parts defined

In this and in the next section we add mix arrows of the type A ∧ B ` A ∨ B to proof-net categories, together with appropriate conditions that will enable us to prove coherence