Johdatus diskreettiin matematiikkaan, syksy 2000
Harjoitus 3, 10.-12.10.

1. Monellako tavalla 6 identtistä palloa voidaan värittää kolmella värillä? Entä jos pallot ovat toisistaan erottuvia (esim. erikokoisia)? Moniko värityksistä sisältää kaikkien kolmen värisiä palloja, kun pallot ovat (a) identtisiä (b) erottuvia?

2. Monenko ei-negatiivisten kokonaislukujen muodostaman kolmikon $(k,l,m) \in {\mathbf N}^3$ kautta kulkee avaruuden ${\mathbf R}^3$ taso $\{(x,y,z) \in {\mathbf R}^3 \;\vert\; x + y + z = 10\}$?

3. Montako erilaista mahdollista pelitilannetta on 3$\times$3-jätkänshakissa (ristinollassa) kahden siirtoparin jälkeen? (Tilanteiden samaistamista pelilaudan kiertojen ja peilausten avulla ei tarvitse tarkastella.)

4. Montako ositusta (ekvivalenssirelaatiota) voidaan määritellä joukossa $A = \{a,b,c,d\}$? Luettele ne.

5. 1. Kuinka monta anagrammia voidaan muodostaa sanasta TIIVITAAVI? (Kaksi sanaa ovat anagrammeja, jos niissä on samat kirjaimet eri järjestyksessä. Tässä tehtävässä anagrammien ei tarvitse olla suomenkielen äänneopin mukaisia.)
   2. Kuinka monella tavalla luennoija (PO) ja neljä teletappia (Tiivi-Taavi, Hipsu, Laa-Laa ja Pai) voidaan ryhmitellä kolmeen ryhmään niin, että mikään ryhmistä ei ole tyhjä?

6. Biologisen perimäinformaation kantajina toimivia nukleotidijonoja voidaan tarkastella nelikirjaimisen aakkoston $\{A, G, T, C\}$ sanoina, joiden kirjaimet vastaavat nukleotidiemästen adeniini, tymiini, guaniini ja sytosiini esiintymiä. Montako erilaista 6 merkin mittaista nukleotidijonoa on olemassa? Moniko näistä sisältää ainakin yhden kappaleen kutakin nukleotidiemästä? Entä montako on sellaista, joissa ei mikään nukleotidiemäs esiinny kahdessa vierekkäisessä positiossa?

7. Todista oikeaksi kokonaislukujen potenssien binomikerroinesityksiä koskeva muunnoskaava:
   
   $$n^p = \sum_{r=1}^p S(p,r)r!{{n}\choose{r}}.$$
   
   
   (Vihje: Tarkastele $n$-alkioisesta perusjoukosta muodostettujen $p$-jonojen erilaisia valintatapoja.) Lausu potenssi $k^3$ binomikertoimien ${{k}\choose{i}}$, $1 \leq i \leq 3$, summana. Osoita em. esitystä ja harjoitusten 2 tehtävän 4(c) summaussääntöä käyttäen todeksi summakaava
   
   $$1^3 + 2^3 + \cdots n^3 = \frac{1}{4}n^2(n+1)^2.$$