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
221
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
- 1121226
Sinkkumiehet hukkaavat tärkeän ässän hihastaan kun
...eivät suostu kavereiksi naisten kanssa. Mikä voi olla heillä syynä? Hyväksyvät vain naisen, joka suorastaan anelee sa1201101- 138993
- 96812
"Kaikkien miesten asia" - kampanja on alkanut
Miehillä on naisiin kohdistuvan väkivallan lopettamisessa merkittävä rooli. Ei riitä, ettei itse tee väkivaltaa. Miesten306787Tiedät, että en voi enää laittaa viestiä
Aikaa kulunut. Eikä se näyttäisi enää luontevalta vastata näin pitkän ajan jälkeen. Tiedän myös, että sinä et enää lait82704Lautakunta käsittelee Iisalmen kulttuuri- ja vapaa-aikajohtajan virkasuhteen purkua koeajalla:
Lautakunta käsittelee Iisalmen kulttuuri- ja vapaa-aikajohtajan virkasuhteen purkua koeajalla: "Aina valinta ei mene nap54626Kun kohtaatte rakkauden, tarttukaa siihen
Toimisinko jälkiviisaana toisin? Varmasti. Vaikka silloin kuvittelin tekeväni, niin kuin on oikein. Mahdollisimman siist49609Lienee aika luopua siitä kaikesta
mitä meillä ikinä olikaan. Hassua, koska juuri mitään ei ole edes ollutkaan. En vaan jaksa tätä mahdotonta juttua enää j64592- 75514