MAT282 Johdatus diskreettiin matematiikkaan (3 ov)
Loppukoe ke 24.1.2001 klo 8-12

1. Piirrä Hasse-kaavio osittainjärjestetystä joukosta $(D_{60}, \vert)$, missä perusjoukkona ovat luvun 60 kokonaislukutekijät $D_{60} = \{d \in \mathbf{N}\;:\; d \vert 60\}$, ja järjestysrelaationa kokonaislukujen jaollisuusrelaatio: $m\vert n$, jos luku $m$ on luvun $n$ tekijä.

2. Tentissä on 5 tehtävää, joiden tarkastaminen halutaan jakaa 3 tarkastajan (A, B, C) kesken niin, että jokainen saa tarkastaakseen vähintään yhden tehtävän. Monellako tavalla ositus voidaan tehdä, kun:
   1. Tehtävien numeroinnilla ei ole väliä, so. ollaan kiinnostuneita vain siitä, montako tehtävää kukin tarkastajista A, B, C saa lukeakseen.
   2. Tehtävien numerointi on tärkeä, mutta sen sijaan sillä kuka tarkastaa minkä tehtäväjoukon ei ole merkitystä.
   3. Sekä tehtävien numerointi että tarkastajien henkilöllisyys otetaan huomioon.

3. Tentissä on 5 tehtävää, joista kustakin voi saada 0-12 pistettä. Monellako tavalla tentistä voi saada tulokseksi tasan 30 pistettä niin, että jokaisesta tehtävästä saa vähintään 1 pisteen? (Tehtävien numerointi otetaan huomioon, so. esimerkiksi pistejakauma 1-2-3-12-12 on eri kuin pistejakauma 12-12-3-2-1.) -- Jos sinulla ei ole laskinta, ratkaisuksi riittää asianmukainen binomikerroinlauseke.

4. Todista, että yhtenäinen verkko $G = (V, E)$, $\vert V\vert \geq 2$, on kaksijakoinen (so. $\chi(G)=2$), jos ja vain jos $G$ ei sisällä parittomia syklejä, so. jos mikään $G$:n aliverkko ei ole muotoa $C_{2k+1}$, $k \geq 1$.

5. Tarkastellaan $n$ alkion sekoituksia (engl. derangements), so. permutaatioita $\sigma: \{1,\dots,n\} \rightarrow \{1,\dots,n\}$, joilla $\sigma(i) \neq i$ kaikilla $i = 1,\dots,n$. Osoita seulayhtälöä käyttäen, että $n$ alkion sekoituksia on kaikkiaan
   
   $$d_n = n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\dots +(-1)^n\frac{1}{n!}\right)$$
   
   
   kappaletta. (Lisätieto, ei liity tehtävän ratkaisemiseen: Kaava osoittaa, että sekoitusten määrä lähestyy $n$:n kasvaessa nopeasti arvoa $n!\,e^{-1}$. Siten on satunnaisesti valittu $n$ alkion permutaatio sekoitus likimäärin todennäköisyydellä $1/e$.)

Pisteytys: Kukin tehtävä 12 pistettä, yhteensä 60 pistettä.