Linkki: https://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics
Ensimmäinen: "hyvät sulutukset", esim. tapauksessa n=3 nämä
((())), ()(()), ()()(), (())(), (()())
Toinen: Tavat suluttaa n 1:n muuttujan (assosiatiivinen) tulo eri tavoin esim n=3:
((ab)c)d, (a(bc))d, (ab)(cd), a((bc)d), a(b(cd))
Kysymys: Näiden välillä on ilmeisesti bijektio, joka menee toisesta ensimmäiseen näin:
-Lisätään uloimmat sulut.
-Poistetaan '('-merkit ja muuttujat.
-Korvataan kertomerkit (jollainen jokaiseen kohtaan "xy", "x(" ja ")x" tulee) merkeillä '('.
[Tulevat tällä tavoin eri järjestyksessä kuin Wikipediassa, poistettaneenko siellä ensin oikeat sulut, tämä algoritmi on täältä: https://math.stackexchange.com/a/1630837/682031]
Kuinka tämän käänteinen koodataan eli mennään hyvästä sulutuksesta (jossa siis ei muuttujia) sellaiseen jossa muuttujat on mukana eli tulon assosiasointiin?
Esim.
a((bc)d) --> (a*((b*c)*d)) --> **)*)) --> (()())
.
Mutta kuinka mennään
(()()) --> **)*)) --> ?
Catalanin lukujen kombinatoriset applikaatiot
1
187
Vastaukset
Mielenkiintoinen kysymys! Kirjoitit oikeaan paikkaan, tältä palstalta löytyy tunnetusti Suomen parasta asiantuntemusta tietotekniikan alalta mitä sotiin tulee.
Minäkin kirjoitan tässä mutua, joka lienee suomenkielen vastine sanalle proof.
Esittämiesi kahden notaation välillä on bijektio, kuten arvelit. Ensimmäinen notaatio on sama kuin postfix, toinen on tietenkin infix. Muunnoksiin notaatioiden välillä on hyvin tunnetut algoritmit, jotka käyttävät pinoa.
Tekemäsi literaalimuunnos on erikoinen. Jos se toimii kaikilla n arvoilla, tilanteeseen sopinee lainata Saulin amerikkalaisen kollegan kaiman sanoja: "The resulting formula is properly parenthesized, believe it or not."
Literaalimuunnos toiseen suuntaan ei käy yhtä vaivattomasti, kuten varsinkin näistä esimerkeistä ilmenee:
(())() --> (a(bc))d
(()()) --> a((bc)d)
Ketjusta on poistettu 0 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
6 kW saunan lämmityksestä kohta 10 euron lisämaksu / kerta
Kokoomuslainen sähköyhtiöiden hallitsema Energiavirasto ehdottaa 5 kW:n rajaa, jonka ylittämisestä tulee lisämaksu. Tark984826Kun väestö ikääntyy ja veronmaksajat vähenee, mitä sitten vasemmistolaiset?
Maahanmuutto ei vaan ole ratkaisu väestön ikääntymiseen. Maahanmuutto lykkää ja hidastaa väestön ikääntymistä ja työv2074658"Mitä sä nainen tuot sitten pöytään" ?
Jos mies provaidaa ja suojelee... Pitääkö miesten kysyä tuollaisia?1173134Ekologinen kommunismi tulee voittamaan fossiilikapitalismin
Kiina on mahtitekijä uusiutuvien energialähteiden kehityksessä, ja Trump osoitus viimeisestä öljyn perään itkemisestä, m243107Minja jytkyttää vas.liiton kannatusta ylöspäin
Alkaa raavaat duunarimiehetkin palaamaan vasemmistoliiton kannattajiksi. Eduskunnassahan on vain kaksi työntekijöiden p983023Mahonselän jäät - Saaristokunta Lieksa brutaalisti kriisin partaalla!
Lieksan loppuvuoden hyvän kehityksen jälkeen ei olisi uskonut että palstan ahkerista kommentoijista huolimatta matkailu1382298- 922251
Oikeistopuolueiden kannatus vain 37,8 %, vasemmiston 43,0 %
Keskustaan jää 17,4 prosenttia ja loput ovat sitten mitä ovat. Mutta selvästikin Suomen kansa on vasemmalle kallellaan.342203- 222148
Mies, kerro minulle vielä jotakin aivan uniikkia
ja ainutlaatuista minkä vain me kaksi voisimme ymmärtää jos olemme sen kokeneet ja eläneet, jotta ihan varmasti tietäisi392105