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

# Parking functions in types C and B

N/A
N/A
Protected

シェア "Parking functions in types C and B"

Copied!
220
0
0

(1)

### Parking functions in types C and B

Robin Sulzgruber joint work with Marko Thiel

Universit¨at Wien

Ellwangen, 23rd March 2015

(2)

### Outline

Regions of the Shi arrangement Finite torus

(parking functions)

Diagonally labelled paths Vertically labelled paths

(3)

### Outline

Regions of the Shi arrangement

Finite torus

(parking functions)

Diagonally labelled paths Vertically labelled paths

(4)

### Outline

Regions of the Shi arrangement Finite torus

(parking functions)

Diagonally labelled paths Vertically labelled paths

(5)

### Outline

Regions of the Shi arrangement Finite torus

(parking functions)

Diagonally labelled paths

Vertically labelled paths

(6)

### Outline

Regions of the Shi arrangement Finite torus

(parking functions)

Diagonally labelled paths Vertically labelled paths

(7)

Parking functions

### Hyperplanes and reflections

Definition

Let V be a Euclidean vector space with inner product h., .i,α∈V a nonzero vector and k ∈Z.

Define an affine hyperplane

Hα,k ={x ∈V :hx, αi=k}. Letsα,k be the reflection throughHα,k.

sα,k(x) =x−2hx, αi −2k hα, αi α.

(8)

Parking functions

### Hyperplanes and reflections

Definition

Let V be a Euclidean vector space with inner product h., .i,α∈V a nonzero vector and k ∈Z.

Define an affine hyperplane

Hα,k ={x ∈V :hx, αi=k}. Letsα,k be the reflection throughHα,k.

sα,k(x) =x−2hx, αi −2k hα, αi α.

(9)

Parking functions

### Hyperplanes and reflections

Definition

Let V be a Euclidean vector space with inner product h., .i,α∈V a nonzero vector and k ∈Z.

Define an affine hyperplane

Hα,k ={x∈V :hx, αi=k}.

Letsα,k be the reflection throughHα,k.

sα,k(x) =x−2hx, αi −2k hα, αi α.

(10)

Parking functions

### Hyperplanes and reflections

Definition

Let V be a Euclidean vector space with inner product h., .i,α∈V a nonzero vector and k ∈Z.

Define an affine hyperplane

Hα,k ={x∈V :hx, αi=k}.

Letsα,k be thereflectionthrough Hα,k.

sα,k(x) =x−2hx, αi −2k hα, αi α.

(11)

Parking functions

### Roots

Definition

A crystallographic root system of V is a finite spanning subset Φ⊆V of nonzero vectors such that

Rα∩Φ ={α,−α}for all α∈Φ, sα,0(Φ)⊆Φ for allα ∈Φ, 2hβ, αi

hα, αi ∈Z for all α, β∈Φ. Let Φ+ denote the positive roots.

We only consider irreducible root systems.

Example

2e1

e2+e1 2e2

e2−e1

The root system of typeC2 in V =R2.

(12)

Parking functions

### Roots

Definition

Acrystallographic root systemof V is a finite spanning subset Φ⊆V of nonzero vectors such that

Rα∩Φ ={α,−α} for all α∈Φ, sα,0(Φ)⊆Φ for allα∈Φ, 2hβ, αi

hα, αi ∈Z for all α, β∈Φ. Let Φ+ denote thepositive roots. We only consider irreducible root systems.

Example

2e1

e2+e1 2e2

e2−e1

The root system of typeC2 in V =R2.

(13)

Parking functions

### Roots

Definition

A crystallographic root system of V is a finite spanning subset Φ⊆V of nonzero vectors such that

Rα∩Φ ={α,−α} for all α∈Φ,

sα,0(Φ)⊆Φ for allα∈Φ, 2hβ, αi

hα, αi ∈Z for all α, β∈Φ. Let Φ+ denote the positive roots. We only consider irreducible root systems.

Example

2e1

e2+e1 2e2

e2−e1

The root system of typeC2 in V =R2.

(14)

Parking functions

### Roots

Definition

A crystallographic root system of V is a finite spanning subset Φ⊆V of nonzero vectors such that

Rα∩Φ ={α,−α} for all α∈Φ, sα,0(Φ)⊆Φ for allα∈Φ,

2hβ, αi

hα, αi ∈Z for all α, β∈Φ. Let Φ+ denote the positive roots. We only consider irreducible root systems.

Example

2e1

e2+e1 2e2

e2−e1

The root system of typeC2 in V =R2.

(15)

Parking functions

### Roots

Definition

A crystallographic root system of V is a finite spanning subset Φ⊆V of nonzero vectors such that

Rα∩Φ ={α,−α} for all α∈Φ, sα,0(Φ)⊆Φ for allα∈Φ, 2hβ, αi

hα, αi ∈Z for all α, β∈Φ.

Let Φ+ denote the positive roots. We only consider irreducible root systems.

Example

2e1

e2+e1 2e2

e2−e1

The root system of typeC2 in V =R2.

(16)

Parking functions

### Roots

Definition

A crystallographic root system of V is a finite spanning subset Φ⊆V of nonzero vectors such that

Rα∩Φ ={α,−α} for all α∈Φ, sα,0(Φ)⊆Φ for allα∈Φ, 2hβ, αi

hα, αi ∈Z for all α, β∈Φ.

Let Φ+ denote the positive roots. We only consider irreducible root systems.

Example

2e1

e2+e1 2e2

e2−e1

(17)

Parking functions

### Roots

Definition

A crystallographic root system of V is a finite spanning subset Φ⊆V of nonzero vectors such that

Rα∩Φ ={α,−α} for all α∈Φ, sα,0(Φ)⊆Φ for allα∈Φ, 2hβ, αi

hα, αi ∈Z for all α, β∈Φ.

LetΦ+ denote the positive roots.

We only consider irreducible root systems.

Example

2e1

e2+e1 2e2

e2−e1

The root system of typeC2 in V =R2.

(18)

Parking functions

### Roots

Definition

A crystallographic root system of V is a finite spanning subset Φ⊆V of nonzero vectors such that

