Sanan osajonojen lukumäärä

Varmistukseksi että laskut menee oikein, niin mitä saatte seuraavalle?

"OSAJONOJEN LUKUMÄÄRÄN LASKEMINEN"

(myös välit lasketaan merkeiksi). Itse saan 1545659216.

Ratkaisu: https://membolicsythod.home.blog/2020/02/29/sanan-osajonojen-lukumaara/

Lisäkysymyksen ensimmäisen kohdan vastaus on f_{n 2} - 1, missä f_k on k:s Fibonacci luku.
Suurin määrää saadaan selvästikin alternoivalla binäärijonolla, sillä aina kannattaa hypätä lähemmäksi, jotta saadaan enemmän kävelyjä (ja mikäli kaksi samaa merkkiä on peräkkäin aiheuttaa tämä toisen yli hyppäämisen edeltävästä merkistä (ja lähtö on -1 eli tyhjä, niin vaikka se olisi heti alussa, niin haittaa tulee)).
Alternoivia on kaksi 0101.... ja 1010.... Näille osajonojen määrä, merkataan sitä a(n), on selvästi yhtäsuuri, sillä toinen saadaan toisesta muuttamalla ykköset nolliksi ja nollat ykkösiksi.

Lasketaan nyt sanan 0101.... (päättyy joko 0 tai 1 riippuen n:n pariteetista) osajonot.
Induktioaskel kaavan todistuksessa menee samaan tyyliin kuin mikä viimeksikin oli missä ratkaisuun tuli Fibonacci luvut. Jaetaan osajonot kolmeen luokkaan:
- tyhjä jono
- 0:lla alkavat
- 1:llä alkavat

Jos osajono v alkaa nollalla, niin silloin loppu eli v[1:] on 101... (pituus n-1):n osajono, induktio-oletuksen mukaan näitä on f_{n 1}-1.
Jos alkaa ykkösellä, niin v[1:] taas on 010... (pituus n-2):n osajono, sillä ensimmäistä nollaa ei ole voitu käyttää, sillä alkoi ykkösellä ja niinkuin tuossa edelläkin se ensimmäinen ykkönen on voitu käyttää tai sitten ei, mutta se loppu on sen lopun osajono joka tapauksessa käytettiin se ensimmäinen ykkönen ekaan paaluun tai myöhemmin. Näitä on f_n - 1.
Siis yhteensä

a(n)
= 1 a_{n-1} a_{n-2}
= 1 f_{n 1} - 1 f_n - 1
= f_{n 2} - 1