CENTRALNA DELANNOYEVA ŠTEVILA

UNIVERZA V LJUBLJANI

FAKULTETA ZA MATEMATIKO IN FIZIKO Pedagoška matematika

Hana Rus

CENTRALNA DELANNOYEVA ŠTEVILA

Magistrsko delo

Mentor: prof. dr. Barbara Drinovec Drnovšek

Ljubljana, 2021

Zahvala

Najprej bi se rada zahvalila mentorici za vso pomoč pri pisanju magistrske naloge in tudi drugje.

Rada bi se zahvalila svoji družini, ki me je podpirala in vedno stala ob strani, tudi v težkih trenutkih.

Hvala vsem sošolcem, s katerimi smo se skupaj učili in motivirali, ter prijateljem, ki so mi stali ob strani in verjeli v moj uspeh.

Največja zahvala pa mojemu možu Gregorju, za vso pomoč, spodbudo in lepe trenutke. In seveda ogromna zahvala še Vidu in Juliji, ki sta pridno spala ponoči, da sem lahko napisala svoje delo.

Kazalo

Program dela vii

1 Uvod 1

2 Centralna Delannoyeva števila 2

3 Objekti, šteti z Delannoyevimi števili 4

3.1 Rodovna funkcija . . . 4

3.1.1 Objekt 1 . . . 6

3.1.2 Objekt 2 . . . 7

3.1.3 Objekt 3 . . . 7

3.2 Utežene vsote poti . . . 8

3.2.1 Objekt 4 . . . 8

3.2.2 Objekt 5 . . . 10

3.3 Bijekcijarazreži in zalepi . . . 10

3.3.1 Objekt 6 . . . 19

3.3.2 Objekt 7 . . . 20

3.3.3 Objekt 8 . . . 21

3.4 Dvojni dvig . . . 22

3.4.1 Objekt 9 . . . 22

3.4.2 Objekt 10 . . . 22

3.5 Poti od izhodišča do premice x= 2n . . . 31

3.5.1 Objekt 11 . . . 31

3.5.2 Objekt 12 . . . 34

3.5.3 Objekt 13 . . . 36

3.5.4 Objekt 14 . . . 37

3.5.5 Objekt 15 . . . 40

3.6 Poti, ki ne gredo nikoli pod abscisno os . . . 41

3.6.1 Objekt 16 . . . 41

3.6.2 Objekt 17 . . . 42

3.6.3 Objekt 18 . . . 44

3.6.4 Objekt 19 . . . 46

3.7 Sprehodi . . . 50

3.7.1 Objekt 20 . . . 50

3.8 Grafi . . . 51

3.8.1 Objekt 21 . . . 51

3.8.2 Objekt 22 . . . 53

3.9 Azteški diamant . . . 54

3.9.1 Objekt 23 . . . 55

3.10 Postavitve kroglic in tvorjenje besed . . . 61

3.10.1 Objekt 24 . . . 61

3.10.2 Objekt 25 . . . 61

3.11 Matrike . . . 62

3.11.1 Objekt 26 . . . 62

3.11.2 Objekt 27 . . . 63

3.12 Hiperoktaeder . . . 64 3.12.1 Objekt 28 . . . 64

4 Zaključek 65

Program dela

V magistrskem delu se posvetite centralnim Delannoyevim številom. Predstavite jih na različne načine: z rekurzivno zvezo, z rodovno funkcijo in z eksplicitno formulo.

Opišite čim več objektov, ki jih preštejejo centralna Delannoyeva števila.

Za osnovni vir literature uporabite:

R. A. Sulanke, Objects counted by the central Delannoy numbers, Journal of Integer Sequences, Vol. 6, 2003.

Podpis mentorja:

Ljubljana, 14. 6. 2021 prof. dr. Barbara Drinovec Drnovšek

Centralna Delannoyeva števila Povzetek

Centralna Delannoyeva števila (dn)n≥0 = 1,3,13,63,321,1683,8989, . . . preštejejo poti v celoštevilski mreži od točke(0,0)do točke(n, n) s koraki tipa(1,0),(0,1)in (1,1). Predstavimo še 28 objektov, ki jih lahko preštejemo z Delannoyevimi števili.

The central Delannoy numbers Abstract

The central Delannoy numbers(d_n)_n≥0 = 1,3,13,63,321,1683,8989, . . . count num- ber of lattice paths running from(0,0)to(n, n) that use the steps (1,0), (0,1)and (1,1). We give a collection of 28 objects which are counted by central Delannoy numbers.

Math. Subj. Class. (2010): 05A15

Ključne besede: centralna Delannoyeva števila, pot, bijekcija, rodovna funkcija Keywords: central Delannoy numbers, path, bijection, generating function

1 Uvod

Henri Auguste Delannoy je bil francoski amaterski matematik, po poklicu vojak.

Pri šestnajstih letih je sicer študiral matematiko, a ni ravno blestel. Šele trideset let kasneje ga je matematika začela zares zanimati, in sicer po dopisovanju s francoskim matematikom Edouardom Lucasom, ki je znan predvsem po svojih rezultatih v teo- riji števil. Delannoy je v svojem drugem članku, izdanem leta 1889, predstavil tako imenovana Delannoyeva števila, s katerimi si je pomagal pri reševanju problemov, s katerimi so se pred njim ukarjali že slavni matematiki Ampere, Bertrand, Huygens, Laplace in Rouche. (Povzeto iz vira [14].)

Slika 1: Henri Auguste Delannoy (1833-1915).

V magistrski nalogi si bomo najprej pogledali, kaj sploh so centralna Delannoyeva števila in kakšne so osnovne poti, štete z njimi. Pogledali si bomo rodovno funkcijo Delannoyevih števil in nato še 28 objektov, ki jih lahko preštejemo z Delannoyevimi števili. Magistrska naloga sledi članku [8], od koder je povzeta tudi večina dokazov.

2 Centralna Delannoyeva števila

Za začetek si poglejmo nekaj definicij.

Definicija 2.1. Naj bo I ⊂ R interval in naj bosta f, g : I → R zvezni funkciji.

Pot v ravnini R² je zvezna preslikava F : I → R², definirana s predpisom F(t) = (f(t), g(t)). Tir poti je njena zaloga vrednosti: F(I) ={(f(t), g(t));t ∈I}.

V tem delu bomo opazovali poti v mreži, zato si poglejmo še naslednjo definicijo.

Definicija 2.2. Pot P v mreži Z² dolžine k s koraki iz množice S je zaporedje vozlišč v₀, v₁, . . . , v_k ∈Z², kjer velja v_i−vi−1 ∈S za vsaki∈ {1, . . . , k}.

Sedaj lahko definiramo Delannoyevo število.

Definicija 2.3. Naj bosta m, n ∈ N ∪ {0}. Delannoyevo število D(m, n) opiše število poti od (0,0) do(m, n)s koraki oblike N = (0,1),E = (1,0)in U = (1,1).

Naj bosta i, j ∈ Z. Definiramo D(0,0) = 1 in D(i, j) =D(i−1, j) +D(i, j−1) + D(i−1, j−1), kjer velja D(i, j) = 0 zai <0alij <0. Dobljeno neskončno matriko Delannoyevih števil imenujemo Delannoyev seznam.

i\j 0 1 2 3 4 5 6

0 1 1 1 1 1 1 1

1 1 3 5 7 9 11 13

2 1 5 13 25 41 61 85

3 1 7 25 63 129 231 377

4 1 9 41 129 321 681 1289

5 1 11 61 231 681 1683 3653

6 1 13 85 377 1289 3653 8989

Tabela 1: Delannoyev seznam za i, j ∈ {0,1,2,3,4,5,6}, obkrožena so centralna Delannoyeva števila.

Definicija 2.4. Naj bo n ∈ N. Centralno Delannoyevo število D(n, n) = d_n opiše število vseh poti od (0,0) do (n, n) s koraki oblike N = (0,1), E = (1,0) in U = (1,1). Te poti imenujemo osnovne Delannoyeve poti.

Primer 2.5. Poglejmo si osnovne Delannoyeve poti za n= 1,2.

• Zan= 1 obstajajo tri različne poti, ki so prikazane na sliki 2. Torej je d₁ = 3.

• Za n = 2 pa imamo 13 različnih poti, ki so prikazane na sliki 3. Torej je d₂ = 13.

1 1

1 1

1 1

Slika 2: Poti od (0,0) do(1,1)s koraki oblike (0,1), (1,0) in(1,1).

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

Slika 3: Poti od (0,0) do(2,2)s koraki oblike (0,1), (1,0) in(1,1).

Navedimo rodovno funkcijo Delannoyevih števil d(z) = ∑

n≥0

d_nzⁿ = 1

√1−6z+z², (2.1)

ki jo bomo dokazali v poglavju 3.1.

Delannoyeva števila ustrezajo rekurzivni zvezi

