Liczby catalana
ksiądz: kolejność mnożenia − liczby Catalana
Mamy n−liczb (n≥3) różnych od zera : c1,c2,c3,c4...cn. Na ile sposobów można wstawić (n−2)
par nawiasów określających jednoznacznie kolejniość mnożenia?
an− liczba tych sposobów
Podać wzór rekurencyjny na an
przyjąć że gdy n=1 to a1 =1
n=2 to a2=1
zrobiłem że dla
n=3 ; n−2=1 a3=2
n=4 ; n−2=2 a4=3
ale nie jestem pewny czy dobrze wyliczyłem te spooby dla n=3 i n=4
w ogóle te zadanie jest dla mnie trudne więc proszę o pomoc
30 maj 22:15
ksiądz: pomoże ktoś
?
30 maj 22:43
ksiądz: pomocy
30 maj 23:59
31 maj 00:09
Artur z miasta Neptuna:
dla n=3
(ab)c
a(bc)
dla n=4
(ab)(cd)
(a(bc))d
a((bc)d)
a(b(cd))
dla n=5
((ab)(cd))e
a((bc)(de))
(ab)(c(de))
((ab)c)(de)
(ab)((cd)e)
(a(bc))(de)
31 maj 00:10
Artur z miasta Neptuna:
natomiast ... aby to pasowało do liczb Catalana należałoby nie wykluczać opcji np.:
dla n=4
a((bc))d
dla n=5
((ab))(cd)e
(ab)c((de))
itd.
31 maj 00:14
Artur z miasta Neptuna:
jednak powstaje wtedy problem ... dlaczego wykluczona została opcja, np.:
dla n=3
a(b)c
dla n=4
(ab)c(d)
itd.
bo skoro ((ab)c) ≠ ((ab))c to także (ab)(c) ≠ ((ab)c)
31 maj 00:18
ksiądz: no właśnie też to zauważyłem i zgłaszam się z tym problemem tu ale podobno wzór rekurencyjny
istnieje.
Gościu powiedział nam że dla n=3 są 2 kombinacje a dla n=4 są 3 kombinacje więc nie wiem jak
on te nawiasy sobie wyobraża .
Ale nie jestem pewny czy ten napis liczby Catalana był na pewno do tego przykładu...
31 maj 00:31
Artur z miasta Neptuna:
skoro dla n=3 są 2 kombinacje ... to nawiasy muszą 'zawierać' minimum dwa elementy (czyli
problem 00:18 rozwiązany)
skoro dla n=4 są 3 kombinacje ... to za chuja to nie wychodzi
bo jest ich 5
(ab)(cd)
((ab)c)d
(a(bc))d
a((bc)d)
a(b(cd))
dla n=5 wszystkie (chyba) możliwości:
1. ((ab)(cd))e
2. a((bc)(de))
3. (ab)(c(de))
4. ((ab)c)(de)
5. (ab)((cd)e)
6. (a(bc))(de)
7. (a(b(cd))e
8. (a((bc)d)e
9. (((ab)c)d)e
10. ((a(bc))d)e
11. a(((bc)d)e)
12. a((b(cd))e)
13. a(b(c(de)))
14. a(b((cd)e))
natomiast wykazanie, że są to liczby Catalana to już inna kara kaloszy
31 maj 00:43
ksiądz: no to nie wiem ... zostawie to w pizdu
31 maj 00:50