Matematické Fórum

nordec · 04. 04. 2009 14:45

Poraďte prosím, co s tím? Tento příklad nějak moc nechápu:

Zadání: Řekneme, že permutace $\pi$ na n prvcích obsahuje permutaci $\rho$ na m prvcích, pokud existuje m-tice indexů $j_1 < j_2 < \ldots < j_m$ taková, že pro každé $1 \le k, l \le m$ platí $\pi(j_l) < \pi(j_k)$ právě tehdy, když $\rho(l) < \rho(k)$ .
Spočítejte počet permutací $\pi$ na n prvcích, které neobsahují $\rho = (1, 3, 2)$ . Počítají se tedy permutace takové, že pro žádné $0 < i < k < l \le n$ neplatí $\pi(i) < \pi(k) < \pi(j)$ .

Rumburak

Počet permutací f splňujících podmínku

(1) f(c) = c pro c = 1.2,3

je zřejmě (n - 3)! . Vezměme jednu takovouto permutaci f a vyjádřeme ji ve tvaru (f(1), f(2), ... , f(n)), Prvky f(1) = 1, f(2) = 2, f(3) = 3 nyní budeme
v tomto zápise "posunovat do prava" při zachování jejich vzájemného pořadí, čímž získáme z permutace f celkem x permutací g (mezi něž počítáme i f),
jejichž částí ve smyslu výše uvedené definice je permutace (1,2,3). Počet úplně všech permutací obsahujících (1,2,3) jako svoji "část" pak zřejmě bude

(2) x*(n - 3)! .

Zbývá vypočítat číslo x z výrazu (2).
Zvolme pevně permutaci f splňující (1) a vytvořme z ní výše navrženým způsobem permutaci g. V ní bude zaujímat
číslo 1 pozici i , číslo 2 pozici j , číslo 3 pozici k , přičemž 1 <= i < j < k <= n . Takže x (= počet způsobů, jak z permutace f vytvořit popsaným
způsobem perm. g) je rovno počtu prvků množiny

{ [i, i, k] element N^3 | 1 <= i < j < k <= n } ,

tj. (nevím, jak to vyjde graficky, v TEXu jsem úplný začátečník)

$x\,\,=\,\,\,\,\,\,\sum_{ 1 \le i < j < k \le n }^{}\,\,1$ .

(Později to případně ještě dopočítám, pokud to bude potřeba.)

Kondr · 06. 04. 2009 18:46

To "obsahovat permutaci" je pro zmatení nepřítele. Když si to člověk přečte selé, zjistí, že důležitá je jen ta část "počítají se tedy permutace ...". Myslím, že jich bude výrazně méně, než píše Rumburak.

nordec · 06. 04. 2009 20:59

Nešlo by vůbec nějak jednodušeji interpretovat zadání? Třeba bych se chytl.

Kondr · 06. 04. 2009 21:31

↑ nordec: Pro dané n urči počet všech permutací takových, že pro žádné $0 < i < k < l \le n$ neplatí $\pi(k) < \pi(l) < \pi(i)$ .

Rumburak

↑ Kondr:
Já Nordecovu zadání rozumím tak, že pro přípustnou permutaci f nesmějí existovat i , j, k taková, aby

i < j < k a zároveň f(i) = 1 , f(j) = 2 , f(k) = 3 .

(Nordec tam sice má "f(j) = 3 , f(k) = 2" místo "f(j) = 2 , f(k) = 3" , ale to je díky transposici zaměňující 2 za 3 myslím irrelevantní.)
Nejsem si jist, zda se v interpretaci shodujeme.

Doposud jsem vyjádřil ve tvaru x*(n-3)! počet permutací, které, pokud se nemýlím, "OBSAHUJÍ" pemutaci (1,2,3) .
Počet permutací, které ji "NEOBSAHUJÍ", bude za těchto předpokladů samozřejmě

n! - x*(n-3)!

***

Rovněž je možné přejít k inversním permutacím. Úloha pak bude vypadat (dle mého chápání) takto:
"Pro kolik permutací h platí, že konečná posloupnost (h(1), h(2), h(3)) není rostoucí ?"

Kondr · 07. 04. 2009 12:21 — Editoval Kondr (07. 04. 2009 14:34)

Vezměme n=4 a permutaci p(1)=4, p(2)=1, p(3)=3, p(4)=2. Ta podle Tebe permutaci (1,2,3) neobsahuje. Existuje ale trojice indexů
j_1=1, j_2=2 a j_3=3 taková, že p(j_i)<p(j_k), právě když r(i)<r(k), tj. právě když $(i,j)\in\{(2,3),(3,1),(2,1)}$ .

PS: to co jsem psal předtím byla blbost, spoléhal jsem na dodatek původního zadání. Už jsem to zeditoval.

A myslím, že znám odpověď: http://en.wikipedia.org/wiki/Catalan_number

Rumburak

↑ Kondr:
Děkuji za vysvětlení, opravdu jsem definici pochopil blbě. Místo abych si ji pořádně přečetl, nechal jsem se strhout vlastní představou "co by to asi mohlo znamenat". Holt poučení pro příště...

Matematické Fórum

#1 04. 04. 2009 14:45

Permutace a podpermutace či co

#2 06. 04. 2009 15:07 — Editoval Rumburak (06. 04. 2009 16:23)

Re: Permutace a podpermutace či co

#3 06. 04. 2009 18:46

Re: Permutace a podpermutace či co

#4 06. 04. 2009 20:59

Re: Permutace a podpermutace či co

#5 06. 04. 2009 21:31

Re: Permutace a podpermutace či co

#6 07. 04. 2009 09:44 — Editoval Rumburak (07. 04. 2009 11:19)

Re: Permutace a podpermutace či co

#7 07. 04. 2009 12:21 — Editoval Kondr (07. 04. 2009 14:34)

Re: Permutace a podpermutace či co

#8 07. 04. 2009 15:07 — Editoval Rumburak (07. 04. 2009 15:08)

Re: Permutace a podpermutace či co

Zápatí