(n+ 2)d_n+2 = 3(2n+ 3)d_n+1−(n+ 1)d_n;d₀ = 1, d₁ = 3 za n∈N∪ {0}, (2.2) kar bomo dokazali s pomočjo rodovne funkcije ∑

n≥0

d_nzⁿ= ^√_1−6z+z¹ ₂ in njenim odvo- dom ∑

n≥1

d_nnzⁿ⁻¹ = ^3−z

(√

1−6z+z²)³. Poglejmo si naslednjo enačbo:

∞

∑

n=0

(n+ 2)d_n+2zⁿ⁺¹ =

∞

∑

n=0

3(2n+ 3)d_n+1zⁿ⁺¹−

∞

∑

n=0

(n+ 1)d_nzⁿ⁺¹. (2.3)

Če dokažemo enačbo (2.3), potem izenačimo koeficiete prizⁿ⁺¹in dobimo rekurzivno zvezo (2.2). Izračunajmo levo stran:

L=

∞

∑

n=0

(n+ 2)d_n+2zⁿ⁺¹ =

∞

∑

m=2

md_mz^m−1 =

∞

∑

m=1

md_mz^m−1−1d₁z⁰ =

= 3−z

(√

1−6z+z²)³ −3.

Preuredimo še desno stran:

D₁ =

∞

∑

n=0

3(2n+ 3)d_n+1zⁿ⁺¹ =

∞

∑

m=1

3(2m+ 1)d_mz^m =

= 6z

∞

∑

m=1

mdmz^m−1+ 3

∞

∑

m=1

dmz^m = 6z

∞

∑

m=1

mdmz^m−1+ 3(

∞

∑

m=0

dmz^m−d0z⁰) =

= 6z(3−z) (√

1−6z+z²)³ + 3

√1−6z+z² −3.

D₂ =

∞

∑

n=0

(n+ 1)d_nzⁿ⁺¹ =

∞

∑

n=0

nd_nzⁿ⁺¹+

∞

∑

n=0

d_nzⁿ⁺¹ =

=z²

∞

∑

n=0

nd_nzⁿ⁻¹+z

∞

∑

n=0

d_nzⁿ= z²(3−z) (√

1−6z+z²)³ + z

√1−6z+z². Na desni strani torej dobimo

D=D₁−D₂ = 3−z (√

1−6z+z²)³ −3 =L.

Koeficienti na levi strani so enaki koeficientom na desni, torej rekurzivna zveza velja.

3 Objekti, šteti z Delannoyevimi števili

Pogledali si bomo 28 objektov, ki jih lahko preštejemo z Delannoyevimi števili. Naj- prej pa si poglejmo še nekaj definicij, ki jih bomo potrebovali v nadaljevanju.

Vsakemu koraku lahko pripišemo utež. Koraku z utežjo k lahko priredimo k obar- vanih korakov. Torej koraku z utežjo 2 lahko priredimo en moder in en rdeč korak.

Definicija 3.1. Teža poti je produkt uteži vseh korakov na poti z uteženimi koraki.

Definicija 3.2. Teža množice poti je vsota uteži vseh poti.

3.1 Rodovna funkcija

Poglejmo si najprej splošni model poti v mreži, kjer so dovoljeni koraki oblike U_t = (1,1) z utežjo t, D₁ = (1,−1) z utežjo 1 in hE_s = (h,0) z utežjo s, kjer je h poljubno fiksno naravno število.

Zan ≥0definiramo množiciU(n)inC(n), in sicer takole: U(n)je množica vseh poti

brez omejitev od(0,0)do(n,0),C(n)pa množica vseh poti vU(n), omejenih s pogo- jem, da ne gredo nikoli podx-os. Rodovni funkciji sta oblikec(z) :=∑

n≥0|C(n)|·zⁿ inu(z) :=∑

n≥0|U(n)| ·zⁿ.

Za vsako pot v množici C(n) velja natanko ena od naslednjih možnosti:

1. ima dolžino 0: obstaja ena taka pot,

2. začne se s korakom hE = (h,0), potem pa sledi pot z omejitvijo: obstaja z^hc(z) takih poti, torej je vsota njihovih uteži enakasz^hc(z),

3. začne se s korakom U, sledi translacija poti z omejitvami (pot ne gre pod premicoy= 1), sledi korakDin nato sledi še ena pot z omejitvijo: vsota uteži takih poti je enaka tz¹c(z)z¹c(z) =tz²c²(z).

Dobimo torej enačbo

c(z) = 1 +sz^hc(z) +tz²c²(z), (3.1) katere rešitev je

c(z)_1,2 = (1−sz^h)±√

s²z^2h −2sz^h + 1−4tz²

2tz² . (3.2)

Podobno tudi za vsako pot v množici U(n) velja natanko ena od naslednjih možnosti:

1. ima dolžino 0: obstaja ena taka pot,

2. začne se s korakom hE = (h,0), sledi pa pot brez omejitev: obstaja z^hu(z) takih poti, torej je vsota njihovih uteži enakasz^hu(z),

3. začne se s korakom U (ali D), sledi pot z omejitvijo, torej taka pot, ki ne gre nikoli pod x-os (ali z zrcalno omejitvijo, torej taka pot, ki ne gre nikoli nad x-os, če je bil prvi korakD), sledi korakD(aliU) in nato še pot brez omejitev:

vsota uteži takih poti je enaka2tz¹c(z)z¹u(z) = 2tz²c(z)u(z).

Dobimo enačbo

u(z) = 1 +sz^hu(z) + 2tz²c(z)u(z). (3.3) Če vstavimo rešitev enačbe (3.1) v enačbo (3.3), dobimo

u(z) = 1

√1−2sz^h +s²z^2h−4tz². (3.4) Če korake na osnovnih Delannoyevih poteh zarotiramo za−45^◦, se korak N = (0,1) preslika v korak U = (1,1), korakE = (1,0)se preslika v korak D= (1,−1), korak U = (1,1)pa se preslika v korak 2E = (2,0). Torej dobimo poti od(0,0)do(2n,0) s koraki U = (1,1), D = (1,−1) in 2E = (2,0), kar so ravno poti iz objekta 1. V tem primeru je utež korakaU enaka 1, torej je t= 1. Vodoraven korak pa je oblike (2,0)z utežjo 1, torej jeh= 2ins= 1. V tem primeru jeu(z) = ^√_1−6z+z¹ ₂. Izpeljali

smo rodovno funkcijo za Delannoyeva števila.

Premislimo še, ali je u(z) rodovna funkcija za Delannoyeva števila še pri kaki dru- gačni izbiri parametrov t, h in s. Veljati mora u(z) = d(z) (spomnimo se for- mule (2.1)), torej

√ 1

1−2sz^h+s²z^2h−4tz² = 1

√1−6z+z². (3.5) Od tod sledi, da je bodisi h= 1 bodisih = 2. V primeruh= 1 dobimo, da je s = 3 int= 2, v primeruh= 2 pa imamo dve možnosti, in sicer je bodisis =t = 1bodisi s = −1 in t = 2. Skupno dobimo torej tri možnosti: h = 1, s = 3, t = 2; h = 2, s = 1, t= 1 in h= 2, s=−1, t= 2.

3.1.1 Objekt 1

Naj bon∈N. V objektu 1 obravnavamo poti od(0,0)do(2n,0)s korakiU = (1,1), D= (1,−1) in2E = (2,0). Število vseh takih poti je enako Delannoyevemu številu d_n.

Primer 3.3. Zan = 2je centralno Delannoyevo število d₂ = 13.Enako obstaja 13 različnih poti od (0,0) do(4,0)s koraki U = (1,1),D= (1,−1) in2E = (2,0).

1 2 3 4 1

2

1 2 3 4 1

2

1 2 3 4 1

2

1 2 3 4 1

2

1 2 3 4 1

2

1 2 3 4

−1

−2

1 2 3 4

−2

−1

1 2 3 4

−1

−2

1 2 3 4

−1

−2

1 2 3 4

−1

−2

1 2 3 4

−1 1

1 2 3 4

−1 1

1 2 3 4

−1 1

Slika 4: Poti od(0,0)do (4,0) s koraki oblike(1,1), (1,−1)in (2,0).

Ugotovili smo že, da poti iz objekta 1 dobimo iz osnovnih Delannoyevih poti z rotacijo za −45^◦.

Poglejmo si še kombinatoričen dokaz:

d_n=

n

∑

k=0

(n k

)(n+k k

)

zan ≥0

Ker je pot od(0,0)do(2n,0)s koraki dolžine 1 ali 2 v smeri x, je največn korakov U, velja pa še, da je enako korakov U in D. Korak U lahko izberemo na k mestih izmed n možnih. Korak D lahko prav tako izberemo na k mestih in sicer izmed n+k objektov, saj imamon mest za D ink korakov oblike U.

3.1.2 Objekt 2