Rα∩Φ ={α,−α} for all α∈Φ, sα,0(Φ)⊆Φ for allα∈Φ, 2hβ, αi

hα, αi ∈Z for all α, β∈Φ.

Let Φ+ denote the positive roots.

Example

2e1

e2+e1 2e2

e2−e1

(19)

Parking functions

### The coroot lattice and the finite torus

Definition

For each root α∈Φ define the corresponding coroot as

ˇ

α= 2

hα, αiα.

Define the coroot lattice as Qˇ = X

α∈Φ+

ˇ αZ.

Define the finite torus as T = ˇQ/(h+ 1) ˇQ.

Example: Type C

The positive roots are given by Φ+={ej±ei : 1≤i <j ≤n}

∪ {2ei : 1≤i ≤n}.

The coroot lattice is Qˇ =Zn. The finite torus is

Zn/(2n+ 1)Zn.

(20)

Parking functions

### The coroot lattice and the finite torus

Definition

For each root α∈Φ define the corresponding corootas

ˇ

α= 2

hα, αiα.

Define the coroot lattice as Qˇ = X

α∈Φ+

ˇ αZ.

Define the finite torus as T = ˇQ/(h+ 1) ˇQ.

Example: Type C

The positive roots are given by Φ+={ej±ei : 1≤i <j ≤n}

∪ {2ei : 1≤i ≤n}.

The coroot lattice is Qˇ =Zn. The finite torus is

Zn/(2n+ 1)Zn.

(21)

Parking functions

### The coroot lattice and the finite torus

Definition

For each root α∈Φ define the corresponding coroot as

ˇ

α= 2

hα, αiα.

Define thecoroot latticeas Qˇ = X

α∈Φ+

ˇ αZ.

Define the finite torus as T = ˇQ/(h+ 1) ˇQ.

Example: Type C

The positive roots are given by Φ+={ej±ei : 1≤i <j ≤n}

∪ {2ei : 1≤i ≤n}.

The coroot lattice is Qˇ =Zn. The finite torus is

Zn/(2n+ 1)Zn.

(22)

Parking functions

### The coroot lattice and the finite torus

Definition

For each root α∈Φ define the corresponding coroot as

ˇ

α= 2

hα, αiα.

Define the coroot lattice as Qˇ = X

α∈Φ+

ˇ αZ.

Define the finite torusas T = ˇQ/(h+ 1) ˇQ.

Example: Type C

The positive roots are given by Φ+={ej±ei : 1≤i <j ≤n}

∪ {2ei : 1≤i ≤n}.

The coroot lattice is Qˇ =Zn. The finite torus is

Zn/(2n+ 1)Zn.

(23)

Parking functions

### The coroot lattice and the finite torus

Definition

For each root α∈Φ define the corresponding coroot as

ˇ

α= 2

hα, αiα.

Define the coroot lattice as Qˇ = X

α∈Φ+

ˇ αZ.

Define the finite torus as T = ˇQ/(h+ 1) ˇQ.

Example: Type C

The positive roots are given by Φ+={ej±ei : 1≤i <j ≤n}

∪ {2ei : 1≤i ≤n}.

The coroot lattice is Qˇ =Zn. The finite torus is

Zn/(2n+ 1)Zn.

(24)

Parking functions

### The coroot lattice and the finite torus

Definition

For each root α∈Φ define the corresponding coroot as

ˇ

α= 2

hα, αiα.

Define the coroot lattice as Qˇ = X

α∈Φ+

ˇ αZ.

Define the finite torus as T = ˇQ/(h+ 1) ˇQ.

Example: Type C

The positive roots are given by Φ+={ej±ei : 1≤i <j ≤n}

∪ {2ei : 1≤i ≤n}.

The coroot lattice is Qˇ =Zn.

The finite torus is Zn/(2n+ 1)Zn.

(25)

Parking functions

### The coroot lattice and the finite torus

Definition

For each root α∈Φ define the corresponding coroot as

ˇ

α= 2

hα, αiα.

Define the coroot lattice as Qˇ = X

α∈Φ+

ˇ αZ.

Define the finite torus as T = ˇQ/(h+ 1) ˇQ.

Example: Type C

The positive roots are given by Φ+={ej±ei : 1≤i <j ≤n}

∪ {2ei : 1≤i ≤n}.

The coroot lattice is Qˇ =Zn. The finite torus is

Zn/(2n+ 1)Zn.

(26)

Parking functions

### Classical parking functions

Definition

A classical parking function is an integer vector

f = (f1,f2, . . . ,fn) with nonnegative entries such that there exists a permutation σ∈Sn with

fσ(i)≤i−1.

Example

f = (1,4,0,0,4,4,1)

σ·f = (0,0,1,1,4,4,4)

≤(0,1,2,3,4,5,6)

(27)

Parking functions

### Classical parking functions

Definition

Aclassical parking function is an integer vector

f = (f1,f2, . . . ,fn) with nonnegative entries such that there exists a permutation σ∈Sn with

fσ(i)≤i−1.

Example

f = (1,4,0,0,4,4,1)

σ·f = (0,0,1,1,4,4,4)

≤(0,1,2,3,4,5,6)

(28)

Parking functions

### Classical parking functions

Definition

A classical parking function is an integer vector

f = (f1,f2, . . . ,fn) with nonnegative entries such that there exists a permutation σ∈Sn with

fσ(i)≤i−1.

Example

f = (1,4,0,0,4,4,1)

σ·f = (0,0,1,1,4,4,4)

≤(0,1,2,3,4,5,6)

(29)

Parking functions

### Classical parking functions

Definition

A classical parking function is an integer vector

f = (f1,f2, . . . ,fn) with nonnegative entries such that there exists a permutation σ∈Sn with

fσ(i)≤i−1.

Example

f = (1,4,0,0,4,4,1) σ·f = (0,0,1,1,4,4,4)

≤(0,1,2,3,4,5,6)

(30)

Parking functions

### Classical parking functions

Definition

A classical parking function is an integer vector

f = (f1,f2, . . . ,fn) with nonnegative entries such that there exists a permutation σ∈Sn with

fσ(i)≤i−1.

Example

