Väritetään n:n peräkkäisen ruudun rivistä osa mustiksi ja lasketaan millaiset putket väritettyjä tuli. Esim (1=väritetty, 0=tyhjä):
0110010111 ---> [2, 1, 3]
Kutsutaan tätä putkien pituuksista koottua vektoria värityksen putkityypiksi.
a) Kuinka monta erilaista putkityyppiä voidaan n:n ruudun rivistä muodostaa?
b) Olkoon rivin pituus n. Kuinka moni eri väritys tuottaa putkityypin [k1, k2, ..., k_m]?
0110010111 ---> [2, 1, 3]
Kutsutaan tätä putkien pituuksista koottua vektoria värityksen putkityypiksi.
a) Kuinka monta erilaista putkityyppiä voidaan n:n ruudun rivistä muodostaa?
b) Olkoon rivin pituus n. Kuinka moni eri väritys tuottaa putkityypin [k1, k2, ..., k_m]?
Vastaukset 6
Vanhimmat
Joo. Kaljalla on ihmeitä tekevä voima.
Kutsutaan putkityyppiä (ja väritystä) maksimaaliseksi, jos siinä mitään putkea ei voi pidentää yhdistämättä putkia.
Esim. 11011101 on maksimaalinen, mutta 10011 ei ole, sillä se voidaan pidentää 10111:ksi tai 11011.
Toisin sanoen jokaisen putken välissä on tasan yksi tyhjä ja päissä ei ole tyhjiä. Tämä voidaan putkityypille [k1, k2,..., km] myös ilmaista yhtälöllä
m - 1 k1 k2 ... km = n
Olkoon n edelleen rivin pituus. Valitaan putkityyppi satunnaisesti. Huom! ei siis väritystä vaan valitaan mahdollisten putkityyppien tasajakaumasta. Kysymys kuuluu:
c) Mikä on todennäköisyys että tyyppi on maksimaalinen? Mitä lukua tämä lähenee, kun n menee äärettömään?
Otetaan sitten väritysten tasajakauma ja kysytään:
d) Mikä on värityksen pisimmän putken odotusarvo.
Voidaanhan tämä toki kysyä myös putkityyppien tasajakaumalle:
e) Mikä on putkityypin (valitaan mahdollisten putkityyppien tasajakaumasta) suurimman alkion odotusarvo?
Älä ota enää!
a) Määrät saadaan erittäin monikäyttöisestä sarjasta: https://oeis.org/A000071
(Ekaa nollaa lukuunottamatta?)
n
0: 0
1: 1
2: 2
3: 4
4: 7
5: 12
6: 20
7: 33
8: 54
9: 88
10: 143
11: 232
12: 376
13: 609
14: 986
15: 1596
16: 2583
17: 4180
18: 6764
19: 10945
20: 17710
Joo, itse asiassa ykköstäkään ei tarvitse vähentää, kun ottaa mukaan myös tyhjän putkityypin [] (ja onhan se mukaan otettava, sillä se tulee tyhjästä värityksestä 00...0).
Esim. n=1:lle on kaksi kappaletta [] ja [1]. Ja nollalla vain [] eli yksi kappale, eli sekin toimii.
Tässä kuinka minä sen alunperin laskin: https://membolicsythod.home.blog/2019/12/10/binaariblokit/
Mutta rekursion noille kysytyille lukumäärille (tuolla merkitty a_n) näkee myös ilman b_n:iä ja graafeja/automaatteja näin:
Olkoon rivin pituus n 1. Lasketaan mahdolliset putkityypit kahdessa osassa: ensin sellaiset, joiden ensimmäinen alkio on 1 ja sitten sellaiset, joiden ensimmäinen alkio > 1. Ensimmäisessä tapauksessa loppu putkityyppi [k_2, ... , k_m] on sellainen joka mahtuu n-2:n pituiseen riviin (koska käytetään korkeintaan 2 ruutua: se yksi väritetty ja sen oikealla puolella oleva pakollinen tyhjä). Jälkimmäisessä tapauksessa putkityyppi [k_1-1, k_2, ..., k_m] on sellainen joka mahtuu n-1:n ruudun riviin (vain yksi väritetty poistetaan alusta).
Jokainen putkityyppi saadaan jommasta kummasta tapauksesta ja kaikki näin muodostetut ovat eri vektoreita, joten haluttu Fibonacci-rekursio on todistettu ja riittää tutkia alkuehdot, mikä jo tehtiinkin.
Ai niin nyt unohtu itseltänikin se tyhjä putkityyppi tuossa todistuksessa, kun oletin, että sillä on ensimmäinen alkio! Se voidaan ottaa mukaan jälkimmäiseen kategoriaan (ja sovitaan, että jos ensimmäinen alkio on olemassa vähennetään siitä 1). Esim. kun n=4 niin ne menee näin
n=2:lle putkityypit ovat: {[], [1], [2]}
n=3:lle putkityypit ovat: {[], [1], [2], [3], [1,1]}
{[], [1], [2], [3], [4] [1,1], [1,2], [2,1] }
= {[1], [1, 1], [1, 2]} U {[], [1 1], [2 1], [3 1], [1 1,1]}
= "n=2:lle ykkönen lisätty vektorin alkuun" U "n=3:lle lisätty ykkönen vektorin ensimmäiseen komponenttiin, mikäli olemassa".