Naj bo n∈N. V objektu 2 računamo težo množice poti od (0,0) do(n,0) s koraki U₂ = (1,1) z utežjo 2, D₁ = (1,−1) z utežjo 1 in E₃ = (1,0) z utežjo 3. Teža množice takih poti je enaka Delannoyevemu številu d_n.

Namesto da korake utežimo, jim lahko priredimo toliko barv, kolikor ima korak utež.

Koraku U₂ torej priredimo moder korak U in rdeč korak U, koraku E₃ pa moder, rdeč in zelen korakE. Torej obravnavamo poti od(0,0)do(n,0)s korakiU = (1,1), D = (1,−1) in E = (1,0), kjer so koraki U pobarvani neodvisno modro ali rdeče, koraki E pa modro, rdeče ali zeleno.

Primer 3.4. Za n= 2 je d₂ = 13 :

1 2

−1 1

Slika 5: Imamo tri možno- sti za prvi korak in tri mo- žnosti za drugi korak, torej skupno3×3 = 9možnosti.

1 2

−1 1

Slika 6: Imamo dve mo- žnosti za prvi korak in eno možnost za drugi korak, torej skupno2×1 = 2mo- žnosti.

1 2

−1 1

Slika 7: Imamo eno mo- žnost za prvi korak in dve možnosti za drugi korak, torej skupno1×2 = 2mo- žnosti.

Slika 8: Poti od (0,0)do (2,0)z uteženimi koraki oblike (1,1)₂, (1,−1)₁ in (1,0)₃. Iz zgornjih treh slik skupaj dobimo torej 9 + 2 + 2 = 13, kar je ravno enako d₂.

Objekt 2 ustreza primeru iz razdelka 3.1 za t = 2, h = 1 in s = 3, za katerega smo izpeljali, da ustreza rodovni funkciji za Delannoyeva števila.

3.1.3 Objekt 3

Naj bo n ∈ N. V objektu 3 računamo vsoto uteži poti od (0,0)do (2n,0) s koraki U2 = (1,1) z utežjo 2, D1 = (1,−1) z utežjo 1 in 2E−1 = (2,0) z utežjo -1. Vsota uteži takih poti je enaka Delannoyevemu številu d_n.

Primer 3.5. Poglejmo si primer za n = 2. Za lažje računanje bomo korake U₂ = (1,1) z utežjo 2 narisali modro, korake 2E₋₁ = (2,0) z utežjo -1 pa rdeče, kot je prikazano na sliki 9.

V prvih 6 primerih imamo dva modra koraka z utežjo 2, torej6·2·2 = 24, v drugih

šestih primerih imamo en moder korak z utežjo 2 in en rdeč korak z utežjo -1, torej 6·2·(−1) = −12, v zadnjem primeru pa imamo 2 rdeča koraka z utežjo -1, torej (−1)·(−1) = 1. Skupaj torej dobimo 24−12 + 1 = 13, kar je enakod₂.

1 2 3 4 1

2

1 2 3 4 1

2

1 2 3 4 1

−1

1 2 3 4 1

−1

1 2 3 4

−2

−1

1 2 3 4 1

−1

1 2 3 4 1

−1

1 2 3 4 1

−1

1 2 3 4 1

−1

1 2 3 4 1

−1

1 2 3 4 1

−1

1 2 3 4 1

−1

1 2 3 4 1

−1

Slika 9: Poti od (0,0) do(4,0)s koraki oblike (1,1)₂, (1,−1)₁ in(2,0)−1.

Objekt 3 ustreza primeru iz razdelka 3.1 zat = 2,h = 2in s=−1, za katerega smo izpeljali, da ustreza rodovni funkciji za Delannoyeva števila.

3.2 Utežene vsote poti

V tem poglavju si bomo pogledali še dva objekta, kjer obravnavamo utežene vsote poti.

3.2.1 Objekt 4

Definicija 3.6. Vrh na poti je sredinsko vozlišče urejenega zaporedja korakov U D, kjer je U = (1,1) inD= (1,−1).

Naj bo n∈N.V objektu 4 računamo uteženo vsoto poti od(0,0)do(2n,0)s koraki U = (1,1) in D = (1,−1), kjer ima vsak vrh utež 2. Utežena vsota takih poti je enaka Delannoyevemu številu dn.

Primer 3.7. Za n= 2 je utežena vsota poti enaka 4×2 + 1×2×2 + 1 = 13. To pa je ravno enako d₂.

1 2 3 4

−1

−2

1 2 3 4 2

1

1 2 3 4

−1 1

1 2 3 4

−1 1

1 2 3 4

−1 1

1 2 3 4

−1 1

Slika 10: Poti od (0,0) do (4,0) s koraki oblike (1,1) in(1,−1), kjer imajo vrhovi, ki so označeni z rdečo, utež 2.

Vsoto uteženih poti bomo izračunali na dva načina. Prvi način je kombinatoričen:

d_n=

n

∑

k=0

(n k

)2

2^k zan ≥0 (3.6)

Sk označimo število vrhov na poti (število vrhov je najmanj 0 in največ n). Zapo- redje korakov U D da vrh, torej imamo na poti natanko k zaporedij U D. Na poti je 2n korakov, od tega n korakov oblike U in n korakov oblike D. Izmed n korakov oblike U izberemo k takih, ki jim sledi korak D. Podobno izmed n korakov oblike Dizberemok takih, pred katerimi je korak oblike U. Na sliki 10 so z oranžno barvo označeni vsi koraki oblike U, ki jim sledi korak D, z modro pa vsi koraki D, pred katerimi je korak U. Ker ima vsak vrh utež 2, imamo za vsakega od k vrhov 2 možnosti, skupno torej2^k.

Drugi dokaz pa sledi iz bijekcije z objektom 1. V objektu 4 ima vsak vrh utež 2, torej vrhove pobarvamo neodvisno bodisi z modro bodisi z rdečo. S tem smo poti z utežjo 2 priredili dve različni poti. Če vsako zaporedje korakov U D z modrim vrhom preslikamo v korak (2,0), dobimo bijekcijo z objektom 1. Ker je vrh sre- dinsko vozlišče zaporedja korakov U D, označimo zaporedja U D z modrimi vrhovi z U D_m, zaporedja U D z rdečimi vrhovi pa z U D_r. Preslikava f slika iz množice poti iz objekta 1 v množico obarvanih poti v objektu 4, definiramo pa jo na njenih gradnikih: f(U) = U, f(D) = D, f((2,0)) = U D_m. Preslikava g pa slika mno- žico obarvanih poti iz objekta 4 v množico poti iz objekta 1. Definiramo jo takole:

g(U D_m) = (2,0), g(U D_r) =U D, g(U) = U, če U ni pred D ing(D) = D, če D ni zaU.

Za dokaz, da je f bijekcija, je treba dokazati, da je f ◦g =id in g◦f =id:

(f ◦ g)(U D_r) = f(g(U D_r)) = f(U D) = U D, (f ◦ g)(U D_m) = f(g(U D_m)) = f((2,0)) =U D_m. V primeru, da U ni pred D velja(f◦g)(U) = f(g(U)) =f(U) = U, v primeru, da D ni za U pa (f ◦g)(D) = f(g(D)) = f(D) = D. Velja torej f◦g =id. Podobno dokažemo še, da jeg◦f =id: (g◦f)(U) =g(f(U)) =g(U) = U, (g ◦f)(D) = g(f(D)) = g(D) = D in (g ◦f)((2,0)) = g(f((2,0))) = g(U D_m) = (2,0).

3.2.2 Objekt 5

Naj bo n ∈N. Pri petem objektu računamo uteženo vsoto poti od (0,0) do (2n,0) s koraki U = (1,1) in D = (1,−1), kjer ima vsak korak U, ki je na lihem mestu v poti, utež 2. Utežena vsota takih poti je enaka Delannoyevemu številu dn.

Primer 3.8. Zan= 2 je utežena vsota poti 2 + 2 + 1 + 4 + 2 + 2 = 13, kar je ravno enakod₂.Za lažje računanje so na sliki 11 koraki oblike(1,1)na lihem mestu v poti označeni z rdečo barvo.

1 2 3 4 2

1

1 2 3 4

−1 1

1 2 3 4

−1 1

1 2 3 4

−1

−2

1 2 3 4

−1 1

1 2 3 4

−1 1

Slika 11: Poti od(0,0)do(4,0)s koraki oblike(1,1)in(1,−1), kjer ima vsak korak oblike (1,1) na lihem mestu v poti utež 2.

Poglejmo si bijekcijo z objektom 2. Vsaka pot v objektu 5 je zaporedje parov korakov (ker je pot od (0,0)do(2n,0), je v poti sodo korakov), kjer je prvi korak v paru na lihem, drugi korak pa na sodem mestu v poti. Možni pari so U U, U D,DU in DD.

