Binääriblokit

Väritetään $n$ :n peräkkäisen ruudun rivistä osa mustiksi ja lasketaan millaiset putket väritettyjä tuli. Esim:

n=10, värityksestä muodostuu putket [2, 1, 3]

Yhteensä erilaisia värityksiä on $2^n$ , sillä jokainen ruutu voidaan joko värittää tai jättää tyhjäksi (vrt. binääriluvut $< 2^n$ ), mutta kysymykset koskevat värityksestä muodostuvia putkia. Sanotaan putkien pituuksista koottua vektoria putkityypiksi. Yo. esimerkissä putkityyppi on [2, 1, 3].

a) Kuinka monta erilaista putkityyppiä voidaan $n$ :n ruudun rivistä muodostaa?
b) Olkoon rivin pituus $n$ . Kuinka moni eri väritys tuottaa putkityypin [ $k_1, k_2, \dots k_m$ ]?

Mahdolliset väritykset ja putkityypit, n = 1, 2, 3, 4

Ratkaisu

a)

Putkityyppi $[k_1, k_2, \dots, k_m]$ on mahdollinen muodostaa, mikäli se mahtuu $n$ -riviin. Jokaisen putken välissä on oltava vähintään $1$ tyhjä ruutu ja välejä on $m-1$ , joten se mahtuu tasan silloin kun

$\begin{aligned} m - 1 + \sum_{j=1}^m k_j \leq n \end{aligned}$

Määritellään lukujonot $a_n$ ja $b_n$ seuraavasti

$\begin{aligned} a_n = \#\{(k_1, k_2, \dots, k_m) \hspace{.3cm} | \hspace{.3cm} m - 1 + \sum_{j=1}^m k_j \leq n \} \\ b_n = \#\{(k_1, k_2, \dots, k_m) \hspace{.3cm} | \hspace{.3cm} m - 1 + \sum_{j=1}^m k_j = n \} \end{aligned}$

eli $b_n$ laskee sellaiset putkityypit, joita ”ei enää voi pidentää” ja $a_n$ on kysytty jono.

Huomataan, että $b_n$ itse asiassa laskee $n-$ pituisia binäärijonoja, joissa ei ole yli yhden pituisia nollaputkia ja jotka alkavat ja päättyvät ykköseen. Näiden lukumäärä voidaan laskea seuraavan graafin $n-1$ -kävelyjen solmusta A solmuun A määränä.

Solmuja voidaan ajatella tiloina seuraavasti: A=”viimeksi on tullut ykkönen”, B=”viimeksi on tullut nolla”, C=”on tullut kahden nollan putki” . Tila C on hylkäävä, siitä ei pääse enää mihinkään. (Voi myös ajatella, että C:stä on siirtymä vain itseensä; todennäköisyydellä 1, jos graafi mielletään Markovin ketjuksi.) Aloitetaan tilasta A, sillä jonon täytyy alkaa ykkösellä, joten voidaan olettaa, että yksi ykkönen on jo tullut. Kävelyn täytyy myös päättyä tilaan A, sillä viimeinen numero halutaan olevan ykkönen.

Se, että näin todella saadaan haluttu lukumäärä, nähdään esimerkiksi ajattelemalla graafia Markovin ketjuna, jossa tilojen A ja B siirtymät tapahtuvat molemmat todennäköisyydellä $\frac{1}{2}$ ja tilasta C on itsesiirtymä todennäköisyydellä $1$ . Näin saadaan todennäköisyys, että binäärijono on kysytynlainen (ks. tilojen selitykset kuvatekstissä). Tämä muutetaan lukumääräksi kertomalla kaikkien $n-1$ -pituisten binäärijonojen lukumäärällä eli $2^{n-1}$ :llä.

Lasketaan siis vierekkäisyysmatriisin $n-1$ :s potenssi diagonalisoimalla

$\begin{aligned} \left[ \begin{array}{ccc} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 0 & 0 \end{array} \right] ^{n-1} = \left[ \begin{array}{ccc} -1 & \frac{1-\sqrt 5}{2} & \frac{1+\sqrt 5}{2} \\ * & * & * \\ * & * & * \end{array} \right] \left[ \begin{array}{ccc} 0 & & \\ & \left( \frac{1-\sqrt 5}{2} \right)^{n-1} & \\ & & \left( \frac{1+\sqrt 5}{2} \right)^{n-1} \end{array} \right] \left[ \begin{array}{ccc} 0 & * & * \\ -\frac{1}{\sqrt 5} & * & * \\ \frac{1}{\sqrt 5} & * & * \end{array} \right] \end{aligned}$

Tämän alkio paikassa (0, 0) antaa luvun $b_n$ . Saadaan

$\begin{aligned} b_n = \frac{1}{\sqrt 5} \left ( \frac{1+\sqrt 5}{2} \right)^n - \frac{1}{\sqrt 5} \left ( \frac{1-\sqrt 5}{2} \right)^n \end{aligned}$

joten $b_n$ on kuuluisa Fibonaccin lukujono $f_n =f_{n-1} + f_{n-2}, f_1=1, f_2 = 1$ .

Ratkaistaan sitten $a_n$ . Koska $n+1$ -pituiseen riviin mahtuvalle putkityypille $(k_1, k_2, \dots, k_m)$ pätee joko $m - 1 + \sum_{j=1}^m k_j \leq n$ tai $m - 1 + \sum_{j=1}^m k_j = n+1$ , niin nähdään rekursio

$\begin{aligned} a_{n+1} = a_n + b_{n+1} \end{aligned}.$

Osoitetaan nyt induktiolla, että $a_n = f_{n+2}$ . Perustapaukset $a_0 = 1$ ja $a_1 = 2$ nähdään helposti luetteloimalla. Induktioaskel saadaan suoraan edellä olleesta rekursiosta, sillä, jos oletetaan $a_n = f_{n+2}$ , niin

$\begin{aligned} a_{n+1} = a_n + b_{n+1} = f_{n+2} + f_{n+1} = f_{n+3}. \end{aligned}$

b)

Olkoon putkityyppi [ $k_1, k_2, \dots k_m$ ]. Merkitään väritettyjen ruutujen määrää $S = \sum_{j=1}^m k_j$ . Kysymys voidaan muotoilla toisin: Asetetaan $n-S$ tyhjää ruutua jonoon ja kysytään kuinka monella tavalla näiden väliköistä (ja päädyistä) voidaan valita $m$ kappaletta, joihin putkityypin putket (järjestyksessä) asetellaan. Välikköjä ja päätyjä on $n-S-1 + 2 = n-S+1$ kappaletta, joten vastaus on

$\begin{aligned} {n-S+1} \choose {m} \end{aligned}.$

Huomioita

Jonon $b_n$ voi todeta Fibonacci jonoksi myös huomaamalla rekursioyhtälön $b_n = b_{n-1} + b_{n-2}$ (joko suoraan graafista tai matriisien kertolaskusta).

Binääriblokit

Ratkaisu

a)

b)

Huomioita

Julkaissut membolic

Jätä kommentti Peruuta vastaus

Ratkaisu

a)

b)

Huomioita

Jaa:

Aiheeseen liittyy

Julkaissut membolic

Jätä kommentti Peruuta vastaus