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
108
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
Ja taas ammuttu kokkolassa
Kokkolaisilta pitäisi kerätä pois kaikki ampumaset, keittiöveitset ja kaikki mikä vähänkään paukku ja on terävä.575489- 934337
Helena Koivu on äiti
Mitä hyötyä on Mikko Koivulla kohdella LASTENSA äitiä huonosti . Vie lapset tutuista ympyröistä pois . Lasten kodista.3752584Ovatko naiset lopettaneet sen vähäisenkin vaivannäön Tinderissa?
Meinaan vaan profiileja selatessa nykyään valtaosalla ei ole minkäänlaista kirjoitettua tekstiä siellä. Juuri ja juuri s721111Suomi vietiin Natoon väärin perustein. Viides artikla on hölynpölyä. Yksin jäämme.
Kuka vielä uskoo, että viides artikla takaa Suomelle avun, jos Suomeen hyökätään. Liikuttavasti täällä on uskottu ja ved3301038- 61853
Sydämeni on sinun luona
Koko ajan. Oli ympärilläni ketä oli niin sinä olet vain ajatuksissa ja tunteissa. En halua muiden kosketusta kuin sinun46826- 28823
Trump ja Venäjä
Huomasitteko muuten... Käytännössä ainoat valtiot, joille Trump EI eilen asettanut typeriä tariffejaan, olivat Venäjä ja102789Jatkuva stressitila
On sinun vuoksesi kun en tiedä missä mennään mutta tunteeni tiedän ainoastaan52779