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

153

    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. Useita puukotettu Tampereella

      Mikäs homma tämä nyt taas on? "Useaa henkilöä on puukotettu Tampereen keskustassa kauppakeskus Ratinan lähistöllä." ht
      Tampere
      243
      4629
    2. Kuka rääkkää eläimiä Puolangalla?

      Poliisi ampui toistakymmentä nälkiintynyttä eläintä Puolangalla Tilalta oli ollut karkuteillä lähes viisikymmentä nälkii
      Puolanka
      76
      3065
    3. Leipivaaran päällä on kuoleman hiljaista.

      Suru vai suuri helpotus...
      Puolanka
      47
      2473
    4. Meneeköhän sulla

      oikeasti pinnan alla yhtä huonosti kuin mulla? Tai yhtä huonosti mutta jollain eri tyylillä? Ei olisi pitänyt jättää sua
      Ikävä
      45
      1777
    5. Laitetaas nyt kirjaimet tänne

      kuka kaipaa ja ketä ?
      Ikävä
      28
      1753
    6. Koska näit kaivattusi viimeksi

      Milloin tapasit rakkaasi? Ja etenikö suhde yhtään?
      Ikävä
      80
      1456
    7. Lähetä terveisesi kaipaamallesi henkilölle

      Vauva-palstalta tuttua kaipaamista uudessa ympäristössä. Kaipuu jatkukoon 💘
      Ikävä
      85
      1285
    8. PS uusimman gallupin rakettimainen nousija

      https://yle.fi/a/74-20170641 Aivan ylivoimaisesti suurin kannatuksen nousu PS:lle. Nousu on alkanut ja jatkuu 2 vuoden
      Maailman menoa
      143
      965
    9. Tekiskö nainen mieli tavata...

      Viikonloppuna ja...?
      Ikävä
      69
      948
    10. Sellainen tunne sydämessä

      Että nainen olet kaivannut minua. Tai sanonko että oikeastaan koet sitä samaa nostalgiaa, kaipuuta ja mukavia muistoja,
      Ikävä
      86
      894
    Aihe