Preslikavaf slika množico uteženih poti iz objekta 5 v množico uteženih poti objekta 2, definirana pa je takole: f(U U) = U, f(U D) = (1,0)2, f(DU) = (1,0)1 in f(DD) = D. Pazimo, da par korakov z utežjo 2 (torej tak par korakov, ki ima na prvem mestu U), slikamo v korak z utežjo 2. Za dokaz, da je f bijekcija, defini- rajmo še preslikavog, ki slika iz množice uteženih poti objekta 2 v množico uteženih poti objekta 5. Za definicijo preslikave g utežen korak (1,0)₃ enolično zapišemo kot (1,0)₁ in(1,0)₂, kjer korak (1,0)₁ predstavlja moder korak, (1,0)₂ pa rdeč in zelen korak (1,0). Preslikava g je torej definirana z naslednjim predpisom: g(U) = U U, g(D) = DD, g((1,0)₂) =U D ing((1,0)₁) = DU.

Sedaj je potrebno dokazati samo še to, da je preslikava g inverz preslikave f. Poka- žimo najprej, da velja f◦g =id: (f◦g)(U) =f(g(U)) =f(U U) = U,(f◦g)(D) = f(g(D)) = f(DD) = D, (f ◦ g)((1,0)₂) = f(g((1,0)₂)) = f(U D) = (1,0)₂ in (f◦g)((1,0)₁) =f(g((1,0)₁)) = f(DU) = (1,0)₁. Podobno dokažemo šeg◦f =id:

(g◦f)(U U) =g(f(U U)) =g(U) =U U,(g◦f)(U D) =g(f(U D)) =g((1,0)2) =U D, (g◦f)(DU) =g(f(DU)) =g((1,0)₁) =DU in (g◦f)(DD) =g(f(DD)) = g(D) = DD. Torej je preslikava f res bijekcija.

3.3 Bijekcija razreži in zalepi

Za naslednje tri primere potrebujemo naslednjo definicijo.

Definicija 3.9. Schröderjeva pot je pot s koraki(1,1),(1,−1)in(2,0), ki se začne in konča nax-osi in ne gre nikoli podx-os. Dvignjena Schröderjeva pot je Schröderjeva pot, ki se osix dotakne samo v začetni in končni točki.

Za dokaz naslednjih primerov bomo definirali bijekcijorazreži in zalepi iz članka [4].

Opazovali bomo poti s koraki oblike(1,1),(1,−1)in vodoravnimi koraki ter njihove momente. Bijekcijarazreži in zalepi povezuje momente poti in moč množic določenih poti brez omejitev. Ta bijekcijarazreže vsako dvignjeno pot na več dobro definiranih podpoti, ki jih v določenem vrstnem reduzlepimo nazaj skupaj tako, da dobimo pot brez omejitev.

Poglejmo si najprej poti in definirajmo njihove momente. Označimo korake U = (1,1), D = (1,−1) in množico vodoravnih korakov H = {(h₁,0),(h₂,0), . . .}, kjer je h_i ∈ Z. Naj bo U(n) množica poti brez omejitev od (0,0) do (n,0) s koraki iz množice {U, D} ∪ H. Naj boE(n)množica dvignjenih poti iz U(n), torej množicah takih poti izU(n), ki so razen v začetni in končni točki strogo nad abscisno osjo.

Opomba 3.10. ZaH={(2,0)} dobimo Schröderjevo pot.

Primer 3.11. Množica E(6) za H ={(2,0)} so dvignjene poti od (0,0) do (6,0) s koraki U, D in 2E = (2,0), kar so ravno poti iz objekta 6 za n= 2.

Definicija 3.12. Dyckova pot reda n je taka pot od (0,0)do (2n,0) s koraki U = (1,1) inD= (1,−1), ki ne gre nikoli pod x-os.

Definicija 3.13. Catalanovo število je definirano kot Cn= _n+1¹ (_2n

n

) zan∈N∪ {0}.

Prva Catalanova števila so torej: C₀ = 1,C₁ = 1,C₂ = 2,C₃ = 5,C₄ = 14,C₅ = 42.

Velja rekurzivna zveza: C_n+1 =

n

∑

k=0

C_kCn−k,C₀ = 1. Dokaz najdemo v [12].

Trditev 3.14. Število Dyckovih poti reda n je enako n-temu Catalanovemu številu C_n.

Dokaz. Označimo z a_n število Dyckovih poti reda n. Velja a₀ = 1 in a₁ = 1, saj obstaja samo pot U D. Za n = 2 obstajata dve poti, in sicer P₁ = U DU D in P₂ =U U DD, torej je a₂ = 2. Dyckova pot reda n pa izgleda takole:

(2k,0)

Slika 12: Dyckova pot redan, kjer je z rdečo točko označeno, kje se pot predzadnjič dotakne abscisne osi.

Rdeče označena točka s koordinatama (2k,0) je točka, kjer se pot predzadnjič dotakne abscisne osi. Levo od te točke imamo torej Dyckovo pot reda k. Na desni strani pa dobimo Dyckovo pot redan−k−1, saj sta prvi in zadnji korak določena

(prvi korak mora bitiU in zadnji D, zato dobimo2n−2k−2 = 2(n−k−1)). Torej velja: an=

n−1

∑

k=0

ak·an−k−1 =Cn

V primeru, ko imamo samo korake oblike U = (1,1) in D = (1,−1), torej ko je množica H prazna, je množica poti E(2n+ 2) enaka množici dvignjenih Dyckovih poti od (0,0) do(2n+ 2,0). Ustrezna moč množicE(2n+ 2) inU(2n) je:

|E(2n+ 2)|= 1

n+ 1|U(2n)|= 1 n+ 1

(2n n

)

(3.7) Vemo, da je |U(2n)| =(_2n

n

), saj iz 2n korakov izberemo n mest za korake U, s tem pa določimo tudi mesta za korakeD. Preostanek zgornje enačbe dokažemo v trditvi 3.32.

Naj (0, p₀),(1, p₁), . . . ,(x, p_x), . . . ,(n, p_n) označujejo točke na poljubni poti P za poljubno množico H. To so vse točke na mreži v poti P, ne samo končne točke korakov. Predstavimo tri momente: ničelni, prvi in drugi moment.

Definicija 3.15. Za j = 0,1,2 definiramo vsoto j-tega momenta poti v E(n) kot:

µ(n, j) := ∑

P∈E(n) 1 n−1

∑

0<i<n(p_i)^j.

Opomba 3.16. Ker je P pot dolžine n, vsebuje n + 1 točk. Začetna in končna točka imata ordinato enako nič, vse vmesne točke pa imajo ordinato večjo od nič, saj imamo dvignjene poti. Torej imamo natanko n−1 neničelnih p_i-jev.

Za poljubno množico H takoj dobimo enakost |E(n)| = µ(n,0). Velja tudi, da je (n−1)µ(n,1)enako površini območja, omejenega s potmi iz E(n) inx-osjo.

Primer 3.17. Poglejmo si spet primer poti izE(6)s koraki U, D in(2,0)(slika 20):

µ(6,1) = ∑

P∈E(6)

1 5

∑

0<i<6

(p_i)¹ = 1

5(9 + 7 + 8 + 6 + 6 + 5) = 41 5

Od tu sledi, da je (6−1)µ(6,1) = 5· ⁴¹₅ = 41. Površine območij, omejenih s potmi in x-osjo so S1 = 9, S2 = 7, S3 = 8, S4 = 6, S5 = 6 in S6 = 5. Torej je skupna površina enaka S =∑

S_i = 41.

Izračunajmo še µ(6,2) : µ(6,2) = ∑

P∈E(6)

1 5

∑

0<i<6

(p_i)² = 1

5(19 + 11 + 14 + 8 + 8 + 5) = 65 5 = 13 Trditev 3.18. Za dvignjene Dyckove poti velja:

(1) µ(2n+ 2,0) = _n+1¹ (_2n

n

)=|E(2n+ 2)|

(2) µ(2n+ 2,1) = _2n+1⁴ⁿ

Dokaz (1) sledi iz trditve 3.32, dokaz (2) pa iz posledice 3.31.

Za poljubno množico H velja:

µ(n+ 2, j) = ∑

P∈E(n+2)

1 n+ 1

∑

0<i<n+2

(p_i)^j =|U(n)|. (3.8) Dokaz enakosti najdemo v članku [9].

Preden definiramo bijekcijo razreži in zalepi si poglejmo domeno in kodomeno pre- slikave. Vsak moment definiran v 3.15 bomo predstavili z zbirko indeksiranih točk, imenovanihpike, ki ležijo pod potjo izE(n+ 2).

Definicija 3.19. Naj bo P dvignjena pot, (x, y) pa točka, ki leži strogo pod potjo P in šibko nadx-osjo. Naj bok celoštevilski parameter. Potem jepika kopija točke (x, y), indeksirana sk. Označimo jo z [P,(x, y), k].

Definicija 3.20. Naj boP pot. Potem [P,(x, P_x)] označujepikasto pot, določeno s točko (x, p_x) na tiru poti P.

Torej ima vsaka pot od(0,0)do (n,0)natanko n+ 1 različnih kopij.

