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
63
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
Useita puukotettu Tampereella
Mikäs homma tämä nyt taas on? "Useaa henkilöä on puukotettu Tampereen keskustassa kauppakeskus Ratinan lähistöllä." ht2324421Kuka rääkkää eläimiä Puolangalla?
Poliisi ampui toistakymmentä nälkiintynyttä eläintä Puolangalla Tilalta oli ollut karkuteillä lähes viisikymmentä nälkii742862- 472403
Meneeköhän sulla
oikeasti pinnan alla yhtä huonosti kuin mulla? Tai yhtä huonosti mutta jollain eri tyylillä? Ei olisi pitänyt jättää sua431687- 781379
Lähetä terveisesi kaipaamallesi henkilölle
Vauva-palstalta tuttua kaipaamista uudessa ympäristössä. Kaipuu jatkukoon 💘691080PS uusimman gallupin rakettimainen nousija
https://yle.fi/a/74-20170641 Aivan ylivoimaisesti suurin kannatuksen nousu PS:lle. Nousu on alkanut ja jatkuu 2 vuoden137919- 64860
Sellainen tunne sydämessä
Että nainen olet kaivannut minua. Tai sanonko että oikeastaan koet sitä samaa nostalgiaa, kaipuuta ja mukavia muistoja,86854Annan meille mahdollisuuden
Olen avoimin mielin ja katson miten asiat etenevät. Mutta tällä kertaa sun on tehtävä eka siirto.Sen jälkeen olen täysil53832