Domino tilings of Aztec rectangle with connected holes

(1)

onne ted holes

MasaoIshikawa y

y

UniversityoftheRyukyus

Combinator ialRepresentationTheoryandRelatedTopi s

O tober21,2015

RIMS,KyotoUniversity

(2)

Abstra t

ItisfamousthatthenumberofdominotilingsofanAzte diamond

is2ton

+

1 hoose2.Westudythenumberofdominotilingsof

anAzte re tanglewithevennumberof onne tedholesinaline

andweobtainaformulawhi hexpressthenumberofsu hdomino

tilingsbyaprodu tofasimilarpowerof2,linearfa torsanda

polynomialofthe oordinatesoftheholesinaline. Wewillnda

formulawhi hexpressesthispolynomialasadeterminantof

terminatingGausshypergeometr i ser iesandshowthatthis

polynomialpossessesinterestingproperties. Firstweusethe

Lindstrom-Gessel-Viennot¨ theoremtoenumeratethedomino

tilingsofanAzte re tanglewith onne tedholesandobtaina

determinantwhoseentr iesaregeneralizedlargeS hroder¨

(3)

Abstra t

Thenwe onsideramoregeneraldeterminantwhoseentr iesare

themomentsoftheLaurentbiorthogonalpolynomials,whi h

enableustoapplytheDesnanot-Ja obiadjointmatr ixtheorem.

Thisgeneraldeterminantredu estothe aseq

=

t

=

1in

Kamioka'sresultifwehavenohole,i.e.,theAzte diamond ase.

Thentheevaluationofthedeterminantredu estoaquadrati

relationoftheabovepolynomials. Thisproje tisstillawor kin

progressandwebelievethatwearevery losetothe omplete

proof. Thisisajointwor kwithFumihikoNakano,TaizoSadahiro

(4)

Planofmytalk

1

LargeS hroder¨ numbers

2

Laurentbiorthogonalpolynomials

3

Azte diamondtheorem

4

Azte Re tanglewith onne tedholesinline

5

Howto ountthetilings?

6

Introdu inganewparameter

7

Strategyforproof

8

(5)

Planofmytalk

1

2

3

Azte diamondtheorem

4

5

6

7

Strategyforproof

8

(6)

Planofmytalk

1

2

3

Azte diamondtheorem

4

5

6

7

Strategyforproof

8

(7)

Planofmytalk

1

2

3

Azte diamondtheorem

4

5

6

7

Strategyforproof

8

(8)

Planofmytalk

1

2

3

Azte diamondtheorem

4

5

6

7

Strategyforproof

8

(9)

Planofmytalk

1

2

3

Azte diamondtheorem

4

5

6

7

Strategyforproof

8

(10)

Planofmytalk

1

2

3

Azte diamondtheorem

4

5

6

7

Strategyforproof

8

(11)

Planofmytalk

1

2

3

Azte diamondtheorem

4

5

6

7

Strategyforproof

8

(12)

Planofmytalk

1

2

3

Azte diamondtheorem

4

5

6

7

Strategyforproof

8

(13)

Inthistalk

1

