De la zidul de cǎrǎmidǎ la şirul luiFibonacci

Leonard Dǎuş

Bucuresti, 23 noiembrie 2017

Cuprins:

• Drumuri laticeale “clasice” si aplicatiile lor

• Drumuri de tip “brick wall”

• Siruri remarcabile obtinute prin numararea drumurilor de tip “brick wall”

• Aplicatii la fiabilitatea retelelor de tip “brick wall”

• Probleme deschise - Proprietati ale polinoamelor de fiabilitate

• Referinte bibliografice

Drumuri laticeale “clasice” si aplicatiile lor

• In ℤ2 un drum laticeal (de lungime k) cu pasi in S este o secventa de puncte

𝑣0, 𝑣1, … , 𝑣𝑘 ∈ ℤ2 astfel incat fiecare diferenta consecutiva 𝑣𝑖+1 − 𝑣𝑖 ∈ 𝑆.

Drum laticeal de lungime 5 cu pasi in 𝑆 = 1,1 , 2,0 , 0, −1

• Drum laticeal Nord-Est (NE) este un drum laticeal cu pasi in 𝑆 = 1,0 , 0,1

• Daca 𝑚, 𝑛 ∈ ℕ, numarul drumurilor laticeale NE ce unesc 𝑂(0,0) si 𝐵(𝑚, 𝑛) este 𝐶𝑚+𝑛

𝑚 .

• Ecuatia

𝑥1 + 𝑥2 +⋯+ 𝑥𝑛 = 𝑚

are exact 𝐶𝑚+𝑛𝑚 solutii natural.

N

E

ENENNEENENEE

• Drumuri laticeale Dyck sunt drumuri cu pasi in 𝑆 = 1,0 , 0,1 , ce unesc

𝑂(0,0) si 𝑃(𝑛, 𝑛) si care nu trec sub dreapta 𝑂𝑃.

• Numarul drumurilor laticeale Dyck ce unesc 𝑂(0,0) si 𝑃(𝑛, 𝑛) este1

𝑛+1𝐶2𝑛𝑛 = 𝐶𝑛 - numarul lui Catalan

1, 2, 5, 14, 42, 132, 429, 1430, 4862

Eugène Charles Catalan(1814 – 1894)

• Numarul drumurilor laticeale Dyck (numarul lui Catalan 𝐶𝑛) apare ca

solutie a unor probleme diverse de numarare:

1. Numarul de moduri diferite in care un poligon convex cu 𝑛 + 2

laturi se descompune in triunghiuri folosind diagonale care nu se

intersecteaza

𝑛 = 4

2. Numarul sirurilor

1 ≤ 𝑎1 ≤ 𝑎2 ≤ ⋯ ≤ 𝑎𝑛

de 𝑛 numere intregi cu 𝑎𝑖 ≤ 𝑖.

3. Numarul arborilor binari totali avand 𝑛 varfuri cu descendenti

4. Numarul de moduri in care se poate scrie asociativiatea unei

operatii binare aplicata de 𝑛 ori

((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd))

Drumuri de tip “brick wall”

O

9

12

• Drum laticeal brick wall este un drum laticeal cu pasi in 𝑆 = 1,0 , 0,1 𝑖 , 0, −1 𝑝

sau in 𝑆 = 1,0 , 0,1 𝑝, 0, −1 𝑖

1

2

3

3 7

6

10

23

19

O

𝐵(𝑙, 𝑤)

7

10

13

13

10

23

19

• Caz I: 𝑤 numar par

• trecerea de la o coloana impara la o coloana para se face cu

transformarea liniara

𝑇𝐿: ℝ𝑤+1 → ℝ𝑤+1, 𝑇𝐿 𝑥1, 𝑥2, … , 𝑥𝑤,𝑥𝑤+1 =

(𝑥1, 𝑥2 + 𝑥3, 𝑥2 + 𝑥3, … , 𝑥𝑤 + 𝑥𝑤+1, 𝑥𝑤 + 𝑥𝑤+1)

𝑀𝐿𝐶2𝑘−1 = 𝐶2𝑘

