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]?
Binäärijonojen ykkösputket
6
<50
Vastaukset
- Anonyymi
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?- Anonyymi
Älä ota enää!
- Anonyymi
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: 17710Joo, 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.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".
Ketjusta on poistettu 0 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
Minä itkin kotona kun tajusin että
Pelkuruuteni takia kun en lähestynyt vaikka järjestit otollisen hetken ja myöhemmin huomasin lasittuneen katseesi miten111785Muistutus t-Naiselle.
Olet ilkeä ja narsistinen k-pää. Annat itsestäsi kiltin kuvan ulospäin kelataksesi ihmiset ansaan. Sitten päsmäröit, hau1511382- 721382
Ylen jälkiviisaat estotonta Kamala Harris suitsutusta
Kolme samanmielistä naikkosta hehkutti Kamala Harrisia ja haukkui Trumpia estottomasti. Nyt oli tarkoituksella valittu2951290- 251150
Oho! Varmistusta odotellaan.
Pitäneekö paikkansa? "🇺🇦Ukrainian drones hit a 🇷🇺Russian Tu-22M3 bomber at the Olenya airfield,"1151122Oiskohan se aika
Selvittää pää vihdoin ja viimein. Minun kaivattu ei todellakaan käy täällä ja piste. Ei ole mitään järkeä enää tuhlata t51039Mää oikeasti vielä kuolen
Tämän tilanteen takia. Minä tosissani yritin ja tiedän että tämä tilanne sattuu sinuunkin. Molemmat taidetaan olla niin42967Onko jotain sanottavaa vielä, nyt voi kertoa
Poistun kohta täältä ja unohdan ajatuksen naimisiin menosta. Mieheltä29889Kun Suomen uutisiin ei voi luottaa?
Kertoisitteko te uutismaailmasn perehtyneet ASIANTUNTIJAT nyt sitten sen, mihin voi?232848