Product Formulas Product Formulas

1

New Product Formulas New Product Formulas

for Tableaux for Tableaux

Ron Adin (Bar-Ilan U)

Ronald King (U Southampton) Yuval Roichman (Bar-Ilan U)

2

Product Formulas Product Formulas

Product formulas for the number of standard Product formulas for the number of standard

Young tableaux were known for two families of Young tableaux were known for two families of

shapes

shapes –– regular and shifted.regular and shifted.

We present an unexpected addition to this list, We present an unexpected addition to this list,

consisting of certain

consisting of certain truncated truncated shapes.shapes.

3

Background

Background

4

Regular Shapes Regular Shapes

diagram standard Young tableau diagram standard Young tableau

(SYT) (SYT)

(5, 4, 2)

| | 5 4 2 11

λ λ

=

= + + =

4 6 3 5 8 11

9

10 7

1 2

5

Regular Shapes Regular Shapes

Theorem:

Theorem: [Frobenius[Frobenius--Young]Young]

The number of SYT of shape The number of SYT of shape

is is

There is an equivalent hook formula [FRT].

There is an equivalent hook formula [FRT].

( ,1 , _m )

λ = λ … λ

(λ1 ≥… ≥ λ_m ≥ 0)

(| |)!

( )

( _i )! _{i j} ^{i j}

i

f i j

m i

λ λ

λ _< λ λ

= ⋅ − − +

+ −

∏

∏

6

Regular Shapes Regular Shapes

Example:

Example: For a For a rectangularrectangular shapeshape ( parts),

( parts),

where where

(n^m ) ( ,n , )n

λ = = … m

( )

( )!

nm m n

m n

f mn F F

F ₊

= ⋅

1

0

!

m m

i

F i

−

=

=

∏

7

Shifted Shapes Shifted Shapes

shifted diagram standard Young tableau shifted diagram standard Young tableau

((SYT)SYT)

(5, 4, 2)

| | 5 4 2 11

λ λ

=

= + + =

4 6

3 5 8 11 9

10 7

1 2

8

Shifted Shapes Shifted Shapes

Theorem:

Theorem: [Schur][Schur]

The number of SYT of shifted shape The number of SYT of shifted shape

is is

There is an equivalent hook formula.

There is an equivalent hook formula.

( ,1 , _m)

λ = λ … λ

(λ1 >… > λ_m > 0)

(| |)!

!

i j

i i j i j

i

g^λ λ λ λ

λ _< λ λ

= ⋅ −

∏

∏

9

Shifted Shapes Shifted Shapes

Example:

Example: For a For a shifted staircaseshifted staircase shapeshape ,,

where where

[ ] : ( ,m m m 1, ,1)

λ = = − …

1 [ ]

0

! !

(2 1)!

m m

i

g M i

i

−

=

= ⋅

∏

| [ ] | 1 . 2

M m  m + 

= =  

 

10

Main Results

Main Results

11

Truncation Truncation

Delete one or more cells from the NE (top right) Delete one or more cells from the NE (top right)

corner of a regular or shifted shape.

corner of a regular or shifted shape.

12

Truncation Truncation

Delete one or more cells from the NE (top right) Delete one or more cells from the NE (top right)

corner of a regular or shifted shape.

corner of a regular or shifted shape.

13

Truncated Shapes Truncated Shapes

with Product Formulas with Product Formulas

•• Rectangle minus a squareRectangle minus a square

•• Rectangle minus a square, plus outer cornerRectangle minus a square, plus outer corner

•• Shifted staircase minus a squareShifted staircase minus a square

•• Shifted staircase ninus a square, plus outer cornerShifted staircase ninus a square, plus outer corner

14

Truncated Shapes Truncated Shapes

with Product Formulas with Product Formulas

•• Rectangle minus a squareRectangle minus a square

•• Rectangle minus a square, plus outer cornerRectangle minus a square, plus outer corner

•• Shifted staircase minus a squareShifted staircase minus a square

•• Shifted staircase ninus a square, plus outer cornerShifted staircase ninus a square, plus outer corner

15

Truncated Shapes Truncated Shapes

with Product Formulas with Product Formulas

•• Rectangle minus a squareRectangle minus a square

•• Rectangle minus a square, plus outer cornerRectangle minus a square, plus outer corner

•• Shifted staircase minus a squareShifted staircase minus a square

•• Shifted staircase ninus a square, plus outer cornerShifted staircase ninus a square, plus outer corner

16

Truncated Shapes Truncated Shapes

with Product Formulas with Product Formulas

•• Rectangle minus a squareRectangle minus a square

