#1 20. 04. 2016 18:56
Kombinatorika ( pocet permutaci )
Dobry den! Nijak mi nepodari pochopit tuto ulohu :
Určete počet permutací množiny {1, 2, . . . , n}, které neobsahují podposloupnost
a1, a2, a3, kde a1 < a3 < a2. (Např. permutace 2, 3, 5, 4, 1 je
zakázaná kvůli trojici 2, 5, 4).
Jestli ma nekdo nejaky nazor, budu vdacny za jakoukoliv radu! Diky!
Offline
- (téma jako vyřešené označil(a) byk7)
#2 20. 04. 2016 19:18 — Editoval byk7 (20. 04. 2016 19:50)
Re: Kombinatorika ( pocet permutaci )
Označme 
počet vyhovujících permutací n-prvkové množiny {1, 2, ..., n}. Přidejme nový prvek n+1 – ten může být na pozici 
, kde 
a první tři členy se zachovají, což dá [následující počet je chybný -->] 
nových vyhovujících permutací [dá to ((n+1)-3)*p(n)]. Nebo může být n+1 na pozici 
– prvky na pozice 
vybereš z {1, 2, ..., n} 
způsoby a zbytek pak uspořádáš libovolně.
Tedy se domnívám, že 
.
[netřeba -->] pro malá 
se to pak musí ošetřit zvlášť.
Příspěvky psané červenou barvou jsou moderátorské, šedá je offtopic.
Offline
#3 20. 04. 2016 19:29 Příspěvek uživatele Comrad byl skryt uživatelem Comrad.
nových permutací.#6 21. 04. 2016 16:40
Re: Kombinatorika ( pocet permutaci )
↑ byk7:
Obávám se, že počítáš s tím, že a1, a2, a3 značí první tři prvky v permutaci, ale podle "Např. permutace 2, 3, 5, 4, 1 je zakázaná kvůli trojici 2, 5, 4" a1, a2, a3 jsou prvky VYBRANÉ posloupnosti a tudíž nestačí, aby podmínka platila pro první tři prvky a zbytek by byl náhodně.
Offline
#7 21. 04. 2016 17:42
Re: Kombinatorika ( pocet permutaci )
↑ King: Hmm, jak říkáš, počítal jsem permutace, jejichž první tři členy splňují zadané nerovnosti.
Ale potom nerozumím asi zadání, to v každé vybrané, alespoň tříprvkové podposloupnosti mají platit nerovnosti ze zadání?
Příspěvky psané červenou barvou jsou moderátorské, šedá je offtopic.
Offline
#8 21. 04. 2016 22:21
Re: Kombinatorika ( pocet permutaci )
↑ byk7:
Podle zadání v permutaci nesmí existovat vybraná posloupnost, že a1<a3<a2. Dle příkladu v zadání podmínku nesplňuje 2, 3, 5, 4, 1 kvůli trojici 2, 5, 4. Takže pokud se například na druhé pozici vyskytuje 2, na páté 9, tak dál se nesmějí vyskytovat čísla mezi dvojkou a devítkou, jinak už by taková vybraná posloupnost existovala.
Offline