f = (1,4,0,0,4,4,1) σ·f = (0,0,1,1,4,4,4)

≤(0,1,2,3,4,5,6)

(31)

Parking functions

### Parking functions of type A and C

Proposition

The set of classical parking functions of length n is a natural system of representatives for the finite torus of type An−1.

Recall that Zn/(2n+ 1)Zn is the finite torus of typeCn. Definition

We define parking functions of type C as integer vectors f = (f1,f2, . . . ,fn) where −n ≤fi ≤n.

(32)

Parking functions

### Parking functions of type A and C

Proposition

The set of classical parking functions of length n is a natural system of representatives for the finite torus of type An−1.

Recall that Zn/(2n+ 1)Zn is the finite torus of typeCn. Definition

We define parking functions of type C as integer vectors f = (f1,f2, . . . ,fn) where −n ≤fi ≤n.

(33)

Parking functions

### Parking functions of type A and C

Proposition

The set of classical parking functions of length n is a natural system of representatives for the finite torus of type An−1.

Recall that Zn/(2n+ 1)Zn is the finite torus of typeCn.

Definition

We define parking functions of type C as integer vectors f = (f1,f2, . . . ,fn) where −n ≤fi ≤n.

(34)

Parking functions

### Parking functions of type A and C

Proposition

The set of classical parking functions of length n is a natural system of representatives for the finite torus of type An−1.

Recall that Zn/(2n+ 1)Zn is the finite torus of typeCn. Definition

We define parking functions of type C as integer vectors f = (f1,f2, . . . ,fn) where−n≤fi ≤n.

(35)

Parking functions

### Vertically labelled Dyck paths

Definition

A vertically labelled Dyck path is a pair (π, σ) of a Dyck path π∈ Dnand a permutation σ∈Sn such that

σi < σi+1

for each rise i ofπ.

We calli a rise if thei-th North step is followed by a North step.

Example

The rises of π are i = 1,3,5,6. Let σ= 3417256. The pair (π, σ) is a vertical labelling.

(36)

Parking functions

### Vertically labelled Dyck paths

Definition

Avertically labelled Dyck path is a pair (π, σ) of a Dyck path π∈ Dn and a permutation σ∈Sn such that

σi < σi+1 for each rise i ofπ.

We calli a rise if thei-th North step is followed by a North step.

Example

The rises of π are i = 1,3,5,6. Let σ= 3417256. The pair (π, σ) is a vertical labelling.

(37)

Parking functions

### Vertically labelled Dyck paths

Definition

A vertically labelled Dyck path is a pair (π, σ) of a Dyck path π∈ Dn and a permutation σ∈Sn such that

σi < σi+1 for each rise i ofπ.

We calli arise if thei-th North step is followed by a North step.

Example

The rises of π are i = 1,3,5,6. Let σ= 3417256. The pair (π, σ) is a vertical labelling.

(38)

Parking functions

### Vertically labelled Dyck paths

Definition

A vertically labelled Dyck path is a pair (π, σ) of a Dyck path π∈ Dn and a permutation σ∈Sn such that

σi < σi+1 for each rise i ofπ.

We calli a rise if thei-th North step is followed by a North step.

Example

The rises of π are i = 1,3,5,6. Let σ= 3417256. The pair (π, σ) is a vertical labelling.

(39)

Parking functions

### Vertically labelled Dyck paths

Definition

A vertically labelled Dyck path is a pair (π, σ) of a Dyck path π∈ Dn and a permutation σ∈Sn such that

σi < σi+1 for each rise i ofπ.

We calli a rise if thei-th North step is followed by a North step.

Example

The rises of π are i =1,3,5,6.

Let σ= 3417256. The pair (π, σ) is a vertical labelling.

(40)

Parking functions

### Vertically labelled Dyck paths

Definition

A vertically labelled Dyck path is a pair (π, σ) of a Dyck path π∈ Dn and a permutation σ∈Sn such that

σi < σi+1 for each rise i ofπ.

We calli a rise if thei-th North step is followed by a North step.

Example

The rises of π are i = 1,3,5,6.

Let σ= 3417256. The pair (π, σ) is a vertical labelling.

(41)

Parking functions

### Vertically labelled Dyck paths

Definition

A vertically labelled Dyck path is a pair (π, σ) of a Dyck path π∈ Dn and a permutation σ∈Sn such that

σi < σi+1 for each rise i ofπ.

We calli a rise if thei-th North step is followed by a North step.

Example

The rises of π are i = 1,3,5,6.

Let σ= 3417256. The pair (π, σ) is a vertical labelling.

(42)

Parking functions

### Vertically labelled Dyck paths

Definition

A vertically labelled Dyck path is a pair (π, σ) of a Dyck path π∈ Dn and a permutation σ∈Sn such that

σi < σi+1 for each rise i ofπ.

We calli a rise if thei-th North step is followed by a North step.

Example

The rises of π are i = 1,3,5,6.

Let σ= 3417256. The pair (π, σ) is a vertical labelling.

(43)

Parking functions

### Vertically labelled Dyck paths

Definition

A vertically labelled Dyck path is a pair (π, σ) of a Dyck path π∈ Dn and a permutation σ∈Sn such that

σi < σi+1 for each rise i ofπ.

We calli a rise if thei-th North step is followed by a North step.

Example

The rises of π are i = 1,3,5,6.

Let σ= 3417256.

The pair (π, σ) is a vertical labelling.

(44)

Parking functions

### Vertically labelled Dyck paths

Definition

A vertically labelled Dyck path is a pair (π, σ) of a Dyck path π∈ Dn and a permutation σ∈Sn such that

σi < σi+1 for each rise i ofπ.

We calli a rise if thei-th North step is followed by a North step.

Example

3

The rises of π are i = 1,3,5,6.

Let σ=3417256.

The pair (π, σ) is a vertical labelling.

(45)

Parking functions

### Vertically labelled Dyck paths

Definition

A vertically labelled Dyck path is a pair (π, σ) of a Dyck path π∈ Dn and a permutation σ∈Sn such that

σi < σi+1 for each rise i ofπ.

We calli a rise if thei-th North step is followed by a North step.

Example

3 4

The rises of π are i = 1,3,5,6.

