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
Voitaisko olla kavereita?
Haluaisin aloittaa puhtaalta pöydältä sinun kanssasi, tabula rasa. Minä lopetan sinun perääsi haikailun, ja sitten sinäk275175Deodoranttiteollisuus
Annan ilmaisen vinkin. Kyseinen teollisuus voisi alkaa valmistaa kuolleen ruumiin hajua. Olisi varma hittituote, ainakin133098Rukoilimme Länsimuurilla 2000 vuoden jälkeen, Jumalamme oli antanut meille kaiken takaisin
Western Wall, In our Hands. 55th Para. https://www.youtube.com/watch?v=u4BJAppyCSo https://en.wikipedia.org/wiki/55th_151288Kerro kaivattusi
Jokin tapa/piirre mikä sinua viehättää ja mistä hän voisi myös tunnistaa itsensä.491201Oulaisten kaupunki tuomittiin maksamaan korvauksia
Mikäs juttu tämä on? Kaupunki syyllistänyt useamman vuoden koneyrittäjiä ja nyt tuomittu.231114PURRA TULEE !
Valtiovarainministeri Riika Purra, joka on lisäksi varapääministeri ja perussuomalaisten puheenjohtaja, tulee puoluesiht141982Onko MOT tulossa Ähtärin valtuuston kokoukseen?
Esityslistan mukaan Ähtärin kaupunginvaltuuston valtapuolueet aikovat maanantaina estää tilintarkastajan laatiman raport43919- 116885
- 37834
- 142763