Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 24. 09. 2012 19:03
Pocet postupnosti {0,1}
Caute,
Mam jeden problém, s ktorým si neviem tak ľahko dat rady:
Koľko je postupností obsahujúcich len 0 a 1 takých, že
a) ich dĺžka je najviac 10 a neobsahujú dve po sebe idúce 1?
b) ich dĺžka je n a neobsahujú tri po sebe idúce 1?
Napadol ma princíp inklúzie exkluzie (zapojenia/vypojenia):
Všetky riešenia - "zlé riešenia"
Všetky riešenia sú v a) 
b) 2^n
horšie je zistiť tie zlé riešenia. Keby mam čisto len postupnosti dĺžky 5 tak nemohlo by to byť nejako takto ?
2^5 - (5-3 +1 nad 1)*2^(n-3)
Keď som však zmenil čisla pre veľkosť 3 alebo 4 (a možnosti som si "ručne" vypisal), nesedelo mi to. Som vôbec na dobrej ceste ? Nemôžte dať nejaký hint ?
Offline
#2 25. 09. 2012 23:52 — Editoval vanok (25. 09. 2012 23:58)
Re: Pocet postupnosti {0,1}
Ahoj ↑ zelo:,
Otazka a) sa da riesit empiricky pozovonim konstrukcie postupnosti vdaka "stromom"
Pozoruj toto
0
0 <
1
0 <
0
1<
1*
0
0 <
1
1 <
0*
1*<
1*
1 riesenie pre postupnosti dlzky 2
1+ 2=3 riesenia dlzky 3
Uz tu vidis ze pre postupnosti dlzky 2 mas jednu zlu postupnost ( zle postupnosti oznacil som s *)
pre postupnosti dlzky 3 mas 1 +2 =3 zle postupnosti
pre postupnosti dlzky 4 podobne sa ukaze , ze mas 1+2+4=7 zlych postupnosti
Poznamka 1: postupnost je vzdy materializovana cestou na grafe stromu.
Poznamka 2: je to sice ina metoda ako si chcel, ale sa mi zda velmi prirodzena
Ak zaroven tvoja postupnost musi splnovat podmienku b) tak upravis jednoducho moje riesenie
A ak je to iny nezavisly problem tak mozes " vytvorit analogicky" nejaku metodu na riesenie ( podobne ako v a) )
Srdecne Vanok
The respect, the politeness are essential qualities...and also the willingness.
Do not judge the other one.
Ak odpovedam na nejaku otazku. MOJ PRINCIP NIE JE DAT ODPOVED ALE UKAZAT AKO SA K ODPOVEDI DOSTAT
Offline
#4 26. 09. 2012 19:07
Re: Pocet postupnosti {0,1}
↑ zelo:
Nezda sa mi, ale mozno ty najdes nejaky suvis
Dobre pokracovanie.
Srdecne Vanok
The respect, the politeness are essential qualities...and also the willingness.
Do not judge the other one.
Ak odpovedam na nejaku otazku. MOJ PRINCIP NIE JE DAT ODPOVED ALE UKAZAT AKO SA K ODPOVEDI DOSTAT
Offline
#5 28. 09. 2012 17:14
Re: Pocet postupnosti {0,1}
Použiji princip dynamického programování.
Označím:
a(n) - počet posloupností délky n, jenž neobsahují 3 jedničky v řadě a na konci nemají jedničku
b(n) - počet posloupností délky n, jenž neobsahují 3 jedničky v řadě a na konci mají 1 jedničku
c(n) - počet posloupností délky n, jenž neobsahují 3 jedničky v řadě a na konci mají 2 jedničky
Pro posloupnosti délky 1 platí:
a(1) = 1
b(1) = 1
c(1) = 0
Pro n >= 1:
a(n+1) = a(n) + b(n) + c(n)
b(n+1) = a(n)
c(n+1) = b(n)
Stačí tedy vyřešit rekurenci.
Offline
#6 28. 09. 2012 19:27 — Editoval radekm (28. 09. 2012 19:28)
Re: Pocet postupnosti {0,1}
Rekurenci by šlo vyřešit pomocí generujících funkcí:
Předně je vidět, že
a(0) = 1 (prázdná posloupnost nemá na konci 1)
a(1) = 1
a(2) = 2
a dále
a(n) = a(n-1) + a(n-2) + a(n-3)
Označme A(x) generující funkci
Pro A(x) platí
Použitím rovnosti a(n) = a(n-1) + a(n-2) + a(n-3) dostaneme
a po rozdělení sumy
Abychom to vyřešili, musíme řady vyjádřit pomocí A(x). Začneme členem 
. Vytknutím x a změnou dolní meze sumy dostaneme
Zbylé dva členy vyjádříme podobně
Nyní to dosadíme do původní rovnice:
Rovnici vyřešíme pro A(x), čímž dostaneme generující funkci:
Polynom ve jmenovateli má ošklivé kořeny, takže explicitní vzorec je ošklivý. Explicitní vzorec je k dispozici v článku o Tribonacciho číslech (posloupnost začíná 0) - jedná se také o posloupnost A000073 (posloupnost začíná dvěma 0).
Offline