• trecerea de la o coloana para la o coloana impara se face cu

transformarea liniara

𝑇𝑈: ℝ𝑤+1 → ℝ𝑤+1, 𝑇𝑈 𝑥1, 𝑥2, … , 𝑥𝑤,𝑥𝑤+1 =

(𝑥1 + 𝑥2, 𝑥1 + 𝑥2, … , 𝑥𝑤−1 + 𝑥𝑤 , 𝑥𝑤−1 + 𝑥𝑤 , 𝑥𝑤+1)

𝑀𝑈𝐶2𝑘 = 𝐶2𝑘+1

• Teorema: Componentele coloanei 𝐶𝑙+1 sunt date de

𝐶𝑙+1 = 𝑀𝑈𝑀𝐿

𝜆𝐶1, daca 𝑙 impar

𝑀𝐿 𝑀𝑈𝑀𝐿𝜆𝐶1, daca 𝑙 impar

unde 𝜆 =𝑙−1

2.

Siruri remarcabile obtinute prin numararea drumurilorde tip “brick wall”

2

8

O

3

3

3

5

5

8

5

8

13

13

3 5 8 13 21 34

21

13

21 21

34

34

55 89

W=2: Sirul lui Fibonacci

• Matricele 𝑀𝐿 si 𝑀𝑈 devin:

𝑀𝐿 =1 0 00 1 10 1 1

, 𝑀𝑈 =1 1 01 1 00 0 1

⇒ 𝑀𝑈𝑀𝐿 =1 1 01 1 11 1 1

=𝐹1 𝐹1 𝐹0𝐹2 𝐹2 𝐹1𝐹2 𝐹2 𝐹1

Daca notam 𝐹 =𝐹1 𝐹1 𝐹0𝐹2 𝐹2 𝐹1𝐹2 𝐹2 𝐹1

, atunci 𝐹𝑛 =

𝐹2𝑛−1 𝐹2𝑛−1 𝐹2𝑛−2𝐹2𝑛 𝐹2𝑛 𝐹2𝑛−1𝐹2𝑛 𝐹2𝑛 𝐹2𝑛−1

Observatie: In 1955 Brenner a introdus o matrice legata de sirul lui

Fibonacci: 𝑄 =𝐹2 𝐹1𝐹1 𝐹0

Matricea 𝐹 =𝐹1 𝐹1 𝐹0𝐹2 𝐹2 𝐹1𝐹2 𝐹2 𝐹1

utilizata anterior are valorile proprii 0, 𝜑2 si

𝜑−2.

Teorema: Numarul drumurilor laticeale brick wall ce unesc 𝑂(0,0) si 𝐴(𝑙, 2)este 𝐹

2𝑙

2+3

.

• W=3:

Aplicatii la fiabilitatea retelelor de tip “brick wall”

• 𝑙 length of a network 𝑁, i.e., the length of a minimal path between 𝑆and 𝑇;

• 𝑤 width of a network 𝑁, i.e., the size of a minimal cut disconnecting 𝑆and 𝑇;

• 𝑝 probability that the device (e.g., relay, switch, transistor, etc.) is closed;

• 𝑞 probability that the device (e.g., relay, switch, transistor, etc.) is open, 𝑞 = 1 − 𝑝;

• ℎ(𝑝) reliability polynomial as a function of 𝑝, i.e., the probability that a network 𝑁 is closed;

𝑆 𝑇

In [3] Maxwell mentions several forms for ℎ 𝑝 , the two most commonones being

ℎ 𝑝 = 𝑘=0𝑛 𝐴𝑘𝑝

𝑘 (2)

ℎ 𝑝 = 𝑓 𝑝, 𝑞 = 𝑘=𝑙𝑤𝑙 𝐵𝑘𝑝

𝑘𝑞𝑤𝑙−𝑘 (3)

where, as we recall, 𝑞 = 1 − 𝑝.

𝐵𝑘 is the number of ways one can select a subset of 𝑘 contacts in thenetwork 𝑁 such that if these 𝑘 contacts are closed and the remaining 𝑛 − 𝑘contacts are open, then the network 𝑁 will be closed.

