Kombinatoriikka, kesä 2016

Luennoitsija 

Hans-Olav Tylli

Laajuus

5 op.

Tyyppi

Kombinatoriikan kurssi sopii valinnaiseksi kurssiksi matematiikan aineopintoihin, ja kurssi on tarkoitettu 1-3 vuoden opiskelijoille. Kurssi sopii myös valinnaiseksi kurssiksi matematiikan aineenopettajan syventyviin opintoihin, sekä myös sivuaineopiskelijoille, jotka tarvitsevat alkeiskombinatoriikan tietoja ja osaamista. Kombinatoriikan kurssi on rinnakkainen syksyn 2015 "Verkot"-kurssin kanssa, joten molempia voi suorittaa.

Esitietovaatimukset

Kurssi rakentuu kurssin "Johdatus yliopistomatematiikkaan" pohjalle, ja JYM-kurssin perustiedot riittänevät varsin pitkälle: alkeellinen joukko-oppi, kuvaukset, todistaminen sekä induktiotodistus (joissakin esimerkeissä jaollisuuden, kompleksilukujen tai potenssisarjojen alkeiden tunteminen saattaa olla vähän avuksi).

Luentoajat

Viikot 20-25 (opetusta jaksolla ti 17.5. - ke 22.6.). Luentoajat:

ti 12-14 viikoilla 20-21 E204 Physicum, viikot 22-25 D123 Exactum  

ke 14-16 viikoilla 20-21 E204 Physicum, viikot 22-25 D123 Exactum  

Ensimmäinen luento ti 17.5 klo 12-14 salissa E204 Physicum. Kurssiin liittyy laskuharjoituksia 2 t/v (ajat alla). Laskuharjoituksista saa (runsaasti) lisäpisteitä.

Kokeet

Kombinatoriikan kurssikoe järjestetään keskiviikkona 29.6 klo 12.15-14.45 salissa B123 (Exactum rakennus on silloin auki). Kombinatoriikan kurssin voi suorittaa lisäksi elokuun yleistentissa to 11.8. klo 10-14, sekä syksyn yleistenteissä 21.9 ja 14.12. Yleistentteihin tulee ilmoittautua weboodissa. Kokeissa saa olla mukana kaksipuolinen A4-kokoinen käsinkirjoitettu muistilappu, muttei laskinta.

Ke 22.6. myös pieni katsaus koealueeseen. Esimerkkeinä luennoijan laatima erilliskoe  sekä pieni kokoelma muiden laatimia Kombinatorikan/Diskreetin matematiikan kurssikokeita. (Huom.: näissä osittain eri koealue!)

Kurssikokeen 29.6.2016 epävirallinen tuloslista. Kombinatoriikan kursikoe 29.6.2016  sekä mallivastaukset . Kominatoriikan kesätentti 11.8.2016  sekä vastaavat mallivastaukset . Kominatoriikan  tentti 21.9.2016 sekä mallivastaukset

Kirjallisuus

Kurssi perustuu seuraaviin kurssimonisteisiin (tarkempi sisältö ja monisteiden kohdat käyvät ilmi allaolevasta luentopäiväkirjasta):

Heikki Junnila: Kombinatoriikka. (linkki löytyy täältä)

Anne-Maria Ernvall-Hytönen: Kombinatoriikka (kesä 2015) (linkki löytyy täältä)

Luentopäiväkirja

17.5.2016:  Käytännön järjestelyistä. Pari esimerkkiä kurssin aiheista: lukumäärän laskemisesta ja rekursiiviset lukujonot. (Luku 1: Joukot, kuvaukset ja relaatiot) Joukko-opin merkinnöistä. Karteesiset tulot. Relaatiot ja esimerkkejä näistä. Käänteisrelaatio ja yhdistetty relaatio. (Junnila: luku I.1, sivut 1-6)

18.5.2016: Kuvaus esimerkkinä relaatioista, injektio/surjektio/bijektio ja käänteiskuvaus, esimerkkejä. Osittainen järjestys relaationa. Luonnolliset luvut ja induktioaksiooma. Lause I.2.2. (Junnila: sivut 6-13)

24.5.2016: Äärellisen joukon ja alkioiden lukumäärän tarkkka määritelmä (erityisesti: määritelmässä esiintyvä luonnollinen luku on yksikäsitteinen). Äärellisten joukkojen ja alkioiden lukumäärän perusominaisuudet: yhdisteen ja erotuksen koko. (Junnila: sivut 13-15, sekä täydentävänä materiaalina sivut 29-32 monisteesta H. Junnila: Johdatus Diskreettiin Matematiikkaan).

25.5.2016: Äärellisen erillisen yhdisteen sekä karteesisen tulon koko. (Junnila: sivu 16, sekä  sivut 33-34 monisteesta H. Junnila: Johdatus Diskreettiin Matematiikkaan).  Esimerkki:  symmetrinen erotusjoukon koko. (Luku 2: Joukkojen koko ja laskemismenetelmiä.) Kokojen vertailu: Lemma II.1.1. (Junnila: sivu 27).

31.5.2016: Äärellisten joukkojen vertailu injektioiden/surjektioiden/bijektioiden avulla (Junnila: sivut 26-28). Laatikkoperiaate ja laskettuja esimerkkejä (Junnila: sivut 28-29). Lisäsovelluksena Dirichlet'n lause eli irrationaaliluvun approksimaatio rationaaliluvuilla (Ernvall-Hytönen: Esim. 9, sivu 10)

