Sanojen kombinatoriikka

Sanojen kombinatoriikka on 1900-luvun lopulla kehittynyt matematiikan ja teoreettisen tietojenkäsittelytieteen haara, jossa tutkitaan sanoja symbolijonoina ilman semanttista merkitystä. Sovelluksia löytyy esimerkiksi molekyylibiologiasta, jossa DNA:ta voidaan mallintaa sanoina nelikirjaimisessa aakkostossa A,C,G, T. 
Symboliaakkosto merkitään usein formula_1 (kreikkalaisen aakkoston iso sigma-kirjain). Tällöin DNA:n kohdalla formula_2 ja bittien kohdalla formula_3. Yleensä vaaditaan, että symboliaakkoston on oltava äärellisen kokoinen, ja usein käytetty esimerkki edellisten lisäksi on formula_4, jolloin kyseessä on siis 3-kirjaiminen symboliaakkosto. 
Symboliaakkostoon liittyvä sana on mikä tahansa äärellisen pituinen merkkijono, jonka merkit kuuluvat annettuun symboliaakkostoon, ja sanan pituus on sen merkkien lukumäärä. Esimerkiksi formula_5-aakkoston kohdalla formula_6 on eräs 5-pituinen sana ja formula_7 on eräs 10-pituinen sana. Sanoja merkitään usein "sanamuuttujilla" kuten formula_8 tai formula_9, jolloin formula_10 merkitsee formula_11-sanan pituutta. Esimerkiksi jos formula_12, formula_13. 
Tietyn symboliaakkoston formula_1 määräämää sanojen joukkoa merkitään formula_15, ja siihen kuuluu lisäksi tyhjä sana, jossa ei ole yhtään symbolia (Se on siis 0-pituinen.), ja jota merkitään usein formula_16 (kreikkalaisen aakkoston pieni epsilon-kirjain). Selvästi formula_15-joukon eri sanoja on (numeroituvasti) ääretön määrä: 0-pituinen tyhjä sana formula_18, 1-pituiset, 2-pituiset, jne. 
Äärellisen pituisten sanojen lisäksi toisinaan tarkastellaan äärettömän pituisia sanoja, joiden kohdalla symbolijono jatkuu äärettömän pitkälle oikealle. Näin on esimerkiksi, kun formula_19, missä formula_20-"jakso" jatkuu oikealle äärettömän monta kertaa, mutta tietenkään kaikkien äärettömän pitkien sanojen rakenteen ei tarvitse olla näin säännöllinen. 
Sanojen kohdalla niiden välinen peruslaskutoimitus on tulo eli katenaatio, joka yksinkertaisesti tarkoittaa kerrottavien sanojen symbolijonojen asettamista peräkkäin niin, että näin muodostuu uusi sana. Esimerkiksi jos formula_21, formula_22 ja formula_23 merkitsee tuloa, formula_24 tai formula_25. Selvästi tämä tulo on epäkommutatiivinen (Sillä yleensä formula_26.) ja assosiatiivinen (Sillä formula_27 suoraan symbolien peräkkäin asettamisesta johtuen, koska formula_28 ja formula_29 ovat molemmilla puolilla samassa vasemmalta-oikealle-järjestyksessä.). 
Assosiatiivisuudesta johtuen sulkumerkit ovat tuloissa tarpeettomia, eli voidaan merkitä formula_30 ja yleisemminkin esimerkiksi formula_31. Usein "tulopisteetkin" jätetään merkitsemättä, jolloin äskeinen lyhenee muotoon formula_32. Tällä tulo-operaatiolla varustettu formula_15-joukko on vapaa monoidi, mistä seuraa, että sanojen tutkimus on yhteydessä myös algebraan. 
Tärkeä tulon erikoistapaus on sanan potenssi, joka tarkoittaa sanan kertomista itsellään eksponentin osoittaman määrän, eli siis formula_34, missä formula_11-sanoja on peräkkäin n kappaletta. Esimerkiksi jos formula_36 ja formula_37, niin formula_38. Lisäksi määritellään luonnolliseen tapaan, että formula_39 ja formula_40. 
Myös prefixin käsite on tärkeä. Sana formula_11 on sanan formula_42 prefix silloin, kun sanan formula_11 kirjainjono muodostaa sanan formula_42 kirjainjonon alkuosan, mikä merkitään formula_45. Esimerkiksi formula_46, ja lisäksi formula_15:n kaikilla sanoilla formula_11 on tietenkin voimassa se, että formula_49 ja formula_50.
Sanojen kombinatoriikka tutkii mm. seuraavanlaisia kysymyksiä.
Esimerkki 1) Millaisten ehtojen vallitessa sanat kommutoivat, eli formula_51. 
On selvää, että sanat formula_11 ja formula_42 kommutoivat ainakin silloin, jos molemmat ovat saman sanan formula_29 potensseja, eli formula_55 ja formula_56, jolloin formula_57. Esimerkiksi jos formula_58 ja formula_59 ja formula_60, formula_61. On melko helposti osoitettavissa, että tämä saman formula_29-sanan potensseina oleminen on riittävyyden lisäksi myös välttämätön ehto sille, että sanat formula_11 ja formula_42 kommutoisivat, eli formula_65 on sama sana kuin formula_66.
Esimerkki 2) Onko mahdollista, että äärettömän pitkälle oikealle jatkuva sana ei sisällä "neliötä" eli samaa "jaksoa" kahta kertaa peräkkäin. Jos näin on, mikä on pienin symboliaakkoston koko, jolloin tämä on mahdollista.
On selvää, että ainakaan 2-kirjaimisessa symboliaakkostossa tämä ei ole mahdollista, sillä selvästi siinä pisimmät "neliötä" sisältämättömät sanat ovat formula_67 ja formula_68, mutta esimerkiksi jo formula_69 eli siinä formula_70 on toistuvana "jaksona". Myös yllä esitetty oikealle ääretön sana sisältää "neliön", sillä siinä formula_20-"jakso" toistuu peräkkäin kahdesti. Esimerkiksi sana formula_72 voi ensisilmäyksellä näyttää "neliöttömältä", mutta se silti sisältää formula_73-"jakson" kahdesti peräkkäin, sillä formula_74. Osoittautuu kuitenkin, että jo 3-kirjaimisessa aakkostossa on löydettävissä tällaisia oikealle äärettömiä "neliöttömiä" sanoja, joista tyypillinen esimerkki on ns. 3-symbolinen Thue-sana. Kyseinen sana on siis "neliötä" sisältämätön mutta oikealle ääretön, ja sen alku on
formula_75. 
Tämä 3-symbolinen Thue-sana voidaan muodostaa ns. morfismi-iteroinnin avulla, mikä on sanojen kombinatoriikassa yleinen menetelmä muodostaa vastaavanlaisia sanoja. Tässä tapauksessa morfismi formula_76 on seuraava
formula_77
formula_78
formula_79
, mikä tarkoittaa siis sitä, että mm. formula_80:n kohdalle kirjoitetaan formula_81, jolloin esimerkiksi formula_82. Morfismin iterointi on vielä aloitettava jostain pisteestä, joka tässä tapauksessa – niin kuin usein muutenkin – on formula_83-kirjain. Muodostetaan siis äärellisen pituisia sanoja 
formula_84
, sillä formula_85 tarkoittaa formula_76-morfismin soveltamista formula_83-kirjaimeen formula_88 kertaa, jolloin esimerkiksi
formula_89.
Näin saaduissa äärellisen pituisissa sanoissa aiempi on aina seuraavien prefix, mikä nähdään induktiivisesti, sillä jos induktio-oletuksen mukaan
formula_90 eli formula_91 (Missä siis formula_92 on formula_93-sanan loppu sen induktio-oletuksen mukaisen formula_94-alun jälkeen.), niin
formula_95, siis formula_96
mistä taas seuraa, että formula_97. Esimerkiksi
formula_98, jolloin formula_99.
Lisäksi induktion perusaskeleena tässä on tietenkin se, että 
formula_100.
Iteroiden saadut sanat voidaan siis tulkita saman oikealle äärettömän sanan yhä piteneviksi (On voimassa formula_101, sillä formula_76-morfismi kirjoittaa jokaisen kirjaimen tilalle vähintään yhden kirjaimen, ja lisäksi "iteraatioalkujen" alussa on formula_83-kirjain, ja formula_83-kirjainten tilalle kirjoitetaan formula_20, mistä seuraa, että "iteraatioalkujen" pituus kasvaa aidosti.) äärellisen pituisiksi aluiksi, jolloin nämä "iteraatioalut" selvällä tavalla määräävät yksikäsitteisen oikealle äärettömän 3-symbolisen Thue-sanan. Tämän x:nnes kirjain määräytyy niin, että katsotaan mikä on formula_94-"iteraatioalun" x:nnes kirjain. Tässä formula_94:ää käytettiin siksi, että "iteraatioalku" olisi riittävän pitkä (Onhan formula_108.), mutta käytännössä riittää iteroida selvästi vähemmän kuin formula_109 kertaa (Oikeastaan helposti nähdään, että formula_110, kun formula_111.).
On syytä huomata, että yllä osoitettiin vain se, että annetun formula_76-morfismin formula_83-iteroinnilla muodostuu mielekkäällä tavalla oikealle ääretön sana. Sitä tässä ei osoitettu, että kyseinen sana on myös "neliötön", vaan tämän osoittaminen vaatisi oman tarkastelunsa, jota tässä ei esitetä. Erityisesti on syytä huomata se, että yleisestikin morfismiin sijoitettavan sanan "neliöttömyys" ei vielä takaa tuloksen "neliöttömyyttä". Tästä esimerkkinä formula_76-morfismi, jossa nyt aiemman sijaan
formula_115
formula_116
formula_117
, jota formula_83-kirjaimesta iteroiden saataisiin vastaavalla tavalla oikealle ääretön sana, sillä formula_119- ja pitenemis-vaatimukset täyttyvät. Kuitenkaan näin saatu sana ei ole "neliötön", sillä vaikka vielä formula_120 on "neliötön", niin formula_121, eli formula_122 sisältää formula_70-"neliön". Tällainen "neliön ilmaantuminen" on mahdollista erityisesti siksi, että "ilmaantuvan neliön" ei tarvitse "osua tasan" formula_124-"lohkoihin", vaan se voi muodostua myös niiden välissä kuten yllä, missä formula_70-"neliö" muodostui formula_126-"osuuden" väliin niin, että "osuuden" vasen formula_81-"reuna" ja oikea formula_128-"reuna" eivät ole mukana muodostamassa "neliötä".
Lähteet.