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
176
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 sössi kaiken 2 vuodessa, itkee nyt Marinin perään
Nyt on taas sama vanha itkuvirsi, kun ei omat taidot riittänee. Kaikki on taas muiden syytä. No miten sen "Tunnin juna"317462Ikuiset kaipaajat
Miksette vaan mene sen kaipauksen kohteen luokse ja puhu sille suoraan? Mitä järkeä on kaipailla jotain puolituttua vuo1434813Nyt se on selvitetty: Sanna Marinin hallitus lisäsi menoja 41 miljardilla
”vasemmistohallitus oli katastrofaalisen huono”, sanoo kokoomus. Sanna Marinin (sd.) hallituksen tekemät menolisäykset754456Orpon hallitus runnoi Tunnin junan ilman tarvetta
Näinkö valtiontaloutta hoidetaan? Siis asiantuntijoidenkin aikoja sitten kannattamattomaksi laskema Tunnin juna tehdään83532Riikka ottaa miljardi euroa EU:n yhteisvelkaa Suomelle
Niin kääntyi irvipersun takki taas, vaikka vaalilupauksissa oli ettei yhteisvelkaa Suomi enää koskaan ota. No nyt otti m793379Lindtman ylivoimainen suosikki pääministeriksi
Lindtmania kannattaa pääministeriksi peräti 50 prosenttia useampi kuin toiseksi suosituinta Kaikkosta. https://www.ilta453170- 262794
Veronmaksajat kustantavat yrittäjien eläkkeitä jo yli 500 miljoonalla
Suomalaista yrittäjää ei kommunistista erota. Aktiivisen "yrittämisen" maksattaa yritystukina yhteiskunnalla, ja vieläpä322651Sanna Marin - Maailman paras talousasiantuntija?
PersKeKoa pukkaa? https://www.hs.fi/politiikka/art-2000011636623.html292509Persut rahoittavat velkarahalla rikkaiden ökyelämää
Minkä vuoksi persut eivät leikkaa rikkailta, joilla on maksukykyä? Tuskinpa tuo persujen käytös saa Suomen kansalta hyv882503