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
<50
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
Aikakone-yhtyeestä tuttu Maki Kolehmainen kuollut
Kuoli tänään aamuyöstä nopeasti edenneeseen sairauteen. Hän oli 58-vuotias.1126699Rokote otti taas omansa. Maki Kolehmainen kuollut.
RIP Maki. Muusikko, tuottaja ja säveltäjä Maki Kolehmainen on kuollut. Asiasta uutisoi ensimmäisenä Yle. Kolehmainen k552844Mites meillä nainen tämä yhteys
Onko se yhteistä se kokemus siitä, että tunnemme syvästi toisemme? Tunnemme vetoa ja sielunyhteyttä, jotain kuin toisest681630- 581339
Se viime kohtaaminen
Oli naine vähän sellainen kohmea. Nopeasti yritin etsiä merkkejä sinusta mutta en saanut mitään ilmi. Ajattelin että ny681253- 1141047
Ihan rakentavassa mielessä
Haluaisin nainen kysyä sinulta ja myös itseltäni että mitä me oikein odotellaan? Olisiko aika jo käydä edes treffeillä?741030- 89947
- 53864
- 46853