Let σ= 3417256.

The pair (π, σ) is a vertical labelling.

(46)

Parking functions

### Vertically labelled Dyck paths

Definition

A vertically labelled Dyck path is a pair (π, σ) of a Dyck path π∈ Dn and a permutation σ∈Sn such that

σi < σi+1 for each rise i ofπ.

We calli a rise if thei-th North step is followed by a North step.

Example

3 4

1

The rises of π are i = 1,3,5,6.

Let σ= 3417256.

The pair (π, σ) is a vertical labelling.

(47)

Parking functions

### Vertically labelled Dyck paths

Definition

A vertically labelled Dyck path is a pair (π, σ) of a Dyck path π∈ Dn and a permutation σ∈Sn such that

σi < σi+1 for each rise i ofπ.

We calli a rise if thei-th North step is followed by a North step.

Example

3 4

1 7

The rises of π are i = 1,3,5,6.

Let σ= 3417256.

The pair (π, σ) is a vertical labelling.

(48)

Parking functions

### Vertically labelled Dyck paths

Definition

A vertically labelled Dyck path is a pair (π, σ) of a Dyck path π∈ Dn and a permutation σ∈Sn such that

σi < σi+1 for each rise i ofπ.

We calli a rise if thei-th North step is followed by a North step.

Example

3 4

1 7

2

The rises of π are i = 1,3,5,6.

Let σ= 3417256.

The pair (π, σ) is a vertical labelling.

(49)

Parking functions

### Vertically labelled Dyck paths

Definition

A vertically labelled Dyck path is a pair (π, σ) of a Dyck path π∈ Dn and a permutation σ∈Sn such that

σi < σi+1 for each rise i ofπ.

We calli a rise if thei-th North step is followed by a North step.

Example

3 4

1 7

2 5

The rises of π are i = 1,3,5,6.

Let σ= 3417256.

The pair (π, σ) is a vertical labelling.

(50)

Parking functions

### Vertically labelled Dyck paths

Definition

A vertically labelled Dyck path is a pair (π, σ) of a Dyck path π∈ Dn and a permutation σ∈Sn such that

σi < σi+1 for each rise i ofπ.

We calli a rise if thei-th North step is followed by a North step.

Example

3 4

1 7

2 5 6

The rises of π are i = 1,3,5,6.

Let σ= 3417256.

The pair (π, σ) is a vertical labelling.

(51)

Parking functions

### Vertically labelled Dyck paths

Definition

A vertically labelled Dyck path is a pair (π, σ) of a Dyck path π∈ Dn and a permutation σ∈Sn such that

σi < σi+1 for each rise i ofπ.

We calli a rise if thei-th North step is followed by a North step.

Example

3 4

1 7

2 5 6

The rises of π are i =1,3,5,6.

Let σ=3417256.

The pair (π, σ) is a vertical labelling.

(52)

Parking functions

### Vertically labelled Dyck paths

Definition

A vertically labelled Dyck path is a pair (π, σ) of a Dyck path π∈ Dn and a permutation σ∈Sn such that

σi < σi+1 for each rise i ofπ.

We calli a rise if thei-th North step is followed by a North step.

Example

3 4

1 7

2 5 6

The rises of π are i = 1,3,5,6.

Let σ= 3417256.

The pair (π, σ) is a vertical labelling.

(53)

Parking functions

### Vertically labelled Dyck paths

Definition

A vertically labelled Dyck path is a pair (π, σ) of a Dyck path π∈ Dn and a permutation σ∈Sn such that

σi < σi+1 for each rise i ofπ.

We calli a rise if thei-th North step is followed by a North step.

Example

3 4

1 7

2 5 6

The rises of π are i = 1,3,5,6.

Let σ= 3417256.

The pair (π, σ) is a vertical labelling.

(54)

Parking functions

### Vertically labelled Dyck paths

Definition

A vertically labelled Dyck path is a pair (π, σ) of a Dyck path π∈ Dn and a permutation σ∈Sn such that

σi < σi+1 for each rise i ofπ.

We calli a rise if thei-th North step is followed by a North step.

Example

3 4

1 7

2 5 6

The rises of π are i = 1,3,5,6.

Let σ= 3417256.

The pair (π, σ) is a vertical labelling.

(55)

Parking functions

### Vertically labelled Dyck paths

Definition

A vertically labelled Dyck path is a pair (π, σ) of a Dyck path π∈ Dn and a permutation σ∈Sn such that

σi < σi+1 for each rise i ofπ.

We calli a rise if thei-th North step is followed by a North step.

Example

3 4

1 7

2 5 6

The rises of π are i = 1,3,5,6.

Let σ= 3417256. The pair (π, σ) is a vertical labelling.

(56)

Parking functions

### From vertically labelled Dyck paths to parking functions

Vertically labelled Dyck paths

3 4

1 7

2 5 6 0

Classical parking functions There is a natural way to construct the parking function corresponding to a vertically labelled Dyck path.

f = (

1

,

4

,

0

,

0

,

4

,

4

,

1

)

(57)

Parking functions

### From vertically labelled Dyck paths to parking functions

Vertically labelled Dyck paths

3 4

1 7

2 5 6 0

Classical parking functions There is a natural way to construct the parking function corresponding to a vertically labelled Dyck path.

f = (

1

,

4

,

0

,

0

,

4

,

4

,

1

)

(58)

Parking functions

### From vertically labelled Dyck paths to parking functions

Vertically labelled Dyck paths

3 4

1 7

2 5 6 0

Classical parking functions There is a natural way to construct the parking function corresponding to a vertically labelled Dyck path.

f = (

1

,

4

,

0

,

0

,

4

,

4

,

1

)

(59)

Parking functions

### From vertically labelled Dyck paths to parking functions

Vertically labelled Dyck paths

3 4

1 7

2 5 6 0

0

Classical parking functions There is a natural way to construct the parking function corresponding to a vertically labelled Dyck path.

f = (

1

,

4

,

0

,

0

,

4

,

4

,

1

)

(60)

Parking functions

### From vertically labelled Dyck paths to parking functions

Vertically labelled Dyck paths

3 4

1 7

