#1 07. 12. 2013 17:42
Množiny, kombinatorika
Ahoj lidi. Připravuji se na zkoušky a nemůžu za žádnou cenu vymyslet tenhle příklad.
pomohl by mi někdo prosím? i postup atd. Budu moc ráda, děkuji :)
Označme množinu všech ternárních řetězců délky n, které neobsahují faktor (podřetězec)
"22", jako An. Dále nechť Bn značí množinu všech takových řetězců, které neobsahují ani
faktor "21" a navíc nekončí dvojkou.
Určete kolik nejvýše dvojek mohou obsahovat řetězce z An a řetězce z Bn.
Kombinatorickou úvahou pak odvoďte nerekurentní předpis pro velikosti an = |An| a
bn = |Bn|
Offline
#3 09. 12. 2013 09:57 — Editoval Frager. (09. 12. 2013 10:26)
#4 09. 12. 2013 14:36
Re: Množiny, kombinatorika
no pokud mi nic neuniká, An může klidně vypadat jako 2x2x2x2x2x2x2... a hustěji v něm dvojky nebudou. Tedy počet dvojek v An bude horní celá část z n/2.
Řetězec který neobsahuje 22 ani 21 stále ještě může být 202020202020... a pokud musí končit nulou, pak je počet dvojek dolní celá část z n/2.
Možná jsem natvrdlej, ale zase nechápu zadání - pod |An| bych si představil délku řetězce An, což je ovšem n, takže to asi nebude ono. Nevím teď, jestli chceš rekurentní výraz pro počet dvojek v řetězci (viz výše) nebo počet všech řetězců splňujících zadání, nebo ještě něco jiného...
Offline
#6 10. 12. 2013 01:15
Re: Množiny, kombinatorika
↑ hribayz: a to an = |An| to je kolik je takových řetězců v závislosti na n.
Jinak ta horní a dolní celá část je správně. Teď jsem si to ověřila a není to nic těžkého.
Tu druhou polovinu bys hrybajz nevedel? :) Jinak promiň jestli otravuju...
Offline
#7 10. 12. 2013 18:02
Re: Množiny, kombinatorika
druhá polovina:
Dospěla jsem k tomuhle prozatim:
pro An - (rozložení na možnosti znaků na určitém indexu)
Lze představit jako strom:
pro n=1 -> 3 {0,1,2}
pro n=2 -> 8 {(první místo 3, druhé místo 3) - tam kde jsou 2 dvojky (1 případ) nebolli 3,2,3}
pro n=3 -> 22 {3 -> 3,2,3 ; 2-> 3,3 ; 3-> 3,2,3}
pro n=4 -> 60 {3 -> 3,2,3 ; 2-> 3,3 ; 3-> 3,2,3....}
pro n=5 -> 164...
pro n=6 -> 448..
pro n=7 ->1224..
pro rozepsání, jsem přišla úvahou na to, že např u
A5 = (A4+A3)osmiček "[počtu osmiček, neboli 3,2,3]" x2
+
A5 = (A4+A3)šestek "[počtu šestek, neboli 3,3]" x2
= těch 164, to je ale rekurentně a nedotažené...
Věděl by někdo jak to bude nerekuretně a dobře? :)
Offline