Matematické Fórum

Comrad · 20. 04. 2016 18:56

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!

byk7 · 20. 04. 2016 19:18 — Editoval byk7 (20. 04. 2016 19:50)

Označme $p_n$ 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 $a_i$ , kde $i>3$ a první tři členy se zachovají, což dá [následující počet je chybný -->] $(n-3)p_n$ nových vyhovujících permutací [dá to ((n+1)-3)*p(n)]. Nebo může být n+1 na pozici $a_2$ – prvky na pozice $a_1,a_3$ vybereš z {1, 2, ..., n} $\tbinom{n}{2}$ způsoby a zbytek pak uspořádáš libovolně.

Tedy se domnívám, že
$p_{n+1}=(n-\color{red}\mathbf{2}\color{black})p_n+\binom{n}{2}(n-2)!$
$p_3=1$ .

[netřeba -->] pro malá $n$ se to pak musí ošetřit zvlášť.

byk7 · 20. 04. 2016 19:42

↑ Comrad:

V argumentaci jsem udělal jednu chybu, vidíš ji? :-)

byk7 · 20. 04. 2016 19:48

↑ Comrad:

Chybu už ↑ jsem: označil. Přidání nového prvku mi dá $\bigl((n+1)-3\bigr)p_n$ nových permutací.

King · 21. 04. 2016 16:40

↑ 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ě.

byk7 · 21. 04. 2016 17:42

↑ 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í?

King · 21. 04. 2016 22:21

↑ 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.

Matematické Fórum

#1 20. 04. 2016 18:56

Kombinatorika ( pocet permutaci )

#2 20. 04. 2016 19:18 — Editoval byk7 (20. 04. 2016 19:50)

Re: Kombinatorika ( pocet permutaci )

#3 20. 04. 2016 19:29 Příspěvek uživatele Comrad byl skryt uživatelem Comrad.

#4 20. 04. 2016 19:42

Re: Kombinatorika ( pocet permutaci )

#5 20. 04. 2016 19:48

Re: Kombinatorika ( pocet permutaci )

#6 21. 04. 2016 16:40

Re: Kombinatorika ( pocet permutaci )

#7 21. 04. 2016 17:42

Re: Kombinatorika ( pocet permutaci )

#8 21. 04. 2016 22:21

Re: Kombinatorika ( pocet permutaci )

Zápatí