Johdatus diskreettiin matematiikkaan, syksy 2000
Harjoitus 5, 24.-26.10.

1. Tasoon piirretään $n$ ei-yhdensuuntaista suoraa niin, että mitkään kolme niistä eivät leikkaa samassa pisteessä. (So. jokainen ``uusi'' suora leikkaa kaikki ``vanhat'' suorat, kunkin eri pisteessä.) Merkitään $a_n$:llä näin muodostuvien erillisten tasoalueiden määrää: siis $a_0 = 1$, $a_1 = 2$, $a_2 = 4$, $a_3 = 7$ jne. Muodosta perusteltu rekursioyhtälö lukujonolle $a_n$ ja ratkaise se.

2. Ratkaise generoivia funktioita käyttäen rekursioyhtälö:
   
   $$\left\{\begin{array}{l} a_0 = 0, \quad a_1 = 1,\\ a_n = a_{n-1} + 6a_{n-2}+2^n, \quad n \geq 2. \end{array}\right.$$
   
   

3. Todista generoivia funktioita käyttäen oikeaksi seuraava binomikerroinyhtälö (ns. Vandermonden konvoluutio):
   
   $$\sum_{k=0}^n {{r}\choose{k}}{{s}\choose{n-k}} = {{r+s}\choose{n}}.$$
   
   
   (Vihje: $(1+x)^r(1+x)^s = (1+x)^{r+s}$.) Keksitkö tulokselle myös kombinatorisen todistuksen?

4. Montako kokonaislukuratkaisua on yhtälöllä $a+b+c=10$, kun vaaditaan että kunkin muuttujan arvo on vähintään 2 ja enintään 4?

5. Kombinaatioteknologian tiedekunnan tiedekuntaneuvostoon kuuluu yhteensä 9 jäsentä kolmesta ryhmästä: professorit, muu henkilökunta ja opiskelijat. Monellako tavalla neuvosto voidaan muodostaa niin, että jokaisesta ryhmästä on siinä ainakin yksi edustaja, mutta millään ryhmällä ei ole ehdotonta enemmistöä? (Vihje: Sovella geometrisen sarjan summakaavaa $1+x+x^2+\cdots+x^n = \frac{1-x^{n+1}}{1-x}$ ja harjoitusten 4 tehtävän 5 tuloksia.)

6. Laatikossa on 30 sinistä, 40 punaista ja 50 vihreää palloa. Montako erilaista 70 pallon kokoelmaa laatikosta voidaan muodostaa? (Vihje: Kuten edellä.)

7. Yliopiston ruokajonossa on satunnaisessa järjestyksessä $2n$ opiskelijaa. Ruoka-annos maksaa 10 mk, ja puolella opiskelijoista on mukanaan tasaraha, puolella taas 20 mk seteli. Ruokalan vaihtokassa on aluksi tyhjä. Mikä on todennnäköisyys, että kassa pystyy palvelemaan kaikki jonossa olevat opiskelijat, ilman että vaihtorahat loppuvat kesken? (Vihje: Merkitään $s_n$:llä sellaisten suotuisten jonojärjestysten määrää, joissa vaihtokassa pysyy ei-negatiivisena koko jonon ajan. Selvästi on $s_1 = 1$. Arvo $s_n$, $n > 1$, voidaan päätellä esim. tarkastelemalla, monenko opiskelijaparin jälkeen vaihtokassa menee nollaan ensimmäisen kerran. Jos kassa nollautuu vasta lopussa, niin ensimmäisellä opiskelijalla on kymppi, viimeisellä kaksikymppinen, ja koko väliajan kassa on aidosti positiivinen: tällaisia jonojärjestyksiä on $s_{n-1}$ kappaletta. Muussa tapauksessa kassa nollautuu ensimmäisen kerran $k$:n opiskelijaparin jälkeen, missä $1 \leq k \leq n-1$. Tällöin...)

Kurssin ensimmäisen välikokeen 25.10. koealue on harjoituksissa 1-5 käsitellyt asiat. Henkilöt, joille 25.10. koepäivä ei tenttien päällekkäisyyksien takia käy, voivat ilmoittautua luennoijalle keskustellakseen kokeen korvaamisesta 15.11. pidettävällä loppukokeella.