•• Rectangle minus a square, plus outer cornerRectangle minus a square, plus outer corner

•• Shifted staircase minus a squareShifted staircase minus a square

•• Shifted staircase ninus a square, plus outer cornerShifted staircase ninus a square, plus outer corner

17

Truncated Shapes Truncated Shapes

with Product Formulas with Product Formulas

•• Rectangle minus a squareRectangle minus a square

•• Rectangle minus a square, plus outer cornerRectangle minus a square, plus outer corner

•• Shifted staircase minus a squareShifted staircase minus a square

•• Shifted staircase ninus a square, plus outer cornerShifted staircase ninus a square, plus outer corner

18

Sample Formulas Sample Formulas

•• Rectangle minus one cell:Rectangle minus one cell:

where is the size of the shape.

where is the size of the shape.

(n^m ) \ (1)

λ =

2 2

2

2 (2 3)!(2 3)!

! (2 2 5)!( 2)

m n

m n

F F

m n

f N

m n m n F

λ _{− −}

+ −

⋅ − −

= ⋅ ⋅

+ − + −

N = mn −1

19

Sample Formulas Sample Formulas

•• Rectangle minus 2x2 square plus outer corner:Rectangle minus 2x2 square plus outer corner:

where is the size of the shape.

where is the size of the shape.

(n^m ) \ (2,1)

λ =

2 2

2

(2 4)!(2 4)!

! (2 2 7)!

m n

m n

F F

m n

f N

m n F

λ _{− −}

+ −

− −

= ⋅ ⋅

+ −

N = mn − 3

20

Sample Formulas Sample Formulas

•• Shifted staircase minus one cell:Shifted staircase minus one cell:

where is the size of the shape.

where is the size of the shape.

[ ] \ (1)m

λ =

5

0

4(2 5) !

! (4 7)!( 1) (2 1)!

m

i

m i

g N

m m i

λ ⁻

=

= ⋅ − ⋅

− −

∏

1 1

2

N  m + 

=   −

 

21

Sample Formulas Sample Formulas

•• Shifted staircase minus 2x2 square, plus outer Shifted staircase minus 2x2 square, plus outer corner:

corner:

where is the size of the shape.

where is the size of the shape.

[ ] \ (2,1)m

λ =

5

0

2 !

! (4 9)!( 2) (2 1)!

m

i

g N i

m m i

λ ⁻

=

= ⋅ ⋅

− −

∏

1 3

2

N  m + 

=   −

 

22

Ideas of Proof

Ideas of Proof

23

Main Idea: Pivoting

Main Idea: Pivoting

24

Main Idea: Pivoting Main Idea: Pivoting

Choose a

Choose a pivot cellpivot cell P P (on the NE boundary)(on the NE boundary)

P

25

Main Idea: Pivoting Main Idea: Pivoting

Choose a

Choose a pivot cellpivot cell P P (on the NE boundary)(on the NE boundary) In an SYT, this cell contains some value . In an SYT, this cell contains some value .

P

k

26

Main Idea: Pivoting Main Idea: Pivoting

Choose a

Choose a pivot cellpivot cell P P (on the NE boundary)(on the NE boundary) In an SYT, this cell contains some value . In an SYT, this cell contains some value .

Where are the values ? ? Where are the values ? ?

P

k

< k > k

27

Main Idea: Pivoting Main Idea: Pivoting

Choose a

Choose a pivot cellpivot cell P P (on the NE boundary)(on the NE boundary) In an SYT, this cell contains some value . In an SYT, this cell contains some value .

Where are the values ? ? Where are the values ? ?

P

k

< k > k

< k

> k

?

28

Main Idea: Pivoting Main Idea: Pivoting

Choose a

Choose a pivot cellpivot cell P P (on the NE boundary)(on the NE boundary) In an SYT, this cell contains some value . In an SYT, this cell contains some value .

Where are the values ? ? Where are the values ? ?

P

k

< k > k

< k

> k

29

Main Idea: Pivoting Main Idea: Pivoting

skew shape skew shape

µ P

θ µ _'

λ

ν '

[ ]

