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
195
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
Purra hyökkää nyt suomalaisen duunarin kimppuun teettämällä mamuilla palkatonta työtä
Niinpä niin. Persut duunaripuolue, HAH. Joko alkaa kovapäisinkin persu älyämään, että persut ovat Suomen kansan vastain32112004Mitä hyvää rikkaiden hyysääminen Suomelle tuonut?
Minäpä vastaan: ei yhtikäs mitään, vaan pelkkää vahinkoa. Demareiden ansiosta Suomen valtio oli käytännössä vielä 1980-15611117Tytti Tuppurainen häpäisi Suomen epäisänmaallisella lausunnollaan USA:n ulkoministerille Rubiolle.
https://www.is.fi/politiikka/art-2000011816267.html Miksi Tytti Tuppurainen päästetään antamaan typeriä lausuntoja noin2666466Purra ehdottaa vaan Tanskan mallia, joka on erittäin hyvä malli
Purra ehdotti helmikuussa Suomeen Tanskan mallia, jossa maahanmuuttajilta vaaditaan työntekoa sosiaalitukien saamiseksi.2395273Kokoomusnuoret: Sosiaalitukien työvelvoitteen tulisi koskea kaikkia
Riikka Purra on esittänyt, että maahanmuuttajilta tulisi edellyttää palkatonta työtä sosiaalitukien vastineeksi. Kokoom1813737- 1743568
L/OVER ikuisesti minun
Aivan järkyttävä sarja. Ei voi olla katsomatta, mutta tuo omat muistot mieleen. Näyttelijät näyttelevät turhankin hyvin542581Mitä voisit miehenä tehdä?
Suojellaksesi kaikkia naisia ja että heillä olisi juuri sinun käytöksen takia edes vähän turvallisempaa. Mitä miehenä3292010Jyrki Linnankivi, Jyrki 69 - Goottirokkarista kirkonmieheksi Lappiin!
Jyrki Linnankivi eli Jyrki 69 on The 69 Eyes -rockyhtyeen vokalisti. Lauluhommien lisäksi hän sanoittaa, säveltää ja sov121854Purra vaatii: Työvelvoite maahanmuuttajille ja kantasuomalaisille pitkäaikaistyöttömille
Jos Perussuomalaiset ja Kokoomus ovat seuraavan hallituksen kaksi johtavaa puoluetta, on suomalaisille pitkäaikaistyöttö1091849