+ All Categories
Home > Documents > Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II...

Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II...

Date post: 26-Jul-2020
Category:
Upload: others
View: 6 times
Download: 0 times
Share this document with a friend
27
Probleme de numărare Drd. Iulia – Cătălina Pleșca Universitatea "Alexandru Ioan Cuza" din Iași 16.01.2017
Transcript
Page 1: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Probleme de numărare

Drd. Iulia – Cătălina Pleșca

Universitatea "Alexandru Ioan Cuza" din Iași

16.01.2017

Page 2: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Drumurile maimuței - I

Câte drumuri are maimuța până în vârful copacului?

1

1 1

1 1 1 1

20

21

22

16.01.2017 Iulia - Cătălina Pleșca 2

Page 3: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Drumurile maimuței - II

Câte drumuri are maimuța până în vârful copacului?

1

1 1

1 2 1

20

21

22

16.01.2017 Iulia - Cătălina Pleșca 3

Page 4: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Câte rezultate diferite obținem la aruncarea de două ori a unei monede (ținând cont de ordine)?

pajură - pajură cap - pajură

20

21

22

16.01.2017 Iulia - Cătălina Pleșca 4

Aruncarea unei monede - I

cap pajură

cap - cap pajură - cap

Page 5: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Cu ce probabilitate obținem fiecare rezultat la aruncarea de două ori unei (neținând cont de ordinea aruncărilor)?

1c – 1p (2)

prima aruncare

a doua aruncare

16.01.2017 Iulia - Cătălina Pleșca 5

Aruncarea unei monede - II

1c 1p

2c (1) 2p (1)

Page 6: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

21

23

16.01.2017 Iulia - Cătălina Pleșca 6

Drumurile maimuței - III

22

24

Triunghiul lui Pascal

1 1

1

1

1

1

1

2

1 1

3 3

4 6 4

Page 7: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Drumuri între case - I

16.01.2017 Iulia - Cătălina Pleșca 7

Câte drumuri există de la casa galbenă la casa albastră mergând doar în sus pe drumuri? 1

1

1

1

1

1

1

1

1

2

3 3

4 4 6

5 10 10

20 15 15

5

35 35

70 =84

Page 8: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Drumuri între case - II

16.01.2017 Iulia - Cătălina Pleșca 8

Câte drumuri există de la casa galbenă la casa albastră mergând doar în sus pe drumuri? 1

1

1 1

1

1 2

3

4 6

10=3 + 23

3

𝑚+ 𝑛𝑛=𝑚 + 𝑛 − 1𝑛

+𝑚 + 𝑛 − 1𝑛 − 1

Drumuri laticeale NE

Page 9: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Coeficienții binomiali

• Un drum poate fi codificat ca un cuvânt de lungime 5 cu caracterele “c” și “p” în care “p” apare de 3 ori.

• Pentru a determina un cuvânt este suficient să alegem pozițiile pe care “p” apare, indiferent de

ordinea lor: 5!

3!2!.

1 + 𝑥 𝑛 = 𝑛

𝑘𝑥𝑘

𝑛

𝑘=0

16.01.2017 Iulia - Cătălina Pleșca 9

Page 10: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Drumuri în grafuri - I

Considerăm graful anterior

16.01.2017 Iulia - Cătălina Pleșca 10

1

2

3

4

5

6 8

9

7

12 11

10

și matricea sa de adiacență

0 1 0 1 0 0 0 0 0 0 0 0

1 0 1 0 1 0 0 0 0 0 0 0

0 1 0 0 0 1 0 0 0 0 0 0

1 0 0 0 1 0 1 0 0 0 0 0

0 1 0 1 0 1 0 1 0 0 0 0

0 0 1 0 1 0 0 0 1 0 0 0

0 0 0 1 0 0 0 1 0 1 0 0

0 0 0 0 1 0 1 0 1 0 1 0

0 0 0 0 0 1 0 1 0 0 0 1

0 0 0 0 0 0 1 0 0 0 1 0

0 0 0 0 0 0 0 1 0 1 0 1

0 0 0 0 0 0 0 0 1 0 1 0

G

𝐴 =

Page 11: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Deoarece drumurile dintre cele două case văzute ca drumuri în graful G de la nodul 1 la nodul 12 sunt toate drumurile de lungime 5, putem calcula numărul lor folosind puterea a cincea a matricei de adiacență.