2 5 6 0

0 1

Classical parking functions There is a natural way to construct the parking function corresponding to a vertically labelled Dyck path.

f = (

1

,

4

,

0

,

0

,

4

,

4

,

1

)

(61)

Parking functions

### From vertically labelled Dyck paths to parking functions

Vertically labelled Dyck paths

3 4

1 7

2 5 6 0

0 1 2

Classical parking functions There is a natural way to construct the parking function corresponding to a vertically labelled Dyck path.

f = (

1

,

4

,

0

,

0

,

4

,

4

,

1

)

(62)

Parking functions

### From vertically labelled Dyck paths to parking functions

Vertically labelled Dyck paths

3 4

1 7

2 5 6 0

0 1 2 3

Classical parking functions There is a natural way to construct the parking function corresponding to a vertically labelled Dyck path.

f = (

1

,

4

,

0

,

0

,

4

,

4

,

1

)

(63)

Parking functions

### From vertically labelled Dyck paths to parking functions

Vertically labelled Dyck paths

3 4

1 7

2 5 6 0

0 1 2 3 4

Classical parking functions There is a natural way to construct the parking function corresponding to a vertically labelled Dyck path.

f = (

1

,

4

,

0

,

0

,

4

,

4

,

1

)

(64)

Parking functions

### From vertically labelled Dyck paths to parking functions

Vertically labelled Dyck paths

3 4

1 7

2 5 6 0

0 1 2 3 4 5

Classical parking functions There is a natural way to construct the parking function corresponding to a vertically labelled Dyck path.

f = (

1

,

4

,

0

,

0

,

4

,

4

,

1

)

(65)

Parking functions

### From vertically labelled Dyck paths to parking functions

Vertically labelled Dyck paths

3 4

1 7

2 5 6 0

0 1 2 3 4 5 6

Classical parking functions There is a natural way to construct the parking function corresponding to a vertically labelled Dyck path.

f = (

1

,

4

,

0

,

0

,

4

,

4

,

1

)

(66)

Parking functions

### From vertically labelled Dyck paths to parking functions

Vertically labelled Dyck paths

3 4

1 7

2 5 6 0

0 1 2 3 4 5 6

Classical parking functions There is a natural way to construct the parking function corresponding to a vertically labelled Dyck path.

f = (

1

,

4

,0,

0

,

4

,

4

,

1

)

(67)

Parking functions

### From vertically labelled Dyck paths to parking functions

Vertically labelled Dyck paths

3 4

1 7

2 5 6 0

0 1 2 3 4 5 6

Classical parking functions There is a natural way to construct the parking function corresponding to a vertically labelled Dyck path.

f = (

1

,

4

,0,0,

4

,

4

,

1

)

(68)

Parking functions

### From vertically labelled Dyck paths to parking functions

Vertically labelled Dyck paths

3 4

1 7

2 5 6 0

0 1 2 3 4 5 6

Classical parking functions There is a natural way to construct the parking function corresponding to a vertically labelled Dyck path.

f = (1,

4

,0,0,

4

,

4

,

1

)

(69)

Parking functions

### From vertically labelled Dyck paths to parking functions

Vertically labelled Dyck paths

3 4

1 7

2 5 6 0

0 1 2 3 4 5 6

Classical parking functions There is a natural way to construct the parking function corresponding to a vertically labelled Dyck path.

f = (1,

4

,0,0,

4

,

4

,1)

(70)

Parking functions

### From vertically labelled Dyck paths to parking functions

Vertically labelled Dyck paths

3 4

1 7

2 5 6 0

0 1 2 3 4 5 6

Classical parking functions There is a natural way to construct the parking function corresponding to a vertically labelled Dyck path.

f = (1,4,0,0,

4

,

4

,1)

(71)

Parking functions

### From vertically labelled Dyck paths to parking functions

Vertically labelled Dyck paths

3 4

1 7

2 5 6 0

0 1 2 3 4 5 6

Classical parking functions There is a natural way to construct the parking function corresponding to a vertically labelled Dyck path.

f = (1,4,0,0,4,

4

,1)

(72)

Parking functions

### From vertically labelled Dyck paths to parking functions

Vertically labelled Dyck paths

3 4

1 7

2 5 6 0

0 1 2 3 4 5 6

Classical parking functions There is a natural way to construct the parking function corresponding to a vertically labelled Dyck path.

f = (1,4,0,0,4,4,1)

(73)

Parking functions

### Vertically labelled lattice paths

Definition

A vertically labelled lattice path is a pair (π, σ) of a lattice path π∈ Ln from (0,0) to (n,n) and a signed permutationσ ∈Hn such that

σi < σi+1

for each risei of π, and such that 0< σ1

ifπ begins with a North step.

Example

1

The rises of π are i = 2,3,4,5. Moreover, π begins with a North step.

Let σ= 1(−5)(−4)236. The pair (π, σ) is a vertical labelling.

(74)

Parking functions

### Vertically labelled lattice paths

Definition

Avertically labelled lattice path is a pair(π, σ)of a lattice path π∈ Ln from (0,0) to (n,n) and a signed permutationσ ∈Hn such that

σi < σi+1

for each risei of π, and such that 0< σ1

Example

1

The rises of π are i = 2,3,4,5. Moreover, π begins with a North step.

Let σ= 1(−5)(−4)236. The pair (π, σ) is a vertical labelling.

(75)

Parking functions

### Vertically labelled lattice paths

Definition

A vertically labelled lattice path is a pair (π, σ) of a lattice path π∈ Ln from (0,0) to (n,n) and a signed permutationσ ∈Hn such that

σi < σi+1

for each risei of π, and such that 0< σ1

ifπ begins with a North step.

Example

1

The rises of π are i = 2,3,4,5. Moreover, π begins with a North step.

Let σ= 1(−5)(−4)236. The pair (π, σ) is a vertical labelling.

(76)

Parking functions

### Vertically labelled lattice paths

Definition

A vertically labelled lattice path is a pair (π, σ) of a lattice path π∈ Ln from (0,0) to (n,n) and a signed permutationσ ∈Hn such that

σi < σi+1

for each risei of π, and such that 0< σ1

Example