[EF℄S.P.EuandT.S.Fu,ASimpleProofoftheAzte DiamondTheorem,Ele tron.J.Combin. 12(2005),Resear h Paper18,8pp.(ele troni ).

2

[EKLP℄N.Elkies,G.Kuperberg,M.Larsen,andJ.Propp,

Alternating-signmatr i esanddominotilings(PartI,II),J.

Algebrai Combinator i s1(1992),111132,219234.

3

[GV℄I.M.GesselandX.G.Viennot,Determinants,Paths,

andPlanePartitions,1989prepr int.

4

[Ka℄S.Kamioka,Laurentbiorthogonalpolynomials,

q-NarayanapolynomialsanddominotilingsoftheAzte

(14)

Inthistalk

1

[EF℄S.P.EuandT.S.Fu,ASimpleProofoftheAzte

DiamondTheorem,Ele tron.J.Combin. 12(2005),Resear h

Paper18,8pp.(ele troni ).

2

[EKLP℄N.Elkies,G.Kuperberg,M.Larsen,andJ.Propp, Alternating-signmatr i esanddominotilings(PartI,II),J. Algebrai Combinator i s1(1992),111132,219234.

3

4

(15)

Inthistalk

1

2

3

[GV℄I.M.GesselandX.G.Viennot,Determinants,Paths, andPlanePartitions,1989prepr int.

4

(16)

Inthistalk

1

2

3

4

[Ka℄S.Kamioka,Laurentbiorthogonalpolynomials, q-NarayanapolynomialsanddominotilingsoftheAzte diamonds,J.Combin. TheorySer. A123(2014),1429.

(17)

(18)

The large S hroder¨ number S

(

n

)

Denition

AS hroder¨ pathisapathintheplane,startingfromtheor igin

(

0;0

)

and endingat

(

2n;0

)

nevergoingbelowthex-axis,usingthesteps

U

= (

1;1

)

up; D

= (

1; 1

)

down; L

= (

2;0

)

level.

ThelargeS hroder¨ number,denotedbyS

(

n

)

,isthenumberofsu h paths.

✲

✻

✒

❘

✒

✲

✒

❘

0 1 2 3 4 5 6 7 8 1 2 UDULUDD S

(

4

) =

90

(19)

Example

Ifn

=

2,thentheS hroder¨ pathsarethefollowings. hen ewe

obtainS

(

2

) =

6.

✲

✻

✒❘✒❘

UDUD

✲

✻

✒

✲

❘

ULD

✲

✻

✒

✒❘

❘

UUDD

✲

✻

✲ ✲

LL

✲

✻

✲✒❘

LUD

✲

✻

✒❘ ✲

UDL

Similar lyoneeasilygets

S

(

0

) =

1; S

(

1

) =

2; S

(

2

) =

6; S

(

3

) =

22

(20)

S

m

(

n

)

Denition

Moregenerally,we onsiderapathstartingfromtheor igin

(

0;0

)

andendingat

(

2n

+

m;m

)

nevergoingbelowthex-axis,usingthe

stepsU,DandL.

✲

✻

✒

✲

✒

❘

✲

0 1 2 3 4 5 6 7 8 1 2 ULUUDL S 2

(

3

) =

146 LetS m

(

n

)

denotethenumberofsu hpaths. Espe ially, S

(

n

) =

S0(n

)

.

(21)

Example ofS

m

(

n

)

Example

Ifm

=

2andn

=

1,thensu hpathsarethefollowings. hen ewe

obtainS 2

(

1

) =

6.

✲

✻

✒

✒❘✒

UUDU

✲

✻

✒

✲

UUH

✲

✻

✒

✒❘

UUDD

✲

✻

✲✒

✒

HUU

✲

✻

✒❘✒

✒

UDUU

✲

✻

✒

✲✒

UHU

Similar lyoneeasilygets

S2(0

) =

1; S2(1

) =

6; S2(2

) =

30

(22)

TheGausshypergeometr i fun tionisdenedbythepowerser ies Denition 2 F 1 a;b

;

x !

=

1 X n

=

0

(

a

)n

(

b

)n

n

!(

)n

x n ;

where

(

a

)n

=

a

(

a

+

1

)

(

a

+

n 1

)

is alledther isingfa tor ial

orPo hhammersymbol.Ifaorbisanegativeinteger,then

2 F

1

(

a;b

;

x

)

is alledterminating.

Proposition

Ifm;n0areintegers,thenS

m

(

n

)

hasthatfollowingexpression bytheGausshypergeometr i ser ies:

S m

(

n

) =

8 > > > > < > > > > : 1 ifn

=

0, 2 n

+

m ! 2 F 1 n

+

1;m

+

n

+

2

;

+

;

1 ! ifn1.

(23)

TheGausshypergeometr i fun tionisdenedbythepowerser ies Denition 2 F 1 a;b

;

x !

=

1 X n

=

0

(

a

)n

(

b

)n

n

!(

)n

x n ;

where

(

a

)n

=

a

(

a

+

1

)

(

a

+

n 1

)

is alledther isingfa tor ial

orPo hhammersymbol.Ifaorbisanegativeinteger,then

2 F

1

(

a;b

;

x

)

is alledterminating.

Proposition

Ifm;n0areintegers,thenSm(n

)

hasthatfollowingexpression

bytheGausshypergeometr i ser ies:

Sm(n

) =

8 > > > > < > > > > : 1 ifn

=

0, 2 n

+

m ! 2 F 1 n

+

1;m

+

n

+

2

;

+

;

1 ! ifn1.

(24)

Proof.Thekeyideais Sm(n

) =

S m

+

1( n 1

) +

Sm(n 1

) +

S m 1( n

)

ifm>0.

✒

❘

✲

S m

(

n

)

S m 1

(

n

)

S m

+

1

(

n 1

)

S m

(

n 1

)

Corollary

Ifn0areintegers,then

S

(

n

) =

8 > > > > < > > > > : 1 ifn

=

0, 2 2 F 1 n

+

1;2

;

2

;

1 ! ifn1.

(25)

(26)

The Laurent biorthogonal polynomials P

n

(

z

)

Denition(TheLaurentbiorthogonalpolynomials)

The(moni )Laurentbiorthogonalpolynomials(LBPs)P n

(

z

)

,n2N,are thepolynomialsdeterminedfromthethreetermrelation

P n

+

1

(

z

) = (

z 1

)

P n

(

z

)

zP n 1

(

z

)

(

n1

)

withP 1

(

z

) =

0andP 0

(

z

) =

1.(KamiokadenedtheLBPswith parametersfb

n gandf

n

g,butherewerestr i tourattentiontothe ase

whereweneed.)

Example

Therstfewtermsareasfollows:

P 1

(

z

) =

z 1 P 2

(

z

) =

z 2 3z

+

1 P 3

(

z

) =

z 3 5z 2

+

5z 1

(27)

n

(

z

)

Denition(TheLaurentbiorthogonalpolynomials)

The(moni )Laurentbiorthogonalpolynomials(LBPs)P n

(

z

)

,n2N,are thepolynomialsdeterminedfromthethreetermrelation

P n

+

1

(

z

) = (

z 1

)

P n

(

z

)

zP n 1

(

z

)

(

n1

)

withP 1

(

z

) =

0andP 0

(

z

) =

1.(KamiokadenedtheLBPswith parametersfb

n gandf

n

g,butherewerestr i tourattentiontothe ase

whereweneed.)

Example

Therstfewtermsareasfollows:

P1(z

) =

z 1 P2(z

) =

z 2 3z

+

1 P 3

(

z

) =

z 3 5z 2

+

5z 1

(28)

Linear fun tional

F

and Moments f

(

n

)

Theorem(FavardtypetheoremforLBPs[Ka℄)

Thereexistsalinearfun tional

F

denedoverLaurent polynomialsinzwithrespe ttowhi htheLBPsP

n

(

z

)

satisfythe orthogonality

F

_[

Pn(z

)

z k

] =

h n Æ n;k ; 0k n

withsome onstantsh

n

,0,whereÆ

n;k

denotestheKrone ker

delta. Thelinearfun tional

F

isuniqueuptoa onstantfa tor.

Hen eweassume

F

[

1

] =

1hereafter.

Denition(moments)

Wewr itethemomentsofthelinearfun tional

F

,

f

(

n

)

= F [

z n

(29)

Linear fun tional

F

and Moments f

(

n

)

Theorem(FavardtypetheoremforLBPs[Ka℄)

Thereexistsalinearfun tional

F

denedoverLaurent polynomialsinzwithrespe ttowhi htheLBPsP

n

(

z

)

satisfythe orthogonality

F

_[

Pn(z

)

z k

] =

h n Æ n;k ; 0k n

withsome onstantsh

n

,0,whereÆ

n;k

denotestheKrone ker

delta. Thelinearfun tional

F

isuniqueuptoa onstantfa tor.

Hen eweassume

F

[

1

] =

1hereafter.

Denition(moments)

Wewr itethemomentsofthelinearfun tional

F,

f

(

n

)

= F [

z n

(30)

Example ofthe momentsf

(

n

)

Example

Forexample,wehave

P1(z

) =

z 1)f

(

1

)

=

f

(

0

) =

1; P2(z

) =

z 2 3z

+

1)f

(

2

)

=

3f

(

1

)

f

(

0

) =

2; P3(z

) =

z 3 5z 2

+

5z 1)f

(

3

)

=

5f

(

2

)

5f

(

1

) +

f

(

0

) =

6: Similar lyweobtain P 2

(

z

) =

z 2 3z

+

1)f

(

1

)

=

3f

(

0

)

f

(

1

)

=

2; P3(z

) =

z 3 5z 2

+

5z 1 )f

(

2

)

=

5f

(

2

) +

5f

(

1

)

f

(

0

)

=

6:

(31)

n

(

z

)

Denition

Form2Nandn2Zwedenefm(n

)

by

f m

(

n

)

= F [

Pm(z

)

z n

]

: Example

A tually,we an omputef

m

(

n

)

by f m

(

n

) =

m X k

=

0

[

z k

]

P m

(

z

)

f

(

k

+

n

)

where

[

z k

]

P m

(

z

)

standsforthe oef ientofz k inP m

(

z

)

. f 1

(

3

) =

16; f 1

(

2

) =

4; f 1

(

1

) =

1; f 1

(

0

) =

0; f 1

(

1

) =

1; f 1

(

2

) =

4; f 1

(

4

) =

16;:::

(32)

n

(

z

)

Denition

Form2Nandn2Zwedenefm(n

)

by

f m

(

n

)

= F [

Pm(z

)

z n

]

: Example

A tually,we an omputefm(n

)

by

fm(n

) =

m X k

=

0

[

z k

]

Pm(z

)

f

(

k

+

n

)

where

[

z k

]

Pm(z

)

standsforthe oef ientofz k inPm(z

)

. f 1

(

3

) =

16; f 1

(

2

) =

4; f 1

(

1

) =

1; f 1

(

0

) =

0; f 1

(

1

) =

1; f 1

(

2

) =

4; f 1

(

4

) =

16;:::

(33)

Proposition

Form2Nandn2Zweobtain

fm(n

) =

8 > > < > > : S m

(

n 1

)

(n1),

(

1

)

m Sm( m n

)

(n0).

(34)

(35)

n

Denition

Forn2N,theAzte diamondAD n

ofordernistheunionofallunit

squareswhi hlieinsidethe losedregionjxj

+

jyjn

+

1.

Example

AD

(36)

n

Denition

+

jyjn

+

1.

Example

AD

(37)

n

Denition

+

jyjn

+

1.

Example

AD

(38)

Denition

Adominodenotesaone-by-twoortwo-by-onere tangle.

Example

12

(39)

Denition

Adominodenotesaone-by-twoortwo-by-onere tangle.

Example

12

(40)

Denition

Adominotiling,orsimplyatiling,ofAD n

isa olle tionof

non-over lappingdominoeswhi hexa tly oversAD

n .

Example

AtilingofAD

(41)

Denition

isa olle tionof

n .

Example

AtilingofAD

(42)

Denition

isa olle tionof

n .

Example

AtilingofAD

(43)

Denition

isa olle tionof

n .

Example

AtilingofAD

(44)

Denition

isa olle tionof

n .

Example

AtilingofAD

(45)

Theorem(Azte diamondtheorem)

Forn2N,LetT

n

denotethesetofalltilingsofAD

n . Then ℄T n

=

2 n

(

n

+

1

)

2

Manyproofsareknown,e.g.,Elkies-Kuperberg-Larsen-Propp

(1992),Ciu u(1996),Br ualdi-Kir kland(2003),Kuo(2004),Eu-Fu

(46)

(47)

Azte re tangle AR

a;b

Denition

Fora;b 2N,theAzte re tangleAR a;b

istheunionofallunitsquares

whi hlieinsidethe losedregion

b 2a 1x

+

y b

+

1; b 1y xb

+

1:

(Hereafterweassumeab.)LetS x;y

denotethesquarewiththevertex

(

x;y

)

,

(

x

+

1;y

)

,

(

x

+

1;y

+

1

)

and

(

x;y

+

1

)

.We allS x;y

white(resp.

bla k)ifx

+

y

+

biseven(resp.odd).

Example 6;8

(

x;y

)

(

x

+

1;y

)

(

x;y

+

1

)

(

x

+

1;y

+

1

)

S x;y

(48)

Azte re tangle AR

a;b

Denition

Fora;b 2N,theAzte re tangleAR a;b

istheunionofallunitsquares

whi hlieinsidethe losedregion

b 2a 1x

+

y b

+

1; b 1y xb

+

1:

(Hereafterweassumeab.)LetS x;y

denotethesquarewiththevertex

(

x;y

)

,

(

x

+

1;y

)

,

(

x

+

1;y

+

1

)

and

(

x;y

+

1

)

.We allS x;y

white(resp.

bla k)ifx

+

y

+

biseven(resp.odd).

Example 6;8

(

x;y

)

(

x

+

1;y

)

(

x;y

+

1

)

(

x

+

1;y

+

1

)

S x;y

(49)

Example

TheAzte re tangleAR

a;b

has

(

a

+

1

)

b bla ksquaresanda

(

b

+

1

)

whitesquares,sothatthereareb amorebla ksquaresthanwhite

ones.Meanwhile,ea hdominoo upies1bla ksquareand1white

square.

AR

(50)

Example

TheAzte re tangleAR

a;b

has

(

a

+

1

)

b bla ksquaresanda

(

b

+

1

)

whitesquares,sothatthereareb amorebla ksquaresthanwhite

ones.Meanwhile,ea hdominoo upies1bla ksquareand1white

square.

AR

(51)

Denition(AR L a;b

(

;

)

andAR S a;b

(

;

)

Weremover

=

b a onne tedbla ksquaresinalineparalleltothe

longorshortsideofAR a;b

,whi hwe allholes.Weusethe oordinates

(

;

)

ofthelowestholeoftheser iesofholesinline,wherein reases alongtheshortsideandin reasesalongthelongside.Herewe

assumethe oordinatesofthelowestbla ksquareis

(

0;0

)

.Iftheholes areparalleltothelong(resp.short)side,wewr itetheremainingareaas

AR L a;b

(

;

)

(resp.AR S a;b

(

;

)

).

■

✒

AR 6;8

(

;

) = (

0;0

)

(52)

Example ofAR L a;b

(

;

)

Example

■

✒

AR L 6;8(1;3

)

(53)

Example ofAR L a;b

(

;

)

Example

■

✒

AR L 6;8(2;3

)

(54)

Example ofAR L a;b

(

;

)

Example

■

✒

AR L 6;8(2;4

)

(55)

Example ofAR S a;b

(

;

)

Example

■

✒

AR S 6;8

(

1;3

)

(56)

AnexampleofdominotilingofAR L 6;8

(

2;5

)

AR L 6;8

(

2;5

)

(57)

(

2;5

)

AR L 6;8

(

2;5

)

(58)

(

2;5

)

AR L 6;8

(

2;5

)

(59)

Problem

WhatisthenumberofdominotilingsofAR L a;b

(

;

)

and AR S a;b

(

;

)

? Isitni eorugly? Denition LetT L a;b

(

;

)

(resp. T S a;b

(

;

)

)denotethesetofdominotilingsof AR L a;b

(

;

)

(resp.AR S a;b

(

;

)

),where

(

;

)

ranges 0aand0a

(

resp.0a r

+

1and0a

+

r 1

)

: Herer

=

b a.

(60)

Answer Letr

=

b a 0. Ifr iseven, ℄T L a;b

(

;

) =

2 a

(

a

+

1

)

2

+

r r 1 Y k

=

0 k

!

(

k

+

)!

f

(

r

)

a; a 2

=

2 a

(

a

+

1

)

2

+

r r 1 Y k

=

0 k

!(

k

+

a

)!

(

k

+

)!(

k

+

a

)!

f

(

r

)

a; a 2 wheref

(

r

)

n

(

a;x

)

isapolynomialofdegreernwithrespe ttoxsu h

thatf

(

r

)

n

(

a; x

) =

f

(

r

)

n

(

a;x

)

. Ifr isodd,℄T L a;b

(

;

)

isugly!

(61)

Answer Letr

=

b a0. Ifriseven,then℄T S a;b

(

;

)

equals 2 a(a+1) 2

+

r r(r 1) 2 r 1 Y k

=

0 k

!

(

k

+

r

+

1

)!

g

(

r

)

r

+

1 a; a r

+

1 2 !

=

2 a

(

a

+

1

)

2

+

r

+

r

(

r1

)

2 r 1 Y k

=

0 k

!(

k

+

a r

+

1

)!

(

k

+

r

+

1

)!(

k

+

a

)!

g

(

r

)

a; a

+

r 1 2 ! forr 1a,otherwise℄T S a;b

(

;

)

equals0.Hereg

(

r

)

n

(

a;x

)

isalsoa polynomialofdegreernwithrespe ttoxsu hthat

g

(

r

)

n

(

a; x

) =

g

(

r

)

n

(

a;x

)

. Ifrisodd,℄T S a;b

(

;

)

isuglyagain!

(62)

Example off

(

r

)

n

(

a;x

)

Example f

(

2

)

0

(

a;x

) =

1 f

(

2

)

1

(

a;x

) =

x 2

+

a 1 4 f

(

2

)

2

(

a;x

) =

x 4 x 2

+

3 16

(

a 1

)

2 f

(

2

)

3

(

a;x

) =

x 6 3a

+

5 4 x 4

+

9a 2 24a

+

31 16 x 2

+

9 64

(

a 3

)(

a 1

)

2

(63)

Example ofg

(

r

)

n

(

a;x

)

Example g

(

2

)

0

(

a;x

) =

1 g

(

2

)

1

(

a;x

) =

x 2

+

a 4 g

(

2

)

2

(

a;x

) =

x 4 x 2

+

3 16 a 2 g

(

2

)

3

(

a;x

) =

x 6 3a

+

8 4 x 4

+

1 16

(

9a 2 6a

+

16

)

x 2

+

9 64 a 2

(

a 2

)

(64)

What aref

(

r

)

n

(

a;x

)

and g

(

r

)

n

(

a;x

)

? Denition Letr;n0. Denef

(

r

)

n

(

a;x

)

by f

(

r

)

n

(

a;x

)

=

2 rn r 1 Y k

=

0

(

n

+

k

)!(

a k

)n

k

!

det 0 B B B B B B B B B B B 2 F 1 n j

+

i; a 2 x

;

a j

+

1

;

2

(

n

+

j i

)!

1 C C C C C C C C C C C A 1i;jr :

Hereweusethe onventionthat 1

m

!

=

0ifm<0.Notethatthisis adeterminantofsizer (thenumberofholes).

Deneg

(

r

)

n

(

a;x

)

by g

(

r

)

n

(

a;x

)

=

f

(

r

)

n

(

a r

+

1;x

)

:

(65)

Example off

(

r

)

n

(

a;x

)

Example Ifr

=

1then f

(

1

)

n

(

a;x

) =

(

a

)n

2 n 2 F 1 n; a 2 x

;

a

;

2 ! : skipIfr

=

2then f

(

2

)

n

(

a;x

) =

n

!(

n

+

1

)!(

a

)

n

(

a 1

)

n 2 2n 1 n

!

2 F 1 n ; a 2 x

;

a

;

2 1

(

n

+

1

)!

2 F 1 n 1; a 2 x

;

a 1

;

2 1

(

n 1

)!

2 F 1 n

+

1; a 2 x

;

a

;

2 1 n

!

2 F 1 n ; a 2 x

;

a 1

;

2 :

(66)

(67)

Denition

LetG bealo allynitedire teda y li graph. Considerbase

verti esu

= (

u

1

;:::;un)anddestinationverti esv

= (

v

1

;:::;vn),

andalsoassignaweight!

e

toea hdire tededgee. Forea h

dire tedpathP betweentwoverti es,let!

(

P

)

betheprodu tof

theweightsoftheedgesofthepath.Foranytwoverti esuandv,

wr iteh

(

u;v

)

forthesumh

(

u;v

) =

P

:

u !v

!

(

P

)

overallpathsfrom

utov. Ifoneassignstheweight1toea hedge,thenh

(

u;v

)

ountsthenumberofpathsfromutov.

Theorem(Lindstrom-Gessel-Viennot¨ Lemma)

X 2S n X

(

P 1 ;:::;P n

):

u !v sgn

(

P

))

n Y i

=

1 !

(

P i

) =

det

(

h

(

u i ;v j

))

1i;j;n

(

)

(68)

Denition

LetG bealo allynitedire teda y li graph. Considerbase

verti esu

= (

u

1

;:::;un)anddestinationverti esv

= (

v

1

;:::;vn),

andalsoassignaweight!

e

toea hdire tededgee. Forea h

dire tedpathP betweentwoverti es,let!

(

P

)

betheprodu tof

theweightsoftheedgesofthepath.Foranytwoverti esuandv,

wr iteh

(

u;v

)

forthesumh

(

u;v

) =

P

:

u !v

!

(

P

)

overallpathsfrom

utov. Ifoneassignstheweight1toea hedge,thenh

(

u;v

)

ountsthenumberofpathsfromutov.

Theorem(Lindstrom-Gessel-Viennot¨ Lemma)

X 2S n X

(

P 1 ;:::;P n

):

u !v sgn

(

P

))

n Y i

=

1 !

(

P i

) =

det

(

h

(

u i ;v j

))1i;j;n

(

)

(69)

Dire ted Graph G for AR L

a;b(;

)

Denition

We onsiderthedire tedgraphG

= (

V;E

)

whereV isthesetof

(

x;y

)

su hthatx

+

yiseven,andtheedgesetE is omposedof U,D andL. Weusethe oordinateshx;yi

= (

2x

+

y;y

)

.

Givena;b;and,denetheverti esu i andv j (1i;j b)as follows: u i

=

hb i;0i

(

1i b

)

; v j

=

8 > > < > > : hj

+

b 1;0i (1ja) ha

+

b j;j a 1

+

i (a <jb) :

(70)

Example

AR L 6;8(2;5

)

(71)

Example

AR L 6;8(2;5

)

(72)

Example

✒

❘

✲

!: edges AR L 6;8(2;5

)

(73)

Example

✒

❘

✲

!: edges u 8 u 7 u 6 u 5 u 4 u 3 u 2 u 1 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 u i :startingpoints v j :endingpoints AR L 6;8(2;5

)

(74)

Theorem

Thereisabije tionbetweendominotilingsandnon-interse ting

latti epaths.

Dominoandpath

Therearefourkindsofdominos:

(75)

Theorem

latti epaths.

Dominoandpath

(76)

Theorem

latti epaths.

Dominoandpath

(77)

Theorem

latti epaths.

Dominoandpath

12 21

(78)

Bije tion

AR L 6;8(2;5

)

(79)

Bije tion

AR L 6;8(2;5

)

(80)

Bije tion

AR L 6;8(2;5

)

(81)

Bije tion u 8 u 7 u 6 u 5 u 4 u 3 u 2 u 1 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 AR L 6;8(2;5

)

(82)

Bije tion u 8 u 7 u 6 u 5 u 4 u 3 u 2 u 1 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8

✲

✲ ✲

✲✒

✲

❘

✲✒

✒

✒❘

❘

✲✒

✒

✲

❘

✒

✒❘✒

✒❘

❘

❘✒❘

❘

✒

❘

AR L 6;8(2;5

)

(83)

Theorem

Assumer

=

b aiseveninteger.Then

℄T L a;b

(

;

) =

det

(

e h L i;j

(

a;b;;

))

1i;jb where e h L i;j

(

a;b;;

)

=

8 > > < > > : S

(

i

+

j 1

)

for1j a, S j a 1

+

(

a

+

i j

)

fora

+

1j b ℄T S a;b

(

;

) =

det

(

e h S i;j

(

a;b;;

))

1i;jb where e h S i;j

(

a;b;;

)

=

8 > > < > > : S

(

i

+

j 1

)

for1j a, S j a 1

+

( i 1

)

fora

+

1j b

(84)

Ifa

=

4,b

=

7(r

=

b a

=

3),

=

2and

=

1,then

(

e h L i;j

(

a;b;;

))1i;jb

is 2 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 4 2 6 22 90 0 0 0 6 22 90 394 1 0 0 22 90 394 1806 8 1 0 90 394 1806 8558 48 10 1 394 1806 8558 41586 264 70 12 1806 8558 41586 206098 1408 430 96 8558 41586 206098 1037718 7432 2490 652 3 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 5

(85)

Ifa

=

4,b

=

8(r

=

b a

=

4),

=

2and

=

1,then

(

e h S i;j

(

a;b;;

))1i;jb

is 2 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 4 2 6 22 90 0 0 0 6 22 90 394 1 1 1 22 90 394 1806 8 10 12 90 394 1806 8558 48 70 96 394 1806 8558 41586 264 430 652 1806 8558 41586 206098 1408 2490 4080 8558 41586 206098 1037718 7432 14002 24396 3 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 5

(86)

(87)

TheDesnanot-Ja obiadjointmatr ixtheorem

LetMbeannbynmatr ix.M i

j

ismatr ixMwithrowi and olumnj

removed. detM 1;n 1;n detM

=

detM 1 1 detM n n detM 1 n detM n 1 :

=

Thisformulaisalso alledtheLuisCarroll ondensationformulaor

(88)

Fa t

The ondensationformulaDONOTwor kwith det

(

e h L i;j

(

a;b;;

))

1i;jb nordet

(

e h S i;j

(

a;b;;

))

1i;jb .

But,thelargeS hroder¨ numbersarethemomentsoftheLaurent

biorthogonalpolynomials.Hen eweextendSm(n

)

forn<0as

f m

(

n

) =

S m

(

n 1

)

alwaysholds. Denition

Letmbeanonnegativeinteger.

S m

(

n

) =

8 > > < > > : 0 if m<n<0,

(

1

)

m S m

(

n m 1

)

ifN< m.

(89)

Denition

Leta;b2N(ab)and 2Z.Let's onsiderthebbmatr i es

H L

(

a;b; ;;

)

=

h L i;j

(

a;b; ;;

)

1i;jb and H S

(

a;b; ;;

)

=

h S i;j

(

a;b; ;;

)

1i;jb denedby h L i;j

(

a;b; ;;

)

=

8 > > < > > : S

(

i

+

j

+

1

)

for1ja, S j a 1

+

(

a

+

i j

+

)

fora

+

1jb, and h S i;j

(

a;b; ;;

)

=

8 > > < > > : S

(

i

+

j

+

1

)

for1ja, S j a 1

+

(

i

+

1

)

fora

+

1jb. Notethath L i;j

(

a;b;0;;

) =

e h L i;j

(

a;b;;

)

and h S i;j

(

a;b;0;;

) =

e h S i;j

(

a;b;;

)

.Weintrodu edanewparameter to applyD-Jadjointmatr ixtheorem,but hasno ombinator ialmeaning!.

(90)

Ifa

=

4,b

=

7(r

=

b a

=

3),

=

3,

=

2and

=

1,then

(

e h L i;j

(

a;b;;

))1i;jb

is 2 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 4 2 1 1 2 1 1 1 1 1 2 6 0 0 0 1 2 6 22 0 0 0 2 6 22 90 0 0 0 6 22 90 394 1 0 0 22 90 394 1806 8 1 0 90 394 1806 8558 48 10 1 3 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 5

(91)

Ifa

=

4,b

=

8(r

=

b a

=

4),

=

3,

=

2and

=

1,then

(

e h S i;j

(

a;b;;

))1i;jb

is 2 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 4 2 1 1 2 1 0 0 1 1 2 6 0 0 0 1 2 6 22 0 0 0 2 6 22 90 0 0 0 6 22 90 394 1 1 1 22 90 394 1806 8 10 12 90 394 1806 8558 48 70 96 3 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 5

(92)

Main Result for F L

(

a;b; ;;

)

MainResult(Notyet ompletelyproved)

Leta;b; beintegerssu hthat0aband a 0.Weput

b a

=

r.

(i)If aand0a

+

,thenF L

(

a;b; ;;

)

isequalto

(

1

)

r

(

+

a

)

2

(a+ )(a+ +1)

2

+

r r 1 Y k

=

0 k

!

(

k

+

)!

f

(

r

)

a

+

; a 2

= (

1

)

r

(

+

a

+

)

2

(

a

+

)(

a

+

1

)

2

+

r

(

+

)

r 1 Y k

=

0 k

!(

k

+

a

)!

(

k

+

)!(

k

+

a

+

)!

f

(

r

)

+

a

+

; a

+

2 ;

(93)

Main Result for F S

(

a;b; ;;

)

MainResult(Notyet ompletelyproved)

(ii)If a r

+

1,thenF S

(

a;b; ;;

)

isequalto

(

1

)

r

(

+

a

)

2

(

a

+

)(

a

+

1

)

2

+

r r

(

r1

)

2 r 1 Y k

=

0 k

!

(

k

+

r

+

1

)!

g

(

r

)

r

+

1 a

+

; a r

+

1 2 !

= (

1

)

r

(

+

a

+

)

2

(

a

+

)(

a

+

1

)

2

+

r

(

+

)+

r

(

r1

)

2 r 1 Y k

=

0 k

!(

k

+

a r

+

1

)!

(

k

+

r

+

1

)!(

k

+

a

+

)!

g

(

r

)

+

a

+

; a

+

r 1 2 !

(94)

(95)

Theorem

ByapplyingtheD-Jadjointmatr ixtheorem,weobtainthefollowing

quadrati formula,i.e.,thebothofF L

(

a;b; ;;

)

and F S

(

a;b; ;;

)

satisfy F

(

a;b 1; ;;

)

F

(

a

+

1;b

+

1; 2;

+

1; 1

)

=

F

(

a

+

1;b; 2;

+

1; 1

)

F

(

a;b; ;;

)

F

(

a

+

1;b; 1;

+

1; 1

)

F

(

a;b; 1;;

)

:

(96)

G L 1

(

a;b; ;;

)

and G L 2

(

a;b; ;;

)

Denition

Leta;b; beintegerssu hthat0aband a 0.Weput

b a

=

r. LetG L 1

(

a;b; ;;

)

be

(

1

)

r

(

+

a

)

2

(

a

+

)(

a

+

1

)

2

+

r r 1 Y k

=

0 k

!

(

k

+

)!

f

(

r

)

a

+

; a 2 ; andletG L 2

(

a;b; ;;

)

be

(

1

)

r

(

+

a

+

)

2

(a+ )(a+ +1)

2

+

r

(

+

)

r 1 Y k

=

0 k

!(

k

+

a

)!

(

k

+

)!(

k

+

a

+

)!

f

(

r

)

+

a

+

; a

+

2 ;

(97)

G S 1

(

a;b; ;;

)

and G S 2

(

a;b; ;;

)

Denition LetG S 1

(

a;b; ;;

)

be

(

1

)

r

(

+

a

)

2

(a+ )(a+ +1)

2

+

r r(r 1) 2 r 1 Y k

=

0 k

!

(

k

+

r

+

1

)!

g

(

r

)

r

+

1 a

+

; a r

+

1 2 ! ; andletG S 2

(

a;b; ;;

)

be

(

1

)

r

(

+

a

+

)

2

(

a

+

)(

a

+

1

)

2

+

r

(

+

)+

r

(

r1

)

2 r 1 Y k

=

0 k

!(

k

+

a r

+

1

)!

(

k

+

r

+

1

)!(

k

+

a

+

)!

g

(

r

)

+

a

+

; a

+

r 1 2 ! :

(98)

Denition of f

(

r

)

n

(

a;x

)

and g

(

r

)

n

(

a;x

)

Re allthedenitionoff

(

r

)

n

(

a;x

)

andg

(

r

)

n

(

a;x

)

: Denition Letr;n0. Denef

(

r

)

n

(

a;x

)

by f

(

r

)

n

(

a;x

)

=

2 rn r 1 Y k

=

0

(

n

+

k

)!(

a k

)

n k

!

det 0 B B B B B B B B B B B 2 F 1 n j

+

i; a 2 x

;

a j

+

1

;

2

(

n

+

j i

)!

1 C C C C C C C C C C C A 1i;jr :

Hereweusethe onventionthat 1 m

!

=

0ifm<0. Deneg

(

r

)

n

(

a;x

)

by g

(

r

)

n

(

a;x

)

=

f

(

r

)

n

(

a r

+

1;x

)

:

(99)

Fundamental quadrati equation for f

(

r

)

n

(

a;x

)

ApplyingtheD-Jadjointmatr ixtheorem,weobtain

Lemma

(

r

+

n

)

f

(

r

)

n

(

a;x

)

f

(

r

)

n a

+

1;x 1 2 ! nf

(

r

)

n 1

(

a;x

)

f

(

r

)

n

+

1 a

+

1;x 1 2 !

=

r f

(

r 1

)

n a

+

1;x 1 2 ! f

(

r

+

1

)

n

(

a;x

)

:

Fromthislemmaweobtain

Proposition f

(

r

)

n

(

a;x

) = (

1

)

rn f

(

n

)

r

(

a;x

)

and f

(

r

)

n

(

a;x

) =

f

(

n

)

r

(

a;x

)

:

(100)

Importantquadrati equationsfor f

(

r

)

n

(

a;x

)

Theorem Thef

(

r

)

n

(

a;x

)

satisesthefollowingquadrati formulas:

f

(

r 1

)

n 1 a 1;x 1 2 ! f

(

r

)

n

(

a;x

)

f

(

r 1

)

n 1

(

a;x

)

f

(

r

)

n a 1;x 1 2 !

=

n

+

r 1 2 f

(

r 1

)

n

(

a;x

)

f

(

r

)

n 1 a 1;x 1 2 ! ; x a 2 f

(

r 1

)

n

(

a;x 1

)

f

(

r

)

n 1 a 1;x

+

1 2 !

+

x

+

a 2

+

r 1 f

(

r 1

)

n

(

a;x

)

f

(

r

)

n 1 a 1;x 1 2 !

=

2f

(

r 1

)

n 1 a 1;x 1 2 ! f

(

r

)

n

(

a;x

)

:

(101)

Importantquadrati relations for g

(

r

)

n

(

a;x

)

Theorem Theg

(

r

)

n

(

a;x

)

satisesthefollowingquadrati formulas:

g

(

r 1

)

n a 1;x 1 2 ! g

(

r

)

n a;x

+

1 2 ! g

(

r 1

)

n

(

a;x

)

g

(

r

)

n

(

a 1;x

)

=

n 2 g

(

r 1

)

n

+

1

(

a;x

)

g

(

r

)

n 1

(

a 1;x

)

; x a r

+

1 2 ! g

(

r 1

)

n a;x 1 2 ! g

(

r

)

n 1 a 1;x

+

1 2 !

+

x

+

a r

+

1 2 ! g

(

r 1

)

n a;x

+

1 2 ! g

(

r

)

n 1 a 1;x 1 2 !

=

2g

(

r 1

)

n 1

(

a 1;x

)

g

(

r

)

n

(

a;x

)

:

(102)

Theorem AllofG L 1

(

a;b; ;;

)

,G L 2

(

a;b; ;;

)

,G S 1

(

a;b; ;;

)

,and G S 2

(

a;b; ;;

)

satisfy G

(

a;b 1; ;;

)

G

(

a

+

1;b

+

1; 2;

+

1; 1

)

=

G

(

a

+

1;b; 2;

+

1; 1

)

G

(

a;b; ;;

)

G

(

a

+

1;b; 1;

+

1; 1

)

G

(

a;b; 1;;

)

:

(103)

A spe ialvaluefor F L

(

a;b; ;;

)

Proposition Leta;r0beintegers. (i)If 2a r 1 rthen F L

(

a;a

+

r; ;;0

) = (

1

)

r

(

+

a

)

2

(

a

+

)(

a

+

1

)

2 : (ii)If 0then F L

(

a;a

+

r; ; ;

) = (

1

)

r

(

+

a

+

)

2

(

a

+

)(

a

+

1

)

2 r 1 Y k

=

0 k

!(

a

+

)!

(

k

+

)!(

k

+

a

+

)!

:

(104)

A spe ialvaluefor F S

(

a;b; ;;

)

Proposition (iii)If 2a r 1 r then F S

(

a;a

+

r; ;;r 1

) = (

1

)

r

(

+

a

)

2

(

a

+

)(

a

+

1

)

2

+

r

(

r 1

)

2 : (iv)If 0then F S

(

a;a

+

r; ; ;

) = (

1

)

r

(

+

a

+

)

2

(

a

+

)(

a

+

1

)

2

+

r

(

r 1

)

2 r 1 Y k

=

0 k

!(

k

+

a

+

r

+

1

)!

(

k

+

r

+

1

)!(

k

+

a

+

)!

:

(105)

(106)

Another expression for f

(

r

)

n

(

a;x

)

. Proposition Ifr

=

2,f

(

2

)

n

(

a;x

)

isexpressedbythefollowingterminating

hypergeometr i ser ies

4 F 3 : f

(

2

)

n

(

a;x

)

= (

1

)

n a 2

+

1 n

+

x n a 2

+

1 n x n 4 F 3 0 B B B B B a 2

+

1 n; a

+

1 2 n;a

+

2 n; n

;

a 2

+

1 n

+

x; a 2

+

1 n x;a

+

1 2n

;

1 1 C C C C C A :

Forr 3weCANNOTndanexpressionbyonehypergeometr i

(107)

A re ursive equation for f

(

r

)

n

(

a;x

)

. Proposition Ifr

=

1,thenf

(

1

)

n

(

a;x

)

satisestheinitial onditionf

(

1

)

0

(

a;x

) =

1 andthefollowing3termre urren e:

f

(

1

)

n

+

2(a;x

)

xf

(

1

)

n

+

1(a;x

) +

(

n

+

1

)(

a n

)

4 f

(

1

)

n

(

a;x

) =

0 forn 1.

(108)

A re ursive equation for f

(

r

)

n

(

a;x

)

. Proposition Ifr

=

2,thenf

(

2

)

n

(

a;x

)

satisestheinitial onditionf

(

2

)

0

(

a;x

) =

1andthe following4termre urren e:

f

(

2

)

n

+

3

(

a;x

)

( x 2

(

n

+

1

)

a

(

n 2

)(

n

+

2

)

4 ) f

(

2

)

n

+

2

(

a;x

)

+

(

n

+

2

)(

a n

)

4 ( x 2

(

n

+

4

)

a

(

n

+

1

)(

n

+

5

)

4 ) f

(

2

)

n

+

1

(

a;x

)

(

n

+

1

)(

n

+

2

)

2

(

a n

)

2

(

a n

+

1

)

64 f

(

2

)

n

(

a;x

) =

0

(

n 2

)

:

Forr 3weCANNOTndanyre ursiveequationforf

(

r

)

n

(

(109)

Weightedversion?

ForAzte diamondone andenethehightfun tionandrankof

tiling. Inthe aseofAzte re tanglewithholes,wedon'tknowhow

todenethehightfun tions. ForAzte diamondone an onsider

theweightedenumerationwiththenumberofverti aldominosand

(110)