1.6.2016: Yleistetty laatikkoperiaate ja esimerkki (Junnila: sivut 30-31). Jonojen, kuvausten ja osajoukkojen lukumäärät. Tulojoukon ja potenssijoukon koko (Junnila: luku II.3, sivut 38-39)

7.6.2016: k-alkioisten osajoukkojen lukumäärä ja binomikertoimet, Pascalin kaava ja binomikertoimien lauseke. Esimerkkejä. Binomilause ja polynomien kertoimet. Kuvausten lukumäärä X:stä Y:hyn. (Junnila: sivut 40-44)

8.6.2016: Bijektioiden ja injektioiden lukumäärät X:stä Y:hyn. (Junnila: sivut 44-46). Tulkinta: k-permutaatioiden ja k-kombinaatioiden lukumäärät. (Junnila: sivu 58). Summa- ja erotusperiaattteen muotoilu. (Junnila: sivut 33-34)

14.6.2016: Summa- ja erotusperiaatteen todistus induktiolla (eri kuin monisteessa). Sovellusesimerkkejä: surjektioiden lukumäärä X:stä Y:hyn (Junnila, sivu 46). Epäjärjestysten lukumäärä (Junnila, sivut 58-60). (Luku 3: Rekursioyhtälöistä) Rekursioyhtälöitä motivoivia esimerkkejä

15.6.2015: Rekursioyhtälöt (RY) yleensä. Ratkaisumenetelmä ja ratkaisukaavoja: 2. kertaluvun vakiokertoimiset RY:t ja karakteristinen yhtälö. Tapaus A: kaksi eri reaalijuurta. Esimerkki: Fibonaccin luvut ja sovelluksia. Tapaus B: reaalinen kaksoisjuuri. (Junnila, sivut 85-88, Esimerkki III.3.5 karakteristisen yhtälön avulla). Luennoijan muistiinpanot 15.6.

21.6.2016: Tapaus C: kompleksinen konjugaattijuuripari. Korkeamman kertaluvun lineaarinen vakiokertoiminen RY: tapaus missä karakteristisella yhtälöllä eri reaalijuuria (vrt. Ernvall-Hytönen: Lauseet 18 ja 19; ei todisteta tällä kurssilla). Esimerkkejä RY:n ratkaisemisesta ja johtamisesta. Muistiinpanot 21.6 (jatkoa skannille 15.6.)

22.6.2016: Täydennyksiä: (A). Multinomikertoimet ja sovelluksia (Junnila: sivut 47-48). (B). Erillisten edustajien valinta joukkoperheesta ja Hallin lause (täydentävä materiaali Junnila: Verkot ; Hallin lause ei kuitenkaan todistettu luennoilla). Katsaus vanhoihin kurssikoetehtäviin. Kurssikoekatsauksen muistiinpanot

Koealueesta: generoivia funktioita ei ole käsitelty luennoilla, vaan rekursioyhtälöt ratkaistaan vastaavan karakteristisen yhtälön juurien avulla.

Alustava sisältö

Kurssin aikana on tarkoitus perehtyä ainakin seuraaviin aihepiireihin (järjestys saattaa vähän muuttua):

• Joukot, kuvaukset ja relaatiot (kertausta), - Hallin lause ja sen sovelluksia (mm. erillisten edustajien valinta)
• Lukumäärän laskeminen ja joukkojen koko: - permutaatiot, kombinaatiot ja osajoukkojen lukumäärä (binomikertoimet), - summan ja erotuksen periaate (inkluusio-ekskluusio periaate), - kyyhkyslakkaperiaate (laatikkoperiaate) ja sen sovelluksia
• Rekursiiviset yhtälöt ja generoivat funktiot: - rekursiiviset  yhtälöt ja niiden ratkaiseminen (mm. vakiokertoimiset lineaariset yhtälöt), Fibonaccin luvut  - generoivat funktioiden ja niiden määrääminen, - esimerkkejä ja sovelluksia

Laskuharjoitukset

Laskuharjoitukset viikoilla 21-25 (yhteensä 5 laskuharjoituskertaa). Tavoitteena on että laskuharjoitustehtävät ilmestyvät kotisivulle edellisen viikon torstaina. Lasketuista laskuharjoitustehtävistä saa lisäpisteitä seuraavan kaavan perusteella: joka laskuharjoituksesta 4-7 ruksia = +1 p., 2-3 ruksia = +1/2 p. Tähtitehtävien ratkaisusta saa 2 ruksia. Lisäpisteet ovat voimassa vuoden 2016 aikana. Maanantaisin (alk. ma 23.5.) klo 14-16 on 3. kerroksen käytävässä lisäksi laskuharjoitusten ohjausvuoro, jolloin voi kysyä neuvoja tehtäviin (ohjaajana on Sarianna Sallinen).

Tehtävät ja mallivastaukset

Harjoitus 1  Mallivastaukset 1

Harjoitus 2  (tehtävässä 2:5 lisävihje)  Mallivastaukset 2

Harjoitus 3  Mallivastaukset 3

Harjoitus 4 Mallivastaukset 4

Harjoitus 5  (viimeinen harjoitus) (tehtävässä 5:1 korjattu painovirhe)  Mallivastaukset 5

 Ilmoittautuminen laskariryhmiin alkaa torstaina 19.5. klo 10.00 weboodissa.

Ilmoittaudu kurssille

Unohditko ilmoittautua? Katso ohjeet täältä!