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

1. Olkoot $n \geq r \geq k \geq 1$ kokonaislukuja. Todista oikeiksi seuraavat binomikerroinyhtälöt:
   
   $${{n}\choose{k}} = \frac{n}{k}{{n-1}\choose{k-1}},\qquad {{n}\choose{r}}{{r}\choose{k}} = {{n}\choose{k}}{{n-k}\choose{r-k}}.$$
   
   
   Anna jälkimmäiselle yhtälölle myös kombinatorinen tulkinta.

2. 1. Muodosta seuraavien puiden Prüfer-koodit:
      
      Minkä 8-solmuisen puun Prüfer-koodi on (2,7,1,8,2,8)?
   2. Osoita, että jokaisen vähintään kaksisolmuisen puun $T$ väriluku on $\chi(T) = 2$.
   3. Osoita, että jos puussa on solmu, jonka asteluku on $d\geq 1$, niin siinä on myös vähintään $d$ lehteä.

3. 1. Piirrä verkko, jonka solmuina ovat nelialkioisen perusjoukon $\{1,2,3,4\}$ kaikki kaksialkioiset osajoukot, ja solmujen $X$ ja $Y$, $X \neq Y$, välillä on kaari, jos ja vain jos $X \cap Y \neq \emptyset$. Osoita, että näin saatu verkko on planaarinen.
   2. Osoita, että vastaavalla tavalla viisialkioisen perusjoukon $\{1,2,3,4,5\}$ kaksialkioisista osajoukoista muodostettu verkko ei ole planaarinen.

4. A:n tasavallan presidentinvaalien ääntenlaskussa on syntynyt kiperä tilanne: 370 Aku Ankalle (joka ei ollut ehdokkaana) annettua ääntä pitäisi jakaa ehdokkaiden B, G ja N kesken niin, että ehdokas B saa vähintään 200 ääntä, ehdokas G 100-199 ääntä ja ehdokas N enintään 10 ääntä. Monellako tavalla toivottu akuankkaäänten ositus voidaan suorittaa?

5. Tarkastellaan nelimerkkisen aakkoston $\{A,B,C,D\}$ merkkijonoja. Merkitään $a_n$:llä sellaisten $n$-merkkisten jonojen määrää, jotka sisältävät parittoman määrän $A$-merkkejä. (Siten $a_0=0$, $a_1=1$, $a_2=6$ jne.) Osoita, että lukuja $a_n$ yhdistää rekursioyhtälö $a_{n+1} = 2a_n+4^n$, ja ratkaise tästä luvut $a_n$ suljetussa muodossa. (Vihje: Osita $(n+1)$:n mittaiset merkkijonot sen mukaan, alkavatko ne $A$:lla vai jollain muulla merkillä.)

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