MAT282 Johdatus diskreettiin matematiikkaan
1. välikoe ke 20.10.1999 klo 8-11

1. 1. Luettele kaikki joukon $\{a,b,c\}$ ositukset (ekvivalenssirelaatiot). Montako ositusta voidaan yleisesti muodostaa $n$ alkion joukossa?
   2. Olkoon $A = \{2,3,4\}^2$. Piirrä Hasse-kaavio järjestysrelaatiosta $\preceq\; \subseteq A\times A$, missä
      
      $$(r,s) \preceq (r',s') \qquad \mbox{joss} \qquad r \leq r' \mbox{ ja } s \vert s'.$$
      
      
      (Merkintä $s \vert s'$ tarkoittaa, että kokonaisluku $s$ on kokonaisluvun $s'$ tekijä.)

2. 1. Kuinka monta sellaista viisimerkkistä ``sanaa'' voidaan muodostaa aakkoston {A, E, M, N, S} kirjaimista, joissa kirjain A esiintyy kaksi tai kolme kertaa ja kukin muista kirjaimista enintään kerran? Sanojen ei tarvitse olla suomenkielen äänneopin mukaisia: kelvollisia ovat siis esimerkiksi AAMEN, ASEMA ja AMSAA, mutta eivät MENSA eikä MASSA.
   2. Montako kokonaislukuratkaisua on epäyhtälöryhmällä:
      
      $$\left\{\begin{array}{l} \sum_{i=1}^5 x_i = 10,\\ 1 \leq x_i \leq 3, \quad i = 1,\dots,5? \end{array}\right.$$
      
      

3. Kokeessa on viisi monivalintatehtävää, joissa on kussakin viisi ratkaisuvaihtoehtoa (a,...,e). Opiskelija K tietää, että kaikkiin kysymyksiin on vastattava eri tavalla, mutta muuten hänellä ei ole mitään käsitystä oikeista vastauksista. Monellako tavalla K voi muodostaa vastausrivin niin, että siinä ovat kaikki vastaukset väärin? (Vihje: Tarkastele, monellako tavalla vastausrivin voisi muodostaa niin, että siinä olisi ainakin $i$. vastaus oikein, $i = 1,\dots,5$.)

4. Ratkaise 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.$$
   
   

Pisteytys: tehtävät 1 ja 2 á 8 pistettä, tehtävät 3 ja 4 á 7 pistettä, yhteensä 30 pistettä.