1

The rises of π are i =2,3,4,5.

Moreover, π begins with a North step.

Let σ= 1(−5)(−4)236. The pair (π, σ) is a vertical labelling.

(77)

Parking functions

### Vertically labelled lattice paths

Definition

A vertically labelled lattice path is a pair (π, σ) of a lattice path π∈ Ln from (0,0) to (n,n) and a signed permutationσ ∈Hn such that

σi < σi+1

for each risei of π, and such that 0< σ1

ifπ begins with a North step.

Example

1

The rises of π are i = 2,3,4,5.

Moreover, π begins with a North step.

Let σ= 1(−5)(−4)236. The pair (π, σ) is a vertical labelling.

(78)

Parking functions

### Vertically labelled lattice paths

Definition

A vertically labelled lattice path is a pair (π, σ) of a lattice path π∈ Ln from (0,0) to (n,n) and a signed permutationσ ∈Hn such that

σi < σi+1

for each risei of π, and such that 0< σ1

Example

1

The rises of π are i = 2,3,4,5.

Moreover, π begins with a North step.

Let σ= 1(−5)(−4)236. The pair (π, σ) is a vertical labelling.

(79)

Parking functions

### Vertically labelled lattice paths

Definition

A vertically labelled lattice path is a pair (π, σ) of a lattice path π∈ Ln from (0,0) to (n,n) and a signed permutationσ ∈Hn such that

σi < σi+1

for each risei of π, and such that 0< σ1

ifπ begins with a North step.

Example

1

The rises of π are i = 2,3,4,5.

Moreover, π begins with a North step.

Let σ= 1(−5)(−4)236. The pair (π, σ) is a vertical labelling.

(80)

Parking functions

### Vertically labelled lattice paths

Definition

A vertically labelled lattice path is a pair (π, σ) of a lattice path π∈ Ln from (0,0) to (n,n) and a signed permutationσ ∈Hn such that

σi < σi+1

for each risei of π, and such that 0< σ1

Example

1

The rises of π are i = 2,3,4,5.

Moreover, π begins with a North step.

Let σ= 1(−5)(−4)236. The pair (π, σ) is a vertical labelling.

(81)

Parking functions

### Vertically labelled lattice paths

Definition

A vertically labelled lattice path is a pair (π, σ) of a lattice path π∈ Ln from (0,0) to (n,n) and a signed permutationσ ∈Hn such that

σi < σi+1

for each risei of π, and such that 0< σ1

ifπ begins with a North step.

Example

1

The rises of π are i = 2,3,4,5.

Moreover, π begins with a North step.

Let σ= 1(−5)(−4)236.

The pair (π, σ) is a vertical labelling.

(82)

Parking functions

### Vertically labelled lattice paths

Definition

A vertically labelled lattice path is a pair (π, σ) of a lattice path π∈ Ln from (0,0) to (n,n) and a signed permutationσ ∈Hn such that

σi < σi+1

for each risei of π, and such that 0< σ1

Example

1

The rises of π are i = 2,3,4,5.

Moreover, π begins with a North step.

The pair (π, σ) is a vertical labelling.

(83)

Parking functions

### Vertically labelled lattice paths

Definition

A vertically labelled lattice path is a pair (π, σ) of a lattice path π∈ Ln from (0,0) to (n,n) and a signed permutationσ ∈Hn such that

σi < σi+1

for each risei of π, and such that 0< σ1

ifπ begins with a North step.

Example

1

−5

The rises of π are i = 2,3,4,5.

Moreover, π begins with a North step.

Let σ= 1(−5)(−4)236.

The pair (π, σ) is a vertical labelling.

(84)

Parking functions

### Vertically labelled lattice paths

Definition

A vertically labelled lattice path is a pair (π, σ) of a lattice path π∈ Ln from (0,0) to (n,n) and a signed permutationσ ∈Hn such that

σi < σi+1

for each risei of π, and such that 0< σ1

Example

1

−5

−4

The rises of π are i = 2,3,4,5.

Moreover, π begins with a North step.

The pair (π, σ) is a vertical labelling.

(85)

Parking functions

### Vertically labelled lattice paths

Definition

A vertically labelled lattice path is a pair (π, σ) of a lattice path π∈ Ln from (0,0) to (n,n) and a signed permutationσ ∈Hn such that

σi < σi+1

for each risei of π, and such that 0< σ1

ifπ begins with a North step.

Example

1

−5

−4 2

The rises of π are i = 2,3,4,5.

Moreover, π begins with a North step.

Let σ= 1(−5)(−4)236.

The pair (π, σ) is a vertical labelling.

(86)

Parking functions

### Vertically labelled lattice paths

Definition

A vertically labelled lattice path is a pair (π, σ) of a lattice path π∈ Ln from (0,0) to (n,n) and a signed permutationσ ∈Hn such that

σi < σi+1

for each risei of π, and such that 0< σ1

Example

1

−5

−4 2 3

The rises of π are i = 2,3,4,5.

Moreover, π begins with a North step.

The pair (π, σ) is a vertical labelling.

(87)

Parking functions

### Vertically labelled lattice paths

Definition

A vertically labelled lattice path is a pair (π, σ) of a lattice path π∈ Ln from (0,0) to (n,n) and a signed permutationσ ∈Hn such that

σi < σi+1

for each risei of π, and such that 0< σ1

ifπ begins with a North step.

Example

1

−5

−4 2 3 6

The rises of π are i = 2,3,4,5.

Moreover, π begins with a North step.

Let σ= 1(−5)(−4)236.

The pair (π, σ) is a vertical labelling.

(88)

Parking functions

### Vertically labelled lattice paths

Definition

A vertically labelled lattice path is a pair (π, σ) of a lattice path π∈ Ln from (0,0) to (n,n) and a signed permutationσ ∈Hn such that

σi < σi+1

for each risei of π, and such that 0< σ1

Example

1

−5

−4 2 3 6

The rises of π are i =2,3,4,5.

Moreover, π begins with a North step.

The pair (π, σ) is a vertical labelling.

(89)

Parking functions

### Vertically labelled lattice paths

Definition