16.01.2017 Iulia - Cătălina Pleșca 11

𝐴5 =

0 34 0 35 0 30 0 35 0 13 0 10

34 0 34 0 65 0 35 0 35 0 23 0

0 34 0 30 0 35 0 35 0 10 0 13

35 0 30 0 69 0 48 0 40 0 35 0

0 65 0 69 0 69 0 88 0 35 0 35

30 0 35 0 69 0 40 0 48 0 35 0

0 35 0 48 0 40 0 69 0 35 0 30

35 0 35 0 88 0 69 0 69 0 65 0

0 35 0 40 0 48 0 69 0 30 0 35

13 0 10 0 35 0 35 0 30 0 34 0

0 23 0 35 0 35 0 65 0 34 0 34

10 0 13 0 35 0 30 0 35 0 34 0

Page 12: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Drumuri în grafuri - II Numărarea drumurilor în grafuri pornește de la o problemă relativ diferită: problema podurilor din Königsberg rezolvată de Euler în 1736: având graful de mai jos, trebuie să numărăm ciclurile sale euleriene, i.e. drumurile care parcurg fiecare muchie exact o dată.

16.01.2017 Iulia - Cătălina Pleșca 12

Problema nu are soluție.

Page 13: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Drumuri în grafuri - II

Problema găsirii numărului de drumuri într-un graf oarecare este complicată (de tip #P).

Variante mai simple ale problemei sunt găsirea drumurilor minimale și maximale (în grafuri aciclice).

16.01.2017 Iulia - Cătălina Pleșca 13

Page 14: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Identități combinatoriale 2𝑛

𝑛=

𝑛

𝑘

2𝑛

𝑘=0

16.01.2017 Iulia - Cătălina Pleșca 14

Fiecare drum laticeal NE intersectează un singur punct de pe diagonală.

Termenul 𝑛𝑘

2 dă numărul

drumurilor laticeale NE care trec prin punctul k.

Page 15: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Drumuri între case - III

16.01.2017 Iulia - Cătălina Pleșca 15

Câte drumuri există de la casa galbenă la casa albastră mergând doar în sus pe drumuri și netrecând de linia neagră?

1

1

1

1

1

1

2

3 2

5

5 9

4

14

𝐶4 =14

Page 16: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Numere Catalan - I Pentru a calcula numerele Catalan, considerăm inițial toate drumurile între case. Definim excesul unui drum ca numărul de muchii la dreapta în stânga diagonalei. Pentru drumul din figură excesul este 3.

16.01.2017 Iulia - Cătălina Pleșca 16

Fiecare drum cu exces 𝑒 > 0 poate fi pus în bijecție cu un drum cu exces 𝑒 − 1.

Page 17: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

• Identificăm prima porțiune care depășește diagonala și marcăm muchia ei finală de pe diagonală și apoi schimbăm ordinea celor două porțiuni de drum din jurul său.

• Singura muchie spre dreapta care își schimbă poziția față de diagonală este cea albastră.

• Transformarea este reversibilă.

16.01.2017 Iulia - Cătălina Pleșca 17

Cele 𝑛 + 1 mulțimi cu excese 0,1,⋯ , 𝑛 − 1 au

același cardinal 1

𝑛+1

2𝑛𝑛

.

Page 18: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Numere Catalan - II Numărul de drumuri Dick de lungime 2n, i.e. drumuri laticeale de la (0,0) la (0,2𝑛) cu pași de forma (1,1) sau (1, −1) fără a coborî sub axa 𝑂𝑋.

Obținem numerele Catalan înlocuind pașii (1,1) cu pași la dreapta și pașii (1, −1) cu pași la stânga.

16.01.2017 Iulia - Cătălina Pleșca 18

Page 19: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Numere Catalan - III

• Numărul de șiruri de tip ballot de lungime 2𝑛, i.e. șiruri de 𝑛 de +1 și 𝑛 de −1 astfel încât sumele parțiale sunt nenegative.

• Problema voturilor lui Bertrand

Având 2 candidați: A și B care obțin în final același număr de voturi, care este probabilitatea ca la numărarea voturilor A să nu fie niciodată depășit de B?

16.01.2017 Iulia - Cătălina Pleșca 19

Page 20: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Corespondența: pentru +1 mergem la dreapta și pentru -1 la stânga. Fiecare drum de la casa galbenă la casa albastră are 𝑛 muchii dreapta și 𝑛 muchii stânga. Condiția ca sumele parțiale să fie pozitive este echivalentă cu condiția ca drumurile să nu treacă de diagonală.

16.01.2017 Iulia - Cătălina Pleșca 20

Page 21: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Numere Catalan - IV

• Numărul de parantezări cu 𝑛 paranteze ale unui șir de 𝑛 + 1 elemente compuse cu o operație binară neasociativă.

• Exemplu pentru șiruri de lungime 4: x(x(xx)), x((xx)x), (xx)(xx), (x(xx))x, ((xx)x)x.

16.01.2017 Iulia - Cătălina Pleșca 21

Page 22: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Drumuri între case - IV

16.01.2017 Iulia - Cătălina Pleșca 22

Câte drumuri există de la casa galbenă la casa albastră mergând doar în sus (inclusiv pe diagonalele pătratelor) pe drumuri?

1

1

1 1

1

1 3

5 5

7 13

25 = 𝐷(2,3)

Page 23: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Numere Delannoy • Evident D a, b = 𝐷 𝑎 − 1, 𝑏 + 𝐷 𝑎, 𝑏 − 1 + 𝐷 𝑎 − 1, 𝑏 − 1 și 𝐷(0, 𝑏) = 𝐷(𝑎, 0) = 1.

• Vom studia drumurile după numărul de muchii diagonale pe care le conțin. Pentru i muchii diagonale, trebuie să avem 𝑎 − 𝑖 muchii la stânga 𝑏 − 𝑖 muchii la dreapta pentru a ajunge în punctul (𝑎, 𝑏). Acești pași pot fi făcuți în orice ordine, deci numărul acestor drumuri este coeficientul multinomial

𝑎 + 𝑏 − 𝑖𝑖, 𝑎 − 𝑖, 𝑏 − 𝑖

=𝑎 + 𝑏 − 𝑖𝑎

𝑎𝑖.

• Expresia pentru numere Delannoy devine

𝐷 𝑎 , 𝑏 = 𝑎 + 𝑏 − 𝑖𝑎

𝑎𝑖.

min (𝑎,𝑏)

𝑖=0

16.01.2017 Iulia - Cătălina Pleșca 23

Page 24: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Drumuri între case - III

16.01.2017 Iulia - Cătălina Pleșca 24

Câte drumuri există de la casa galbenă la casa albastră mergând doar în sus pe drumuri și diagonale și netrecând de linia neagră?

1

1

1

1

1

2

4

6 6

16

22 32

8

70

92

Page 25: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Numere Schröder

Numerele Schröder au aceeași relație cu numerele Delannoy ca numerele Catalan cu coeficienții binomiali.

Formula lor explicită este:

𝑠𝑛 =1

𝑛+1 𝑛𝑖𝑛 + 𝑖𝑖

𝑛𝑖=0 .

16.01.2017 Iulia - Cătălina Pleșca 25

Page 26: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Deblocarea unui telefon Android Care este numărul de coduri de deblocare a unui telefon Android?

Reguli:

• drumurile au orientare

• nu se poate trece de două ori prin același vârf

• lungimea unui drum este minim 4

• dacă două vârfuri care nu sunt incidente au vârful dintre ele folosit deja în drum, atunci ele devin incidente.

16.01.2017 Iulia - Cătălina Pleșca 26

Răspuns: 389112.

Page 27: Probleme de numărare€¦ · 3 3 4 6 5 10 10 15 20 15 5 35 35 70= 8 4. Drumuri între case - II 16.01.2017 Iulia - Cătălina Pleșca 8 Câte drumuri există de la casa galbenă

Bibliografie

• Adam J. Aviv, Katherine Gibson, Evan Mossop, Matt Blaze, and Jonathan M. Smith (2010). “Smudge Attacks on Smartphone Touch Screens”

• Philippe Boulanger (1998). “Suntem cei mai tari la mate!”. Compania.

• Josef Rukavicka (2011). “On Generalized Dyck Paths”, Electronic Journal of Combinatorics

• Richard P. Stanley (2015). “Catalan Numbers”. Cambridge University Press.

• Leslie G. Valiant (1979). "The Complexity of Computing the Permanent". Theoretical Computer Science. Elsevier. 8 (2): 189–201.

16.01.2017 Iulia - Cătălina Pleșca 27


Recommended