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).

Vastaa

Täytä tietosi alle tai klikkaa kuvaketta kirjautuaksesi sisään:

WordPress.com-logo

Olet kommentoimassa WordPress.com -tilin nimissä. Log Out /  Muuta )

Google photo

Olet kommentoimassa Google -tilin nimissä. Log Out /  Muuta )

Twitter-kuva

Olet kommentoimassa Twitter -tilin nimissä. Log Out /  Muuta )

Facebook-kuva

Olet kommentoimassa Facebook -tilin nimissä. Log Out /  Muuta )

Muodostetaan yhteyttä palveluun %s