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
96
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
En voi jutella kanssasi
tietenkään, mutta täällä voin sanoa sinulle, että se sinun hiljaisuutesi ja herkkyytesi eivät ole heikkoutta. Ne ovat ih517016Trump ja Vance murskasivat ja nolasivat Zelenskyn tiedotusvälineiden edessä Valkoisessa talossa.
Jopa oli uskomaton tilaisuus Valkoisessa talossa. Zelensky jäi täydelliseksi lehdellä soittelijaksi suhteessa Trumpiin j7033123Kokoomus haluaa hoitaa flussat yksityisellä, jotta säästettäisiin rahaa ja aikaa
Mies hakeutui Terveystalo Kamppiin flunssaoireiden takia helmikuisena sunnuntai-iltana. Diagnoosiksi kirjattiin influens831310Mikä on kaivattusi ärsyttävin piirre?
Mun kaivattu on erittäin vastahakoinen puhumaan itsestä. Kääntää puheenaiheen aina muuhun kun hänestä tulee puhetta.981291- 841285
Anteeksi Pekka -vedätys
Apuna Ry:n somessa levinnyt Anteeksi Pakka -kampanja saa aina vaan kummallisempia piirteitä. ”Mä pyydän anteeksi. Mä631187- 891180
Rakkaus ei iloitse vääryydestä vaan iloitsee yhdessä TOTUUDEN kanssa.
Tajuatteko, että jotkut ihmiset pitävät siitä, kun toiset kaatuvat? He nauttivat siitä, kun toiset mokaavat tai käyttävä2361136Zelenskyi ei suostunut nöyrtymään Trumpin ja Vancen edessä, siksi meni pieleen
Trumppia täytyy imarrella, silloin homma toimii aina. Tähän Zelenskyi ei suostunut.2181120- 761046