Fibonaccin lukujono on monille tuttu: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. . . Se muodostetaan ottamalla uudeksi luvuksi aina kahden edellisen luvun summa.
Lukujono sai nimensä matemaatikko Leonardo Pisalaiselta, jonka kerrotaan keksineen lukujonon pohtiessaan kanipopulaation kasvua joskus 1200-luvulla. Hänet tunnetaan sittemmin nimellä Fibonacci.
Fibonaccin jono löytyy luonnosta. Esimerkiksi artisokan kukinto, männynkävyn peitinsuomujen määrä ja puiden oksien haarautumat noudattelevat lukujonoa.
Entä abaababaabaab…?
Se on Fibonaccin sana. Kahdella kirjaimella muodostettu merkkijono rakennetaan samantyyppisillä säännöillä kuin Fibonaccin luku.
Ensimmäiset sanat ovat b ja a. Kaikki niitä seuraavat sanat muodostetaan pistämällä kaksi edellistä putkeen. Listassa, josta Fibonaccin sana muodostetaan on ensimmäisenä b, jotta itse sana saadaan alkamaan a:lla.
Tulos on loputon kirjainjono, joka ei koskaan toista itseään.
Sana tai merkkijono ilmestyi merkkijoukkoja tutkivaan matematiikkaan eli kombinatoriikkaan viimeistään 1940-luvulla.
Kombinatoriikassa pohditaan jonoja ja todennäköisyyksiä. Esimerkiksi se, miten monella tapaa korttipakan voi järjestää, on kombinatoriikan kysymyksiä. Myös merkkijonot, siis myös sanat, ovat kombinatoriikan alaa.
Fibonaccin sanan keksijästä ei ole varmuutta. Ensimmäisen kerran se mainittiin tutkimuskirjallisuudessa vuonna 1947. Vastaava kehitelmä mainittiin toisessa yhteydessä satoja vuosia aiemmin.
”Fibonaccin sana on yksinkertainen. Siihen tarvitaan vain kaksi merkkiä ja sen luomiseen tarvittava sääntö on selvä”, selittää Turun yliopiston tutkijatohtori Jarkko Peltomäki. Turun yliopistolla on kombinatoriikan tutkimuksessa pitkät perinteet.
”Siitä huolimatta Fibonaccin sanalla on paljon erikoisia ominaisuuksia. Aika usein, jos joku keksii kombinatoriikassa uuden idean, sitä testataan juuri ensin Fibonaccin sanalla. Emme vielä tunne sen kaikkia outouksia.”
Yksi esimerkki sanan erikoisuuksista on professori Juhani Karhumäen todistus vuodelta 1983.
Todistuksen mukaan jokainen Fibonaccin sanassa esiintyvä lyhyempi sana esiintyy enintään kolmesti peräkkäin, muttei koskaan neljästi. Aba on jo sanan alun lähellä kolmesti peräkkäin, mutta yhdistelmää abaabaabaaba ei löydy sanasta kertaakaan.
Fibonaccin sana on mahdollisimman vaikea hahmotettava klassiselle etsintäalgoritmille, joka pyrkii löytämään sanoista tuttuja merkkijonoja.
”Jokin Fibonaccin sanan rakenteesta tekee sellaisen, ettei algoritmi saa otetta. Algoritmi joutuu vertailemaan merkkejä paljon enemmän kuin yleensä.”
Mikään rajallisen mittainen Fibonaccin sana ei ole palindromi, jollaisen voi lukea kumminkin päin. Sanasta voi tehdä palindromin poistamalla kaksi viimeistä kirjainta.
Miksi Fibonaccin sanan kaltainen mitään tarkoittamaton merkkijono kiinnostaa matemaatikkoja?
Peltomäki selittää merkkijonojen olevan matematiikan perustutkimuskohde, kuten luvut ja geometriset muodotkin.
Fibonaccin sanaa voi verrata geometriasta tuttuun fraktaaliin. Se on muoto, joka skaalautuu omien sääntöjensä mukaan loputtomasti, niin läheltä kuin kaukaa katsottuna.
. Fibonaccin spiraali rakentuu pienenevistä neliöistä. Niiden sivut pienenevät aina samassa suhteessa. Kuva: SEYMOUR/SCIENCE PHOTO LIBRARY
Peltomäki tekee perustutkimusta, jolla ei tavoitella käytännön sovelluksia. Silti merkkijonojen ymmärtäminen ei ole vain akateemista leikkiä.
”Sanomme tietokoneita laskukoneiksi, mutta itse asiassa ne eivät käsittele lainkaan lukuja, vaan merkkijonoja. A ja b voidaan ihan yhtä hyvin korvata ykkösellä ja nollalla.”
Kombinatoriikka ei myöskään rajoitu kahden merkin yhdistelmiin. Periaatteessa merkkejä voi olla vaikka kuinka paljon.
Merkkijonojen ymmärtäminen on tarpeen, kun suunnitellaan hakukoneita, jotka etsivät merkkiyhdistelmiä tietomassoista.
”Tehokas algoritmi analysoi tekstimassan. Sen sijaan, että kävisi koko tekstimassan halki merkki kerrallaan, se pyrkii päättelemään, mistä merkkejä kannattaa etsiä.”
Tietojenkäsittelytieteen lisäksi kombinatoriikalle on löytynyt sovelluksia genetiikasta. Ihmisen genomi on kirjoitettu dna-molekyylin neljällä emäksellä, joita voidaan ajatella neljän merkin jonona.
”Mitä paremmin ymmärrämme tällaisten jonojen ominaisuuksia, sitä paremmin voimme ymmärtää dna:n kaltaisia valtavia datamassoja.”
Peltomäki tekee parhaillaan tutkimusta, joka pyrkii selvittämään sanoissa esiintyviä toistoja, joissa sallitaan kirjainten siirtely. Toistosta abcabc saa siirtämällä ensimmäisen kirjaimen paikkaa siirretyn toiston bacabc, mutta merkkien määrä ja suhde toisiinsa pysyvät samoina.
”Yritän ymmärtää, millä säännöillä tällaiset toistot sanoissa toistuvat ja milloin tulee merkki, joka rikkoo ne.”
Peltomäki on tutkinut Fibonaccin sanaa itsekin.
”Se on kiehtova, koska se on niin hyvin tunnettu, mutta siitä voi silti löytää aina uutta.”
Hän kertoo yhden oman tuloksensa, jonka löysi kollegansa Markus Whitelandin kanssa.
Sen ideana on kirjoittaa Fibonaccin luku käyttämällä kuutta sanaa, joista jokaisessa toistuu sama kahdesti. Ne ovat aa, abab, abaaba, baba, baabaa, baababaaba. Näiden avulla voidaan kirjoittaa miten pitkä Fibonaccin sana tahansa, tähän tyyliin: abaaba baabaa baba abab aa baababaaba abab aa baba abaaba. . .
Seuraavassa vaiheessa poistetaan jokaisesta kuudesta sanasta aina puolet. Saadaan merkkijono joka alkaa näin: aba baa ba a baaba ab a ba aba. . .
Yhtä lailla loputtoman pitkä, itseään toistamaton merkkijono, muttei Fibonaccin sana.
Mutta tässä ei vielä kaikki. Jos laitamme Fibonaccin sanan eteen lisätään kaksi merkkiä, b ja a, ne sekoittuvat ensimmäiseen merkkiin ja muuttavat näin koko merkkijonon jakautumista kuuden sanan kesken.
Jos toistot poistetaan, on lopputulos sama kuin mistä lähdettiin eli Fibonaccin sana, jonka edessä ovat nuo kaksi merkkiä.
”Eli poistamme puolet, ja kuitenkin jäljelle jää sama sana. Minusta se on kiehtovaa. Se kertoo, miten Fibonaccin sana yllättää aina uudelleen.”
Korjaus 19. maaliskuuta kello 11.25: Tarkennettu, että Leonardo Pisalainen tunnettiin sittemmin nimellä Fibonacci. Korjaus 23. maaliskuuta kello 9.45: dna-molekyylin koodia kirjoitetaan emäksillä, ei aminohapoilla.
