Catalanin luvuista ja niiden sovelluksista
VIERTOLA, SARA (2013)
2013
Matematiikka - Mathematics
Informaatiotieteiden yksikkö - School of Information Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2013-04-04
Julkaisun pysyvä osoite on
https://urn.fi/urn:nbn:fi:uta-1-23710
https://urn.fi/urn:nbn:fi:uta-1-23710
Tiivistelmä
Catalanin luvut tarjoavat paljon hauskoja ja kiinnostavia esimerkkejä matematiikan opiskelun eri osa-alueisiin. Catalanin lukuja voidaan soveltaa moniin eri sovellusalueiden ongelmiin kuten tietojenkäsittelytieteen, kombinatoriikan, geometrian tai graafiteorian ongelmiin tai vaikkapa shakin peluuseen.
Tässä tutkielmassa keskitytään rakentamaan hyvä pohja Catalanin lukujen ja niiden monien sovelluksien ymmärtämiseen. Tämän takia Catalanin lukujen kaava johdetaan kahden erilaisen ongelmatilanteen pohjalta. Johtamistavan sisäistäminen auttaa ymmärtämän, mitkä muut ongelmat ratkeavat Catalanin lukujen avulla, tai miten Catalanin lukuja voidaan soveltaa uusiin tilanteisiin. Ymmärtämistä tuetaan monilla esimerkeillä ja kuvilla.
Catalanin luvut antavat tiettyjen ongelmien ratkaisujen lukumäärän. Lukumäärän kasvaessa on kuitenkin vaikea pystyä löytämään kaikki eri ratkaisuvaihtoehdot, ellei vaihtoehtojen luettelemiseen ole jotakin systemaattista tapaa. Tässä työssä esitetään käsiteltäviin ongelmiin systemaattinen tapa löytää kaikki eri ratkaisuvaihtoehdot.
Työn toisen luvun alussa annamme Catalanin lukujen määritelmän. Tutustumme Eulerin muotoilemaan monikulmion jakamisongelmaan, ja todistamme, että monikulmion jakamisongelman ratkaisut ovat Catalanin lukuja. Luvun lopussa käsittelemme kaikkien ratkaisujen löytämistä sekä Catalanin lukujen likiarvoja.
Kolmannessa luvussa todistamme kahdella eri tavalla, että sallittujen hilapolkujen lukumäärät ovat Catalanin lukuja. Näytämme myös, miten kaikki ratkaisut voidaan luetella.
Neljännessä luvussa esittelemme muita Catalanin lukujen sovelluksia ja näytämme niiden yhteyden edellisten lukujen esimerkkeihin.
Päälähteinä työssä on käytetty teoksia Koshy T. Catalan Numbers with Applications ja Grimaldi, R. P. Fibonacci and Catalan Numbers, An Introduction. Hilapolkujen yhteydessä on lähteenä käytetty myös artikkelia Crepinšek M., Mernik L. An Efficient Representation for Solving Catalan Number Related Problems, International Journal of Pure and Applied Mathematics, Volume 56, No. 4, 2009. Nämä ja muut lähteet on kerrottu kirjallisuusluettelossa.
Tässä tutkielmassa keskitytään rakentamaan hyvä pohja Catalanin lukujen ja niiden monien sovelluksien ymmärtämiseen. Tämän takia Catalanin lukujen kaava johdetaan kahden erilaisen ongelmatilanteen pohjalta. Johtamistavan sisäistäminen auttaa ymmärtämän, mitkä muut ongelmat ratkeavat Catalanin lukujen avulla, tai miten Catalanin lukuja voidaan soveltaa uusiin tilanteisiin. Ymmärtämistä tuetaan monilla esimerkeillä ja kuvilla.
Catalanin luvut antavat tiettyjen ongelmien ratkaisujen lukumäärän. Lukumäärän kasvaessa on kuitenkin vaikea pystyä löytämään kaikki eri ratkaisuvaihtoehdot, ellei vaihtoehtojen luettelemiseen ole jotakin systemaattista tapaa. Tässä työssä esitetään käsiteltäviin ongelmiin systemaattinen tapa löytää kaikki eri ratkaisuvaihtoehdot.
Työn toisen luvun alussa annamme Catalanin lukujen määritelmän. Tutustumme Eulerin muotoilemaan monikulmion jakamisongelmaan, ja todistamme, että monikulmion jakamisongelman ratkaisut ovat Catalanin lukuja. Luvun lopussa käsittelemme kaikkien ratkaisujen löytämistä sekä Catalanin lukujen likiarvoja.
Kolmannessa luvussa todistamme kahdella eri tavalla, että sallittujen hilapolkujen lukumäärät ovat Catalanin lukuja. Näytämme myös, miten kaikki ratkaisut voidaan luetella.
Neljännessä luvussa esittelemme muita Catalanin lukujen sovelluksia ja näytämme niiden yhteyden edellisten lukujen esimerkkeihin.
Päälähteinä työssä on käytetty teoksia Koshy T. Catalan Numbers with Applications ja Grimaldi, R. P. Fibonacci and Catalan Numbers, An Introduction. Hilapolkujen yhteydessä on lähteenä käytetty myös artikkelia Crepinšek M., Mernik L. An Efficient Representation for Solving Catalan Number Related Problems, International Journal of Pure and Applied Mathematics, Volume 56, No. 4, 2009. Nämä ja muut lähteet on kerrottu kirjallisuusluettelossa.