Catalanin lukujen kombinatoriset applikaatiot

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
(()()) --> **)*)) --> ?

1

157

    Vastaukset

    Anonyymi (Kirjaudu / Rekisteröidy)
    5000
    • 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

    1. Ikävöin sinua kokoyön!

      En halua odottaa, että voisin näyttää sinulle kuinka paljon rakastan sinua. Toivon, että uskot, että olen varsin hullun
      Ikävä
      61
      4308
    2. KALAJOEN UIMAVALVONTA

      https://www.kalajokiseutu.fi/artikkeli/ei-tulisi-mieleenkaan-jattaa-pienta-yksinaan-hiekkasarkkien-valvomattomalla-uimar
      Kalajoki
      137
      3021
    3. Jos sinä olisit pyrkimässä elämääni takaisin

      Arvelisin sen johtuvan siitä, että olisit taas polttanut jonkun sillan takanasi. Ei taida löytyä enää kyliltä naista, jo
      Tunteet
      45
      2342
    4. Kadonnut poika hukkunut lietteeseen mitä kalajoella nyt on?

      Jätelautta ajautunut merelle ja lapsi uponnut jätelautan alle?
      Kalajoki
      45
      2254
    5. Älä mahdollisesti ota itseesi

      En voinut tietää. Sitäpaitsi.. niin
      Ikävä
      24
      1873
    6. Hukkuneet pojat kalajoella pakolaisia?

      Eivät osanneet suomea nimittäin.
      Maailman menoa
      91
      1832
    7. Ota nainen yhteyttä ja tee Tikusta asiaa?

      Niin sitten minä teen Takusta asiaa.
      Ikävä
      28
      1586
    8. Joku hukkui Hyrynsalmella?

      Oliko mökkiläinen taas?
      Hyrynsalmi
      22
      1539
    9. Mitä sinä mietit

      Mies?
      Ikävä
      148
      1384
    10. Metsästysmökki

      Metsästyskortti saapui. Lisäksi metsästysmökki varata!
      Kuhmo
      32
      1200
    Aihe