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
74
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
Asianajaja Herman Ljungberg
Ei ole tällä herralla kaikki muumit laaksossa, kun väittää, että kaapelien katkominen on NORMAALIA. Kaikkea se leipä elä1566799Löytyykö jyväskylästä naista kenenkä pyllyä saisi kosketella ja haistellla??
Olen ihan mukava ja kunnollinen herras mies 41 vuotta.313926Neljä nuorta kuoli Nurmijärvellä, auto suistui jokeen Onnettomuuden tutkinta on vielä alussa.
Neljä nuorta kuoli Nurmijärvellä, auto suistui jokeen Onnettomuuden tutkinta on vielä alussa. Poliisi sai lauantaina 4.1101858- 591848
Sähköauto sopii erinomaisesti maaseudulle, jopa paremmin kuin kaupunkiin.
Sähköautolla pärjää maaseudulla jopa paremmin kuin kaupungissa, sillä jokainen sähköistetyn talon piha on mahdollinen la1911438- 811431
Nainen, taidan inhota minua todella
tai sitten et halua olla missään tekemisissä kanssani. Sellaiset otteet sulla. On tosi karmeata olla toiselle kuin kuoll731081Tämä oli vuoden 1. luetuin artikkeli Suomi24 Viihteessä: Rock-legenda Andy McCoy, 61, sai eläkkeen
Rock-legenda Andy McCoy, 61, sai kuin saikin taiteilijaeläkkeen - Tämän suuruinen eläke on kuussa! -artikkeli oli v. 20213974- 48969
Rattoisaa lauantai iltaa
Mitäs tänään tapahtuu? Mitäs kirsikalle kuuluu? Onko lähdössä iltaelämään? 😊✨💞🌆 Minä vietä taas yksinäistä koti-iltaa223936