• Conjectura 1: Daca 𝑙 = 𝑤 = 2𝑘, atunci exista doua retele de tip “brick wall” de dimensiune (2𝑘, 2𝑘), iar polinoamele lor de fiabilitate satisfac relatia

𝐻2𝑘,2𝑘 1 − 𝑝 = 1 − 𝐻2𝑘,2𝑘+ (𝑝),

pentru orice 𝑝 ∈ [0,1].

𝐻2,2 𝑝 = 1 − 1 − 𝑝 2 2

= 𝑝4 − 4𝑝3+4𝑝2

Probleme deschise - Proprietati ale polinoamelor de fiabilitate

• Corolar: Graficele polinoamelor de fiabilitate𝐻2𝑘,2𝑘 si 𝐻2𝑘,2𝑘+ sunt

simetrice unul fata de celalalt in raport cu punctul1

2,1

2

(sau, echivalent, graficul lui 𝐻2𝑘,2𝑘+ se poate obtine din graficul lui 𝐻2𝑘,2𝑘

printr-o rotatie de unghi 𝜋 in jurul punctului1

2,1

2).

𝐻3,3 𝑝 = 8𝑝3 − 6𝑝4 − 6𝑝5 + 12𝑝7 −9𝑝8 +2𝑝9

• Conjectura 2: Daca 𝑙 = 𝑤 = 2𝑘 + 1 , atunci graficul polinomului de

fiabilitate 𝐻2𝑘+1,2𝑘+1 𝑝 este simetric fata de punctul1

2,1

2.

• Corolar: Pentru orice 𝑘 ∈ Ν, unicul punct fix din intervalul 0,1 al

polinomului de fiabilitate 𝐻2𝑘+1,2𝑘+1 𝑝 este 𝑝 =1

2.

𝐻2,3 𝑝 = 1 − 1 − 𝑝2 2 1 − 1 − 𝑝 2 𝐻3,2 𝑝 =1 − 1 − 1 − 1 − 𝑝2 2 1 − 𝑝2

• Conjectura 3: Daca 𝑙 ≠ 𝑤, atunci intre polinomul de fiabilitate 𝐻𝑙,𝑤 al

retelei (𝑙, 𝑤) si polinomul de fiabilitate 𝐻𝑙,𝑤 al retelei (𝑤, 𝑙) exista relatia

𝐻𝑙,𝑤 1 − 𝑝 = 1 − 𝐻𝑤,𝑙(𝑝),

pentru orice 𝑝 ∈ [0,1].

• Corolar: Pentru orice 𝑙 ≠ 𝑤, graficul polinoamelor 𝐻𝑙,𝑤 si 𝐻𝑤,𝑙 sunt

simetrice unul fata de celalalt in raport cu punctul1

2,1

2

(sau, echivalent, graficul lui𝐻𝑙,𝑤 se poate obtine din graficul lui𝐻𝑤,𝑙 printr-o

rotatie de unghi 𝜋 in jurul punctului1

2,1

2).

References

[1] E. F. Moore, and C. E. Shannon, “Reliable circuits using less reliable relays – Part I,” J. Frankl. Inst., vol. 262, no. 3, pp. 191–208, Sept. 1956. http://dx.doi.org/10.1016/0016-0032(56)90559-2

[2] L. M. Maxwell, “Synthesis of contact networks from prescribed reliability functions,” J. Franklin Inst., vol. 281, no. 3, pp. 214–234, Mar. 1966. http://dx.doi.org/10.1016/0016-0032(66)90019-6

[3] S. R. Cowell, V. Beiu, L. Dăuş, and P. Poulin, “On the Exact Reliability Enhancements of Small Hammock Networks”, submitted to IEEE Trans. on Reliability

[4] L. Dăuş, V. Beiu, S. R. Cowell, and P. Poulin, “Brick wall lattice paths”, in progress

[5] K. Humphreys, “A history and a survey of lattice path enumeration”, Journal of Statistical Planning and Inference 140 (2010), 2237-2254

[6] The On-Line Encyclopedia of Integer Sequences: https://oeis.org/