( ' [ ] / , )

c c

m

g^θ g^{µ λ} g^{µ λ} m

λ

ν λ ν λ

∪ ∪

⊆

=

∑

30

Main Idea: Pivoting Main Idea: Pivoting

skew shape set complement skew shape set complement

µ P

θ µ _'

λ

ν '

[ ]

( ' [ ] / , )

c c

m

g^θ g^{µ λ} g^{µ λ} m

λ

ν λ ν λ

∪ ∪

⊆

=

∑

(3, 2) (4,1)

λ ν

=

=

31

Complementary Ideas Complementary Ideas

[ ]

c

m

g^θ g^{µ λ} g^{µ λ}

λ

∪ ∪

⊆

=

∑

[ ]

[ ]

| |

( )

m c

m t

g g g^{λ λ} t

λλ^⊆=

=

∑

( ,| |,| |)

c c

g^{µ λ∪} g^{µ λ∪} = c µ λ λc ⋅ g g^{λ λ}

32

Further Comments

Further Comments

33

Motivation: Triangle

Motivation: Triangle - - Free Free Triangulations

Triangulations

Definition:Definition: A A triangulationtriangulation of a convex polygon of a convex polygon is is triangletriangle--free (TFT) free (TFT) if it contains no “if it contains no “internalinternal””

triangle, i.e., a triangle whose 3 sides are

triangle, i.e., a triangle whose 3 sides are diagonals diagonals of the polygon. The set of all TFT

of the polygon. The set of all TFT’’s of an s of an --gon gon is denoted

is denoted

TFT non-TFT

n TFT n( ).

34

Motivation: Colored TFT Motivation: Colored TFT

Note:Note: A triangulation is triangleA triangulation is triangle--free iff the dual free iff the dual tree is a

tree is a pathpath..

The triangles of a TFT can be linearly ordered The triangles of a TFT can be linearly ordered (colored) in two

(colored) in two ““directions”directions”. Denote by . Denote by the set of

the set of coloredcolored TFTTFT’’s.s.

CTFT n( )

35

Motivation: Flip Graph Motivation: Flip Graph

FlipFlip = replacing a diagonal by the other diagonal of the = replacing a diagonal by the other diagonal of the same quadrangle.

same quadrangle.

The The colored flip graphcolored flip graph has vertex sethas vertex set with edges corresponding to flips.

with edges corresponding to flips.

Γn CTFT n( )

36

Motivation: Truncated Shifted Motivation: Truncated Shifted

Tableaux Tableaux

The standard Young tableaux of truncated The standard Young tableaux of truncated shifted staircase shape : shifted staircase shape :

1 2 3 1 2 4 1 2 3 1 2 4

4 5 6 3 5 6 4 5 7 3 5 7

7 8 7 8 6 8 6 8

9 9 9 9

[4] \ (1) = (3, 3, 2,1)

37

Motivation: Geodesics and Tableaux Motivation: Geodesics and Tableaux

Theorem:Theorem: [Adin[Adin--Roichman] Roichman]

The number of geodesics in

The number of geodesics in from a star from a star TFT to its reverse is twice

TFT to its reverse is twice the number of the number of

standard Young tableaux of truncated shifted standard Young tableaux of truncated shifted

shape shape ..

1 2 4 3 5 6

7 8 9 1

2 3 4

3 4 5 6

13 14 24 15 25 … 36 46 sequence of flipped diagonals

(n − 3, n − 3, n − 4,…,1) = [n − 2] \ (1) Γn

38

Motivation: Numerical Evidence Motivation: Numerical Evidence

•• Shifted staircase minus one cell: Shifted staircase minus one cell:

Largest prime factor is !!!

Largest prime factor is !!!

6 2 2 2

= 116528733315142075200

= 2 3 5 7 13 17 19 23 37 41 43 47 53 f ^λ

⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅

[10] \ (1) 54

λ λ

=

=

λ

≤

39

Parallel Results Parallel Results

Greta Panova (Harvard U) has used quite Greta Panova (Harvard U) has used quite

different methods (including: bijections, Schur different methods (including: bijections, Schur

functions, polytope volume computation and functions, polytope volume computation and

contour integration) to prove product formulas contour integration) to prove product formulas

in the following cases:

in the following cases:

•• Rectangle minus a staircaseRectangle minus a staircase

•• Rectangle minus a square, plus outer cornerRectangle minus a square, plus outer corner

•• Shifted staircase minus one cellShifted staircase minus one cell

40

Parallel Results Parallel Results

AKR P

motivating problem

41

Open Problems Open Problems

•• Conjecture:Conjecture: For a For a squaresquare minus two cells:minus two cells:

•• Other shapes? Characterization?Other shapes? Characterization?

2 2

2 2

2

2 4

6 (3 4)!

( 2)!

(6 8)!(2 2)!( 2)!

n n

F f n n

n n n F

λ ₋

−

⋅ −

= − ⋅ ⋅

− − −

(nⁿ ) \ (2)

λ =

42

Grazie Grazie per l

per l ’ ’ attenzione! attenzione!