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
144
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
- 1191732
Noniin rakas
Annetaanko pikkuhiljaa jo olla, niin ehkä säilyy vienot hymyt kohdatessa. En edelleenkään halua sulle tai kenellekään mi991558Lasten hyväksikäyttö netissä - Joka 3. nuori on saanut seksuaalisen yhteydenoton pedofiililtä
Järkyttävää! Lapsiin kohdistuva seksuaalinen hyväksikäyttö verkossa on yhä pahempi ongelma. Ulkolinja: Lasten hyväksikäy441066Multa sulle
Pyörit 24/7 mielessä, kuljet mun mukana, mielessä kyselen sun mielipiteitä, vitsailen sulle, olen sydän auki, aitona. M29919Kumpi vetoaa enemmän sinuun
Kaivatun ulkonäkö vai persoonallisuus? Ulkonäössä kasvot vai vartalo? Mikä luonteessa viehättää eniten? Mikä ulkonäössä?38881Nainen, olen tutkinut sinua paljon
Salaisuutesi ei ole minulle salaisuus. Ehkä teimme jonkinlaista vaihtokauppaa kun tutkisimme toisiamme. Meillä oli kumm50836Mies, eihän sulla ole vaimoa tai naisystävää?
Minusta tuntuu jotenkin, että olisit eronnut joskus, vaikka en edes tiedä onko se totta. Jos oletkin oikeasti edelleen s43778Olet myös vähän ärsyttävä
Tuntuu, että olet tahallaan nuin vaikeasti tavoiteltava. En tiedä kauanko jaksan tätä näin.37770Okei nyt mä ymmärrän
Olet siis noin rakastunut, se selittää. Onneksesi tunne on molemminpuolinen 😘56768Onko sulla empatiakykyä?
Etkö tajua yhtään miltä tämä tuntuu minusta? Minä ainakin yritän ymmärtää miltä sinusta voisi tuntua. En usko, että olet37750