Trditev 3.21. V primerih, kjer je natanko ena pika v vsaki točki strogo pod dano potjo P, po trapeznem pravilu sledi, da je število pik enako ploščini območja, ome- jenega s potjo P in abscisno osjo.

Opomba 3.22. Trapezno pravilo je tehnika aproksimacije določenega integrala:

b

∫

a

f(x)dx ≈ ^∆x₂ (f(x₀) + 2f(x₁) + 2f(x₂) + · · ·+ 2f(x_N−1 +f(x_N)), kjer smo in- terval [a, b] razdelili na N enakih delov: a= x₀ < x₁ < x₂ <· · · < xN−1 < x_N =b in∆x= ^b−a_N .

Dokaz. Naj a označuje število takih pik. Upoštevamo, da je ∆x = 1 in f(x₀) = f(x_N) = 0. Z uporabo trapeznega pravila dobimo: S = ¹₂(2(f(x₁)+· · ·+f(x_N−1))) = f(x₁) + . . . f(x_N−1) = a, saj je strogo pod f(x₁) natanko f(x₁) pik, pod f(x₂) natanko f(x₂)pik in tako naprej.

Primer 3.23. Poglejmo si dvignjene Dyckove poti izE(6), torej dvignjene poti od (0,0) do (6,0) s koraki tipa U = (1,1) in D = (1,−1). Ploščina območja na levi sliki je enaka 9, na desni pa 7.

1 2 3 4 5 6

1 2 3

1 2 3 4 5 6

1 2 3

Slika 13: Na levi sliki imamo devet pik, na desni pa sedem.

Iz druge točke trditve 3.18 sledi, da je skupna ploščina pod dvignjenimi Dyckovimi potmi enaka:

|{[P,(x, y),0];P ∈ E(2n+ 2),0< x < n+ 2,0≤y < p_x}|= 4ⁿ.

V primeru 3.23 je skupna ploščina pod dvignjenimi Dyckovimi potmi iz E(6) enaka 9 + 7 = 16 = 4².

V primeru, ko je H prazna množica, je tudi število presečišč poti iz U(n) z x-osjo enako 4ⁿ.

Primer 3.24. Poglejmo si pikaste poti, ki ustrezajo pikam iz slike 13. V tem primeru imamo pikaste poti od (0,0) do(4,0). Imamo 16 = 4² presečišč z x osjo.

1 2 3 4 1

2

1 2 3 4 1

2

1 2 3 4 1

2

1 2 3 4 1

2

1 2 3 4 1

2

1 2 3 4

−1 1

1 2 3 4

−1 1

1 2 3 4

−1 1

1 2 3 4

−1 1

1 2 3 4

−1 1

1 2 3 4

−1 1

1 2 3 4

−1 1

1 2 3 4

−1 1

1 2 3 4

−1

1 −1 1 2 3 4

−2

1 2 3 4

−1

−2 Slika 14: Poti iz množice U(4).

Poglejmo si drugi moment iz enačbe (3.8):

Trditev 3.25. Naj bo n ≥0. Potem za poljubno množico korakov {U, D} ∪ H velja

∑

P∈E(n+2) n+1

∑

i=1

(p_i)² = (n+ 1)|U(n)|.

Dokaz. Pod vsako točko(x, px)narišemop²_x pik. Leva stran enačbe prešteje te pike.

Desna stran enačbe pa ustreza dejstvu, da za vsako pot iz U(n) dobimo (n + 1) pikastih poti.

Primer 3.26. Poglejmo si E(6) inU(4) v primeru, ko je H=∅. V tem primeru je U(4) ={U U DD, U DU D, U DDU, DU U D, DU DU, DDU U}.Prvi dve sliki predsta- vljata 30 pik za E(6), ki ustrezajo levi strani enačbe iz trditve 3.25.

1 2 3 4 5 6 1

2 3

1 2 3 4 5 6

1 2 3

Slika 15: Na levi sliki imamo 11 pik, na desni pa 19, skupaj torej 30 pik.

Na sliki 16 nam 30 točk predstavlja 30 pikastih poti iz U(4), saj vsaka točka določa drugo pikasto pot.

1 2 3 4

1 2

1 2 3 4

1 2

1 2 3 4

−1 1

1 2 3 4

−1 1

1 2 3 4

−1

−2

1 2 3 4

−1

−2

Slika 16: Na vsakih izmed 6 poti imamo 5 točk, torej skupaj 30 pikastih poti.

Kot vidimo na sliki 15 v primeru 3.26 smo za domeno želene bijekcije uporabili konfiguracijo kvadratnih seznamov pik. Izkaže se, da je bolj praktično, če za domeno uporabimo trikotne sezname pik. Torej moramo kvadratne sezname s transformacijo pretvoriti v trikotne.

Primer 3.27. Poglejmo si primer, ko je (x, p_x) = (x,3)točka na poti P.

Slika 17: Transformacija kvadrata 3× 3 pik v trikotnik pik. Z rdečo barvo so označene pike, ki se prestavijo.

Za dano pot P in točko (x, px) na poti P definiramo to transformacijo takole: ∆ : {[P,(x, y), k]; 0 ≤ y < p_x,0 ≤ k < p_x} → {[P,(x, y), k^′];−p_x < k^′ < p_x,0 ≤ y <

p_x− |k^′|}, kjer velja

∆([P,(x, y), k]) =

{[P,(x, y), k] ; 0≤y < p_x−k [P,(x, y−p_x+k),−p_x+k] ;p_x−k ≤y < p_x

Naj bo n≥0. Definirajmo sedaj bijekcijorazreži in zalepi takole:

φ:PIKE(n+ 2)→PIKPOTI(n)

Domena preslikave je množica pik PIKE(n+ 2) = {[P,(x, y), k];P ∈ E(n+ 2),0<

x < n+ 2,−p_x < k < p_x,0 ≤y < p_x− |k|}, kodomena pa množica vseh usmejenih poti, tvorjenih iz poti U(n) : PIKPOTI(n) = {[P,(x, px)];P ∈ U(n),0 ≤ x ≤ n}.

Množica PIKPOTI(n) je očitno izomorfna produktuU(n)× {0,1, . . . , n}. Bijekcija deluje tako, da poljubno dvignjeno pot razreže na krajše dobro definirane poti in jih nato zlepi skupaj v določenem vrstnem redu tako, da dobimo pot brez omejitev.

Predpostavimo najprej, da je k ≥ 0. Za poljubno piko [P,(x, y), k]∈ PIKE(n+ 2) lahko določimo štiri točke na poti P :

1. Naj boθ taka točka na P,ki je direktno nad točko (x, y), torej θ = (x, p_x).

2. Naj boε= (ε₁, ε₂)najbližja točka naP levo od(x, y)z ordinatoy=p_x−k−1.

3. Naj boλ= (λ₁, λ₂) najbližja točka na P levo od (x, y) z ordinato y=λ₂. 4. Naj boρ= (ρ₁, ρ₂) najbližja točka naP desno od (x, y)z ordinato y=ρ₂. Poglejmo si sedaj dve možnosti. Prva možnost je, da je y = 0. Od tod sledi, da je λ = (0,0) in ρ = (n+ 2,0), saj sta to edini dve točki na poti P z ordinato y = 0.

Naj bo L2 podpot P od λ doε inR1 podpot P od ε doρ. V tem primeru je torej P =L₂R₁.Naj bo R˜₁ pot, pridobljena iz potiR₁ tako, da odstranimo prvi in zadnji korak. Definirajmoφ([L₂R₁,(x, y), k]) = [˜R₁L₂,(x^′, k)],kjer je točkaθ premaknjena po poti R˜₁ tako, da velja x^′ = x−ε₁−1. Opazimo, da noben del poti P^′ = R˜₁L₂ levo od (x^′, k) ne leži podx-osjo.

Primer 3.28. Poglejmo si primer za k = 2, in sicer piko [P,(12,0),2] ∈PIKE(30) in njeno sliko [P^′,(x^′, k)] = [P^′,(4,2)] ∈ PIKPOTI(28). V tem primeru je ε₂ = p_x−k−1 = 6−2−1 = 3, torej je točkaε= (7,3). Od tu dobimox^′ =x−ε₁−1 = 12−7−1 = 4. Primer je predstavljen na sliki 18.

Druga možnost je, da je y > 0. Od tod sledi, da je λ1 > 0 in ρ1 < n+ 2. Naj bo L₁ podpot P od (0,0) do λ, L₂ podpot P od λ do ε, R₁ podpot P od ε do ρ in R₂ podpot P od ρ do (n+ 2,0). V tem primeru je P = L₁L₂R₁R₂. Naj bo L˜₁R₁ pot, pridobljena iz poti L₁R₁ tako, da odstranimo prvi in zadnji korak. Definirajmo φ([L₁L₂R₁R₂,(x, y), k]) = [R₂L˜₁R₁L₂,(x^′, k)], kjer je točka θ premaknjena po poti R₁ tako, da velja x^′ =x+n+λ₁+ 1−ε₁−ρ₁.Opazimo, da v tem primeru del poti P^′ levo od (x^′, k)leži pod x-osjo.

Primer 3.29. Poglejmo si primer za k = 2, in sicer piko [P,(15,3),2] ∈PIKE(30) in njeno sliko [P^′,(x^′, k)] = [P^′,(22,2)] ∈PIKPOTI(28), na sliki 19. V tem primeru je θ = (15,7), ε₂ = p_x −k −1 = 7−2−1 = 4, torej je točka ε = (8,4). Od tu dobimo x^′ =x+n+λ₁ + 1−ε₁−ρ₁ = 15 + 28 + 7 + 1−8−21 = 22.

1 5 7 10 12 15 20 25 30 1

3 6

L₂

R₁

(x, y) λ

ε

θ

ρ

1 4 10 12 15 21 28

1 4

−3

R˜1 =C1

L₂ =C₂ (x^′, k)

γ

Slika 18: Pika [P,(12,0),2]∈PIKE(30) in slika [P^′,(4,2)]∈PIKPOTI(28).

1 5 7 8 15 21 25 30

1 3 4 7

L1

L₂

R₁

R₂ (x, y)

λ ε

θ

ρ

1 5 9 15 22 28

1 4

−3

−1

R₂ =A₁

A₂

L˜₁R₁ C₁

L₂ =C₂ (x^′, k)

α

β γ

Slika 19: Pika[P,(15,3),2]∈PIKE(30) in slika [P^′,(22,2)] ∈PIKPOTI(28).

V primeru, ko je k < 0, z REFL(P^′) označimo pot, ki jo dobimo, če pot P^′ pre- zrcalimo čez x-os. Definirajmo φ([P,(x, y), k]) = [REFL(P^′),(x^′, k)], kjer je pot P^′ definirana s preslikavo φ([P,(x, y),|k|]) = [P^′,(x^′,|k|)].

Če dodamo še vodoravne korake, ti ne vplivajo na definicijo preslikave φ ali na bi- jektivnost.

Dokazati moramo še, da je preslikava φ res bijektivna. Poiščimo njen inverz. De- finirajmo preslikavo ψ : PIKPOTI(n) → PIKE(n + 2). Za k ≥ 0 definiramo ψ v dveh možnostih, ki ustrezata možnostima iz definicije preslikave φ. Za k < 0

analogno kot pri preslikavi φ prezrcalimo pot čez x-os. Za poljubno pikasto pot [P^′,(x^′, k)]∈PIKPOTI(n) lahko določimo dve točki na poti P^′ :

1. Naj boα = (α₁, α₂)taka točka naP^′, ki je najbolj levo od vseh najnižjih točk, ki so levo od (x^′, k).

2. Naj bo γ = (γ₁, γ₂) taka točka na P^′, ki je najbolj desno od vseh najnižjih točk, ki so desno od (x^′, k).

Prva možnost je, da je α₂ = 0. Naj bo C₁ podpot P^′ od (0,0) do γ in C₂ podpot P^′ od γ do (n,0). V tem primeru je P^′ = C₁C₂. Defnirajmo ψ([C₁C₂,(x^′, k)]) = [C₂U C₁D,(x^′+n+ 1−γ₁,0), k]. V primeru 3.28 je γ = (21,−3) in (x^′, k) = (4,2).

Od tu sledi x=x^′+n+ 1−γ₁ = 4 + 28 + 1−21 = 12, torej je (x, y) = (12,0).

Druga možnost pa je, da jeα₂ <0.Na boβnajbližja točka levo od(x^′, k)z ordinato y =−1. Naj bo A₁ podpot P^′ od (0,0)do α, A₂ podpot P^′ od α doβ, C₁ podpot P^′ od β do γ in C₂ podpot P^′ od γ do (n,0). V tem primeru je P^′ = A₁A₂C₁C₂. Definirajmo ψ([A₁A₂C₁C₂,(x^′, k)]) = [U A₂C₂C₁DA₁,(x^′+n+ 1−α₁−γ₁,−α₂), k].

V primeru 19 je α = (9,−3), β = (15,−1), γ = (27,−1) in (x^′, k) = (22,2). Od tu izračunamo x=x^′+n+ 1−α₁−γ₁ = 22 + 28 + 1−9−27 = 15 in y=−α₂ = 3, torej je (x, y) = (15,3).

Če omejimo našo bijekcijo na k = 0, torej dobimo bijekcijo φ : {[P,(x, y),0];P ∈ E(n+ 2),0< x < n+ 2,0≤y < p_x} → {[P^′,(x^′,0)];P^′ ∈ U(n),0≤x^′ ≤n}. Od tu sledi, da je skupna ploščina pot potmi iz E(n+ 2) enaka številu presečišč z x-osjo poti iz U(n).

Trditev 3.30. Naj bo k ≥ 0 in n ≥ 0. Za množico korakov {U, D} ∪ H je skupna ploščina območij pod potmi E(2n+ 2) in nad premico y = k enaka številu pikastih poti U(n), določenih s točko z ordinato k.

Dokaz. Opazujmo območja, ki imajo natanko eno piko v vsaki celoštevilski točki, ki leži šibko nad premico y =k. Za vsako pot P in abscisox je bodisi px > k, kjer je stolpec p_x −k takih pik, bodisi p_x ≤ k, kjer ni stolpca pik. Stolpec potiskamo navzdol, dokler najnižja pika ne zadane abscisne osi. To nam da naslednji stolpec pik, kjer dodelimo parameter k : [P,(x,0), k],[P,(x,1), k], . . . ,[P,(x, px−k−1), k].

Ker je k sedaj fiksno število, je dokaz končan, če omejimo bijekcijo φ takole: φ : {[P,(x, y), k];P ∈ E(n+ 2),0 < x < n+ 2,0 ≤ y < p_x−k} → {[P^′,(x^′, k)];P^′ ∈ E(n),0≤x^′ ≤n}.

Posledica 3.31. Za množico korakov {U, D} je skupna ploščina območij pod potmi iz E(n+ 2) enaka 4ⁿ.

Dokaz posledice najdemo v članku [3].

Trditev 3.32. Naj bo m≥1in n≥0.Za poljubno množico korakov {U, D} ∪ H naj E(n, m) in U(n, m) označujeta taki podmnožici E(n) oziroma U(n), kjer ima vsaka pot m korakov oblike U. Potem velja (m+ 1)|E(n+ 2, m+ 1)|=|U(n, m)|.

Dokaz. Pod vsako pot P ∈ E(n + 2, m + 1) postavimo m+ 1 pik na x-os tako, da je vsaka pika postavljena pod končno točko koraka U. Naj bo k = 0 in y = 0. Potem je vsaka pika preslikana s prvo možnostjo preslikave φ v pikasto pot

φ([P,(x,0),0]) = [˜R₁L₂,(0,0)].Dobimo torej preslikavo φ:{[P,(x,0),0];P ∈ E(n+ 2, m+ 1), x pod končno točko korakaU} → {[P^′,(0,0)];P^′ ∈ U(n, m)}. Moč do- mene je(m+ 1)· |E(n+ 2, m+ 1)|, moč kodomene pa|U(n, m)|.Ker je φbijekcija, velja(m+ 1)· |E(n+ 2, m+ 1)|=|U(n, m)|.

3.3.1 Objekt 6

V objektu 6 opazujemo drugi moment množice dvignjenih Schröderjevih poti od (0,0) do(2n+ 2,0) s koraki U = (1,1), D= (1,−1) in2E = (2,0).

Delannoyevo število d_n je enako vsoti povprečij kvadratov višin točk v mreži po dvignjenih Schröderjevih poteh.

Primer 3.33. Poglejmo si primer za n = 2. V prvem primeru je vsota kvadratov višin enaka1 + 4 + 9 + 4 + 1 = 19, podobno izračunamo še v ostalih primerih. Vsota povprečij je torej ¹⁹₅ +⁵₅ + ⁸₅ +¹¹₅ +⁸₅ + ¹⁴₅ = ⁶⁵₅ = 13, kar je enakod₂.

1 2 3 4 5 6 1

2 3

1 4

9 4 1

P₁

1 2 3 4 5 6 1

2 3

1

4 1 4 1P₂

1 2 3 4 5 6 1

2 3

1 1 1 1 1 P₃

1 2 3 4 5 6 1

2 3

1

4 1 1 1 P₄

1 2 3 4 5 6 1

2 3

1 1 1

4 1 P₅

1 2 3 4 5 6 1

2 3

1

4 4 4 1

P₆

Slika 20: Dvignjene Schröderjeve poti od(0,0)do(6,0)s koraki oblikeU,D in2E.

Z roza barvo so označene pike pod končnimi točkami korakovU nax-osi.

Definirajmo sedaj bijekcijorazreži in zalepi, s katero iz poti iz objekta 6 dobimo poti iz objekta 1. Na sliki 20 smo na posameznih poteh iz objekta 6 označili pike pod končnimi točkami korakov U na x-osi. Uporabimo idejo dokaza trditve 3.32, torej za vsako piko posebej pogledamo, kam se preslika s prvo možnostjo preslikaveφ:

Iz dokaza vemo, da v vseh primerih velja (x^′, k) = (0,0). Poglejmo si najprej pot P₁. Prva pika na tej poti je (x, y) = (1,0). Od tu izračunamo ε₂ = p_x −k−1 = 1−0−1 = 0, torej je ε= (0,0). Druga pika je(x, y) = (2,0),od koder izračunamo ε= (1,1) in tretja pika (x, y) = (3,0), kjer dobimo ε= (2,2).

1 2 3 4

1 2

1 2 3 4

1

−1

1 2 3 4

−1

−2

Slika 21: Poti φ([P₁,(1,0),0]),φ([P₁,(2,0),0]) inφ([P₁,(3,0),0]).

Poglejmo si kam se preslika potP₂.Prva pika na tej poti je(x, y) = (1,0).Od tu izračunamo ε= (0,0). Druga pika je(x, y) = (2,0),kjer dobimo ε= (1,1)in tretja pika (x, y) = (4,0)z ε= (3,1).

1 2 3 4

1

−1 1 2 3 4

1

−1 1 2 3 4

−1 1

Slika 22: Potiφ([P₂,(1,0),0]), φ([P₂,(2,0),0]) in φ([P₂,(4,0),0]).

Poglejmo si sedaj kam se preslikata potiP₃inP₄. Na potiP₃je pika(x, y) = (1,0) z ε = (0,0). Na poti P₄ pa je prva pika (x, y) = (1,0) z ε = (0,0) in druga pika (x, y) = (2,0) zε= (1,1).

1 2 3 4

1

−1 1 2 3 4

1

−1 1 2 3 4

−1 1

Slika 23: Potiφ([P₃,(1,0),0]), φ([P₄,(1,0),0]) in φ([P₄,(2,0),0]).

Na poti P₅ je prva pika (x, y) = (1,0) z ε = (0,0) in druga pika (x, y) = (4,0) z ε = (3,1). Na poti P₆ pa je prva pika (x, y) = (1,0) z ε = (0,0) in druga pika (x, y) = (2,0) zε= (1,1).

1 2 3 4 1

−1 1 2 3 4

1

−1 1 2 3 4

1

−1 −1 1 2 3 4

1

Slika 24: Potiφ([P₅,(1,0),0]), φ([P₅,(4,0),0]), φ([P₆,(1,0),0]) in φ([P₆,(2,0),0]).

Na slikah 21, 22, 23 in 24 dobimo ravno vse poti od (0,0) do (4,0) s koraki U, D in2E, kar so ravno vse poti iz objekta 1 za n= 2. Torej bijekcija φpreslika poti iz objekta 6 v poti iz objekta 1.

3.3.2 Objekt 7

Tudi v tem primeru opazujemo drugi moment: dvignjene Schröderjeve poti od(0,0) do (2n+ 2,0) s koraki U = (1,1), D = (1,−1) in 2E = (2,0), kjer ima nezačetni korak U = (1,1) utež 2 in korak2E = (2,0) utež -1.

Delannoyevo številod_nje enako vsoti uteženih povprečij kvadratov višin točk v mreži po dvignjenih Schröderjevih poteh.

Primer 3.34. Poglejmo si primer za n = 2. Za boljšo preglednost bomo korake z utežjo 2 označili z modro, korake z utežjo -1 pa z zeleno barvo.

V prvem primeru imamo dve modri povezavi, vsota kvadratov višin pa je1 + 4 + 9 + 4 + 1 = 19, torej dobimo 2·2·19 = 76. Podobno izračunamo še ostale in dobimo:

76

5 + ⁵₅ +⁻¹⁶₅ + ⁴⁴₅ + ⁻¹⁶₅ + ⁻²⁸₅ = ⁶⁵₅ = 13, kar je enako kot d₂.

1 2 3 4 5 6 1

2 3

1 4

9 4 1

1 2 3 4 5 6 1

2 1

4 1 4 1

1 2 3 4 5 6 1

2

1 1 1 1 1

1 2 3 4 5 6 1

2 1

4 1 1 1

1 2 3 4 5 6 1

2

1 1 1

4 1

1 2 3 4 5 6 1

2 1

4 4 4 1

Slika 25: Dvignjene Schröderjeve poti od(0,0)do(6,0)s koraki oblike(1,1),(1,−1) in(2,0).

Podobno kot pri objektu 6 lahko tudi tu tvorimo bijekcijorazreži in zalepi, s katero iz poti iz objekta 7 dobimo poti iz objekta 3.

3.3.3 Objekt 8

Tudi pri tem objektu opazujemo drugi moment, in sicer dvignjene poti od(0,0)do (n+ 2,0)s korakiU = (1,1),D= (1,−1)inE = (1,0), kjer imajo nezačetni koraki U = (1,1)utež 2 in koraki E = (1,0)utež 3.

Delannoyevo število d_n je enako vsoti uteženih povprečij kvadratov višin točk v mreži.

Primer 3.35. Poglejmo si primer za n = 2. Za boljšo preglednost pobarvajmo nezačetne korake U = (1,1) z utežjo 2 z modro barvo, korake E = (1,0) z utežjo 3 pa z zeleno barvo. V prvem primeru dobimo 2·(1 + 4 + 1) = 12, v drugem pa 3·3·(1 + 1 + 1) = 27, skupaj torej ¹²₃ +²⁷₃ = 4 + 9 = 13,kar je enako d₂.

1 2 3 4

1 2

1 4

1

1 2 3 4

1 2

1 1 1

Slika 26: Dvignjene poti od (0,0) do (4,0) s koraki oblike (1,1), (1,−1) in (1,0)₃, kjer imajo nezačetni koraki oblike (1,1)utež 2.

Podobno kot pri objektu 6 lahko tudi tu tvorimo bijekcijo razreži in zalepi, s katero iz poti iz objekta 8 dobimo poti iz objekta 2.

3.4 Dvojni dvig

Dokaza objektov iz tega poglavja sta povzeta iz članka [7].

3.4.1 Objekt 9

Naj bo n ∈ N. V objektu 9 računamo vsoto uteži poti od (0,0) do (2n + 1,1) s koraki U = (1,1) in D = (1,−1), ki se začnejo s korakom U = (1,1) in kjer imajo vsa vmesna vozlišča na dvojnih vzponih utež 2. Vsota uteži takih poti je enaka Delannoyevemu številu d_n.

Definicija 3.36. Dvojni vzpon na poti je urejeno zaporedje korakov U U, kjer je U = (1,1).

Primer 3.37. Zan= 2 je vsota uteži poti enaka 1×4 + 1×1 + 4×2 = 13,kar je ravno enako Delannoyevemu številu d₂.

1 2 3 4 5 2

1 3

1 2 3 4 5 2

1

1 2 3 4 5 2

1

1 2 3 4 5 2

1

1 2 3 4 5 2

1

1 2 3 4 5

−1 1

Slika 27: Poti od (0,0) do (5,1) s koraki oblike (1,1) in (1,−1), ki se začnejo s korakom (1,1)in kjer imajo vmesna vozlišča na dvojnih vzponih utež 2.

Ta objekt bomo dokazali z bijekcijo poti iz objekta 4, prezrcaljenih čezx-os. Za dokaz zavrtimo poti za 45^◦, tako da iz koraka U = (1,1) dobimo korak N = (0,1), iz koraka D= (1,−1)pa korak E = (1,0).

Naj bo A₂(n) množica vseh takih poti od (0,−1) do (n, n) s koraki N = (0,1) in E = (1,0), ki, razen na prvem koraku, ostanejo šibko nad x-osjo (oziroma strogo nad premico y = −1). Bijekcija F : A^cc₂ (n) → A^l₂(n) iz dokaza trditve 3.54 (b) na strani 29 je ravno naša bijekcija.

3.4.2 Objekt 10

Naj bo n ∈ N. Število vseh poti od (0,0) do (n, n) s koraki oblike (k, l), kjer sta k, l ∈N∪ {0}, vendar ne oba hkrati 0, je enako 2ⁿ⁻¹·d_n.

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

1 2 1

2

Slika 28: Poti od(0,0)do(2,2)s koraki oblike(k, l), kjer stak, l ∈ {0,1,2}, vendar ne oba hkrati enaka 0.

Primer 3.38. Za n= 2 je 2²⁻¹d₂ = 2·13 = 26.

Uporabljamo korake(1,0), (2,0), (0,1), (0,2),(1,1),(1,2), (2,1)in (2,2).

Označimo z D(n) množico osnovnih Delannoyevih poti (torej veljadn=|D(n)|) in z E(n) množico poti od (0,0)do (n, n) s koraki iz množice N×N− {(0,0)}. Za dokaz objekta 10 torej moramo dokazati, da velja enakost |E(n)|= 2ⁿ⁻¹|D(n)|.

Pogledali si bomo 6 različnih množic dovoljenih korakov. Množice označimo s Si, kjer je i∈ {1, . . . ,6}. Definirajmo A_i(n) kot množico vseh poti od(0,−1)do(n, n) s koraki iz množice S_i, ki so, razen v začetni točki, strogo nad premico y = −1.

Definirajmo še Li(n) kot množico takih poti v Ai(n), ki so, razen v začetni točki, strogo nad premico y=x−1.

V množici korakov S1 = N×N je A1(n, k) množica poti v A1(n) s k koraki.

Analogno definiramo tudiL₁(n, k) kot množico poti v L₁(n) s k koraki.

Primer 3.39. MnožicaA₁(2,1)vsebuje samo eno pot, in sicer iz enega koraka oblike (2,3), torej A₁(2,1) ={(2,3)} in L₁(2,1) ={(2,3)}. Množica A₁(2,2) pa vsebuje

dva elementa: A₁(2,2) = {(1,1)(1,2),(1,2)(1,1)}, L₁(2,2) = {(1,2)(1,1)}, kar je ponazorjeno na sliki 29.

1 2

−1 0 1 2

1 2

−1 0 1 2

1 2

−1 0 1 2

Slika 29: Na prvi sliki je pot izA₁(2,1), na drugih dveh pa poti izA₁(2,2).Z modro barvo je označena premica y =x−1.

Trditev 3.40. Natanko ena izmed k cikličnih permutacij poljubne poti iz A₁(n, k) je v L₁(n, k).

Ideja dokaza je iz članka [6].

Dokaz. A₁(n, k)inL₁(n, k)sta poti od(0,−1)do(n, n)sk koraki iz množiceN×N. Namesto poti od (0,−1) do (n, n) opazujmo poti od (0,0) do (n,1). To dosežemo s transformacijo, kjer (x, y)preslikamo v(x,−x+y+ 1).Trdimo, da za vsako tako pridobljeno pot obstaja natanko ena ciklična permutacija, ki razen na začetku, leži strogo nad abscisno osjo.

1 2 3 4 5 6 7 8 9 10

−2

−1 0 1 2 3 4

1 2 3 4 5 6 7 8 9 10

−2

−1 0 1 2 3 4

Slika 30: Na levi sliki je primer poti od (0,0) do (10,1), kjer je z modro črtkano premico označena minimalna vrednost ordinate, z rdečo barvo pa zadnja točka poti na tej premici. Na desni sliki pa novo pridobljena pot z začetkom v rdeči točki s prve poti.

Do želene permutacije pridemo takole: Vzamemo točke, v katerih je dosežen mini- mum ordinate in med vsemi njimi izberemo zadnjo. S to točko začnemo. Ta pot bo ves čas nad abscisno osjo, saj se prvotna pot konča v točki z ordinato 1, torej bodo vse točke, ki so na prvotni poti levo od začetne točke, na novi poti za ena višje.

Pokazati moramo samo še, da nobena druga pot ne bo ves čas nad abscisno osjo.

Ločimo dve možnosti:

1. Če začnemo s točko, kjer ni dosežen minimum ordinate, bo točka z manjšo ordinato pod abscisno osjo.

2. Če začnemo z nezadnjo točko z minimumom ordinate, se naslednja točka z minimumo ordinate dotakne abscisne osi.

Torej res nobena druga pot ni ustrezna.

Trditev 3.41. Za 0< k≤n veljata naslednji enakosti:

(a) |A₁(n, k)|=(n−1 k−1

)( _n

k−1

) in (b) |L₁(n, k)|= ¹_k(n−1

k−1

)( n k−1

) = _n¹( n k−1

)(n k

).

Dokaz. (a) Za izračun moči množiceA₁(n, k)štejemo načine, kako lahko dodelimo koordinate končnih točk korakov na poti. Izbiramo k −1 koordinat končnih korakov, saj je končna točka zadnjega koraka določena s končno točko poti, torej z (n, n). Za izbor x-koordinate izbiramo med n−1 možnostmi, za izbor y-koordinate pa izmed n možnostmi.

(b) Iz trditve 3.40 velja, da je natanko ena izmed k cikličnih permutacij po- ljubne poti iz A₁(n, k) v L₁(n, k). Od tod pa sledi: |L₁(n, k)|= ¹_k|A₁(n, k)|=

1 k

(n−1 k−1

)( _n

k−1

).

Dokažimo še drugo enakost:

1 k

(n−1 k−1

)( n k−1

)

= (n−1)!n!·n

k(k−1)!(n−k)!(k−1)!(n−k+ 1)!·n =

= n!

k!(n−k)!· n!

(k−1)!(n−k+ 1)! · 1 n = 1

n ( n

k−1 )(n

k )

Množica korakov S2 ={N, E},kjer je N = (0,1) inE = (1,0).

Primer 3.42. Množica L₂(2) ima dva elementa: L₂(2) ={N N N EE, N N EN E}

1 2

−1 0 1 2

1 2

−1 0 1 2

Slika 31: Poti iz L₂(2), kjer je z modro barvo označena premica y=x−1.

Opazimo, da vsak korak (u, v)∈S₁ določa kombinacija navpičnega koraka (0, v) in vodoravnega koraka(u,0)v poljubnem vrstnem redu. Ker v množiciS₁ ni vodorav- nih in navpičnih korakov, je število korakov vA₁(n, k) enako številu desnih ovinkov v A₂(n, k). Od tod sledi enakost |A₁(n, k)| =|A₂(n, k)|, kjer je A₂(n, k) taka pod- množica A₂(n), kjer ima vsaka pot natanko k vrhov oziroma desnih ovinkov, torej zaporednih parov V H. Torej velja tudi |A₁(n)|=|A₂(n)| in |L₁(n)|=|L₂(n)|.

Definicija 3.43. Narayanovo število je definirano kot N(n, k) = _n¹( _n

k−1

)(_n

k

), n-ti Narayanov polinom paN_n(z) = ∑n

k=1 1 n

( _n

k−1

)(_n

k

)z^k za 1≤k ≤n.

Narayanova števila tvorijo trikotno zaporedje naravnih števil:

n\k 1 2 3 4 5

1 1

2 1 1

3 1 3 1

4 1 6 6 1

5 1 10 20 10 1

Tabela 2: Zaporedje Narayanovih števil za n, k ∈ {1,2,3,4,5}.

Vsotan-te vrstice Narayanovih števil je n-to Catalanovo število:

n

∑

k=1

N(n, k) =

n

∑

k=1 1 n

(_n

k

)( _n

k−1

)= _n+1¹ (_2n

n

) =C_n. Narayanovo število N(n, k) prešteje Dyckove poti reda n s k vrhovi.

Opazimo, da je Narayanovo število enako moči množice L₂(n, k), torej N(n, k) =

|L2(n, k)|.

V vsaki poti iz L₂(n) pobarvamo vrhove neodvisno z z različnimi barvami, kjer je z poljubno naravno število. V primeru, da je z ≥ 2, zahtevamo, da je ena barva modra (oznaka: m) in ena barva rdeča (r). Množico vseh takih poti s pobarvanimi vrhovi označimo z L^c₂(n;z).

Primer 3.44. Primeru iz slike 31 pobarvamo vrhove z modro oziroma rdečo barvo:

L^c₂(2; 2) ={N N N mEE, N N N rEE, N N mEN mE, N N mEN rE, N N rEN mE, N N rEN rE}

Trditev 3.45. Velja |L^c₂(n;z)|=Nn(z).

Dokaz. Velja N_n(z) = ∑n k=1

1 n

( _n

k−1

)(_n

k

)z^k = ∑n

k=1|L₂(n, k)|z^k = |L^c₂(n;z)|, saj imamo v množici L^c₂(n;z)za vsakega izmed k vrhov z možnih barv.

Definicija 3.46. Sredinsko vozlišče zaporednih korakovN N imenujemodvojni dvig.

Sredinsko vozlišče zaporednih korakov EE imenujemo dvojni spust.

Definirajmo množicoL^cc₂ (n;z)kot množico poti izL₂(n), kjer zz različnimi barvami neodvisno pobarvamo vse dvojne dvige.

Primer 3.47. Primeru iz slike 31 pobarvamo dvojne dvige z modro oziroma rdečo barvo: L^cc₂ (2; 2) ={N mN mN EE, N mN rN EE, N rN mN EE, N rN rN EE,

N mN EN E, N rN EN E}.

Definirajmo bijekcijo f :L^cc₂(n;z)→L^c₂(n;z) takole:

Naj bo R iz L^cc₂ (n;z) določena s koordinatami vrhov oziroma desnih ovinkov, torej s koordinatami vozlišč med zaporednima korakoma N in E: (x₁, y₁), . . . ,(x_k, y_k).