A vertically labelled lattice path is a pair (π, σ) of a lattice path π∈ Ln from (0,0) to (n,n) and a signed permutationσ ∈Hn such that

σi < σi+1

for each risei of π, and such that 0< σ1

ifπ begins with a North step.

Example

1

−5

−4 2 3 6

The rises of π are i = 2,3,4,5.

Moreover, π begins with a North step.

Let σ= 1(−5)(−4)236.

The pair (π, σ) is a vertical labelling.

(90)

Parking functions

### Vertically labelled lattice paths

Definition

A vertically labelled lattice path is a pair (π, σ) of a lattice path π∈ Ln from (0,0) to (n,n) and a signed permutationσ ∈Hn such that

σi < σi+1

for each risei of π, and such that 0< σ1

Example

1

−5

−4 2 3 6

The rises of π are i = 2,3,4,5.

Moreover, π begins with a North step.

The pair (π, σ) is a vertical labelling.

(91)

Parking functions

### Vertically labelled lattice paths

Definition

A vertically labelled lattice path is a pair (π, σ) of a lattice path π∈ Ln from (0,0) to (n,n) and a signed permutationσ ∈Hn such that

σi < σi+1

for each risei of π, and such that 0< σ1

ifπ begins with a North step.

Example

1

−5

−4 2 3 6

The rises of π are i = 2,3,4,5.

Moreover, π begins with a North step.

Let σ= 1(−5)(−4)236.

The pair (π, σ) is a vertical labelling.

(92)

Parking functions

### Vertically labelled lattice paths

Definition

A vertically labelled lattice path is a pair (π, σ) of a lattice path π∈ Ln from (0,0) to (n,n) and a signed permutationσ ∈Hn such that

σi < σi+1

for each risei of π, and such that 0< σ1

Example

1

−5

−4 2 3 6

The rises of π are i = 2,3,4,5.

Moreover, π begins with a North step.

The pair (π, σ) is a vertical labelling.

(93)

Parking functions

### Vertically labelled lattice paths

Definition

A vertically labelled lattice path is a pair (π, σ) of a lattice path π∈ Ln from (0,0) to (n,n) and a signed permutationσ ∈Hn such that

σi < σi+1

for each risei of π, and such that 0< σ1

ifπ begins with a North step.

Example

1

−5

−4 2 3 6

The rises of π are i = 2,3,4,5.

Moreover, π begins with a North step.

Let σ= 1(−5)(−4)236. The pair (π, σ) is a vertical labelling.

(94)

Parking functions

### From vertically labelled lattice paths to parking functions

Vertically labelled lattice paths

1

−5

−4 2 3 6

0

Type C parking functions There is a natural bijection between typeC parking functions and vertically labelled lattice paths.

f = (

0

,

4

,

4

,

−4

,

−4

,

4

)

(95)

Parking functions

### From vertically labelled lattice paths to parking functions

Vertically labelled lattice paths

1

−5

−4 2 3 6

0 Type C parking functions

There is a natural bijection between typeC parking functions and vertically labelled lattice paths.

f = (

0

,

4

,

4

,

−4

,

−4

,

4

)

(96)

Parking functions

### From vertically labelled lattice paths to parking functions

Vertically labelled lattice paths

1

−5

−4 2 3 6

0

Type C parking functions There is a natural bijection between typeC parking functions and vertically labelled lattice paths.

f = (

0

,

4

,

4

,

−4

,

−4

,

4

)

(97)

Parking functions

### From vertically labelled lattice paths to parking functions

Vertically labelled lattice paths

1

−5

−4 2 3 6

0 Type C parking functions

There is a natural bijection between typeC parking functions and vertically labelled lattice paths.

f = (

0

,

4

,

4

,

−4

,

−4

,

4

)

(98)

Parking functions

### From vertically labelled lattice paths to parking functions

Vertically labelled lattice paths

1

−5

−4 2 3 6

0 1 Type C parking functions

There is a natural bijection between typeC parking functions and vertically labelled lattice paths.

f = (

0

,

4

,

4

,

−4

,

−4

,

4

)

(99)

Parking functions

### From vertically labelled lattice paths to parking functions

Vertically labelled lattice paths

1

−5

−4 2 3 6

0 1 2 Type C parking functions

There is a natural bijection between typeC parking functions and vertically labelled lattice paths.

f = (

0

,

4

,

4

,

−4

,

−4

,

4

)

(100)

Parking functions

### From vertically labelled lattice paths to parking functions

Vertically labelled lattice paths

1

−5

−4 2 3 6

0 1 2 3 Type C parking functions

There is a natural bijection between typeC parking functions and vertically labelled lattice paths.

f = (

0

,

4

,

4

,

−4

,

−4

,

4

)

(101)

Parking functions

### From vertically labelled lattice paths to parking functions

Vertically labelled lattice paths

1

−5

−4 2 3 6

0 1 2 3 4 Type C parking functions

There is a natural bijection between typeC parking functions and vertically labelled lattice paths.

f = (

0

,

4

,

4

,

−4

,

−4

,

4

)

(102)

Parking functions

### From vertically labelled lattice paths to parking functions

Vertically labelled lattice paths

1

−5

−4 2 3 6

0 1 2 3 4 5 Type C parking functions

There is a natural bijection between typeC parking functions and vertically labelled lattice paths.

f = (

0

,

4

,

4

,

−4

,

−4

,

4

)

(103)

Parking functions

### From vertically labelled lattice paths to parking functions

Vertically labelled lattice paths

1

−5

−4 2 3 6

0 1 2 3 4 5 6 Type C parking functions There is a natural bijection between typeC parking functions and vertically labelled lattice paths.

f = (

0

,

4

,

4

,

−4

,

−4

,

4

)

(104)

Parking functions

### From vertically labelled lattice paths to parking functions

Vertically labelled lattice paths

1

−5

−4 2 3 6

0 1 2 3 4 5 6 Type C parking functions There is a natural bijection between typeC parking functions and vertically labelled lattice paths.

f = (0,

4

,

4

,

−4

,

−4

,

4

)

(105)

Parking functions

### From vertically labelled lattice paths to parking functions

Vertically labelled lattice paths

1

−5

−4 2 3 6

