Binäärijonojen ykkösputket

Älä ota enää!

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.

minkkilaukku kirjoitti:

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.

Lue lisää

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