0 1 2 3 4 5 6 Type C parking functions There is a natural bijection between typeC parking functions and vertically labelled lattice paths.

f = (0,

4

,

4

,

−4

,−4,

4

)

(106)

Parking functions

### From vertically labelled lattice paths to parking functions

Vertically labelled lattice paths

1

−5

−4 2 3 6

0 1 2 3 4 5 6 Type C parking functions There is a natural bijection between typeC parking functions and vertically labelled lattice paths.

f = (0,

4

,

4

,−4,−4,

4

)

(107)

Parking functions

### From vertically labelled lattice paths to parking functions

Vertically labelled lattice paths

1

−5

−4 2 3 6

0 1 2 3 4 5 6 Type C parking functions There is a natural bijection between typeC parking functions and vertically labelled lattice paths.

f = (0,4,

4

,−4,−4,

4

)

(108)

Parking functions

### From vertically labelled lattice paths to parking functions

Vertically labelled lattice paths

1

−5

−4 2 3 6

0 1 2 3 4 5 6 Type C parking functions There is a natural bijection between typeC parking functions and vertically labelled lattice paths.

f = (0,4,4,−4,−4,

4

)

(109)

Parking functions

### From vertically labelled lattice paths to parking functions

Vertically labelled lattice paths

1

−5

−4 2 3 6

0 1 2 3 4 5 6 Type C parking functions There is a natural bijection between typeC parking functions and vertically labelled lattice paths.

f = (0,4,4,−4,−4,4)

(110)

Shi regions

### The Shi arrangement

Definition

We define the Shi arrangement of the root system Φ as

ShiΦ ={Hα,k :α∈Φ+,k = 0,1}.

The connected components of

V − [

H∈ShiΦ

H

are called the regions of the Shi arrangement.

Example: ShiC2

In typeC2 we have

Φ+={2e1,2e2,e2+e1,e2−e1}.

(111)

Shi regions

### The Shi arrangement

Definition

We define theShi arrangementof the root system Φ as

ShiΦ ={Hα,k :α∈Φ+,k = 0,1}.

The connected components of

V − [

H∈ShiΦ

H

are called the regions of the Shi arrangement.

Example: ShiC2

In typeC2 we have

Φ+={2e1,2e2,e2+e1,e2−e1}.

(112)

Shi regions

### The Shi arrangement

Definition

We define the Shi arrangement of the root system Φ as

ShiΦ ={Hα,k :α∈Φ+,k = 0,1}.

The connected components of

V − [

H∈ShiΦ

H

are called the regions of the Shi arrangement.

Example: ShiC2

In typeC2 we have

Φ+={2e ,2e ,e +e ,e −e }.

(113)

Shi regions

### The Shi arrangement

Definition

We define the Shi arrangement of the root system Φ as

ShiΦ ={Hα,k :α∈Φ+,k = 0,1}.

The connected components of

V − [

H∈ShiΦ

H

are called the regions of the Shi arrangement.

Example: ShiC2

In typeC2 we have

Φ+={2e1,2e2,e2+e1,e2−e1}.

(114)

Shi regions

### The Shi arrangement

Definition

We define the Shi arrangement of the root system Φ as

ShiΦ ={Hα,k :α∈Φ+,k = 0,1}.

The connected components of

V − [

H∈ShiΦ

H

are called the regions of the Shi arrangement.

Example: ShiC2

In typeC2 we have

Φ+={2e ,2e ,e +e ,e −e }.

(115)

Shi regions

### The Shi arrangement

Definition

We define the Shi arrangement of the root system Φ as

ShiΦ ={Hα,k :α∈Φ+,k = 0,1}.

The connected components of

V − [

H∈ShiΦ

H

are called the regions of the Shi arrangement.

Example: ShiC2

In typeC2 we have

Φ+={2e1,2e2,e2+e1,e2−e1}.

(116)

Shi regions

### The Shi arrangement

Definition

We define the Shi arrangement of the root system Φ as

ShiΦ ={Hα,k :α∈Φ+,k = 0,1}.

The connected components of

V − [

H∈ShiΦ

H

are called the regions of the Shi arrangement.

Example: ShiC2

In typeC2 we have

Φ+={2e ,2e ,e +e ,e −e }.

(117)

Shi regions

### The Shi arrangement

Definition

We define the Shi arrangement of the root system Φ as

ShiΦ ={Hα,k :α∈Φ+,k = 0,1}.

The connected components of

V − [

H∈ShiΦ

H

are called the regions of the Shi arrangement.

Example: ShiC2

In typeC2 we have

Φ+={2e1,2e2,e2+e1,e2−e1}.

(118)

Shi regions

### The Shi arrangement

Definition

We define the Shi arrangement of the root system Φ as

ShiΦ ={Hα,k :α∈Φ+,k = 0,1}.

The connected components of

V − [

H∈ShiΦ

H

are called the regions of the Shi arrangement.

Example: ShiC2

In typeC2 we have

Φ+={2e ,2e ,e +e ,e −e }.

Those of us in the social sciences in general, and the human spatial sciences in specific, who choose to use nonlinear dynamics in modeling and interpreting socio-spatial events in

Projection of Diﬀerential Algebras and Elimination As was indicated in 5.23, Proposition 5.22 ensures that if we know how to resolve simple basic objects, then a sequence of

Polarity, Girard’s test from Linear Logic Hypersequent calculus from Fuzzy Logic DM completion from Substructural Logic. to establish uniform cut-elimination for extensions of

Keywords: continuous time random walk, Brownian motion, collision time, skew Young tableaux, tandem queue.. AMS 2000 Subject Classification: Primary:

I The bijection sending the area to the sum of the major and the inverse major index can be generalized to types B and C but fails to exist in type D... Non-crossing and non-nesting

This paper presents an investigation into the mechanics of this specific problem and develops an analytical approach that accounts for the eﬀects of geometrical and material data on

While conducting an experiment regarding fetal move- ments as a result of Pulsed Wave Doppler (PWD) ultrasound, [8] we encountered the severe artifacts in the acquired image2.

Wro ´nski’s construction replaced by phase semantic completion. ASubL3, Crakow 06/11/06