Matematické Fórum

jirinaK · 24. 11. 2007 13:21

kolik je permutací s jedním pevným bodem? Třeba pro n=3: (v uvozovkách pevné body): "1" 2 3 & "1" 3 2 dale 1 "2" 3 & 3 "1" 2, dale 1 2 "3" & 2 1 "3" - prozatím 6, ale některé jsou tam dvakrát, takže výsledek je 4. Kolik je to ale obecně? Když obsadím jednu pozici permutace a permutuji ty zbylé, mám (n-1)! možností. pozic je tam n, takže vychází n! možností (což je nesmysl), ještě je třeba něco odečíst, nevím však, co.

No a už vůbec netuším, jak bych postupovala při výpočtu počtu permutací s "k" pevnými body. (n-k)! to asi nebude...

Kondr · 24. 11. 2007 19:16

Uvažme rovnou k pevných bodů. Možností jak vybrat z n pozic k pevných bodů je ${n\choose k}$ . Pak pro první nepevnýbod můžeme vybrat n-k-1 prvků, na které se zobrazí (nezobrazí se na žádný pevný bod a nezobrazí se na sebe). Pro další nepevný bod máme n-k-2 možností (nezobrazí se na pevné body, na sebe a na obraz prvního).
Pro dlaší máme n-k-2, ... , pro poslední 1 možnost. Celkem proto máme
${n\choose k}(n-k-1)\cdot(n-k-2)\cdots1={n\choose k}(n-k-1)!=\frac{n!}{k!(n-k)}$
možností.
To nám pro n=3 a k=1 dává 3. Kde jsi vzala 4. možnost?
(podle mě vyhoví jen 1,3,2; 3,2,1; 2,1,3; zbylé 3 mají buď 0 nebo 3 pevné body.)

talcott

to Kondr: Myslíš, že jsou naše závěry ekvivalentní? Budu o tom přemýšlet :o)
Je to tady:

- Možností jak vybrat z $n$ pozic $k$ pevných bodů je ${n\choose k}$
- Zbytek permutace, tj. permutace $n-k$ prvků musí být bez pevného bodu :
{doporučuji vyhledat problém šatnářky, kde se odvozuje počet permutací bez pevného bodu $sh(n)$ .
/např. Kapitoly z diskrétní matematiky: Matoušek, Nešetřil/.}

$sh(n-k) = (n-k)! - \frac{(n-k)!}{1!} + \frac{(n-k)!}{2!} - \frac{(n-k)!}{3!} + ... + (-1)^{n-k-1} \cdot \frac{(n-k)!}{(n-k)!}$

- Počet permutací $n$ prvků s právě $k$ pevnými body lze vyjádřit vzorcem:

$S_n^k = \frac{n!}{k!} \cdot (1 - \frac1{1!} + \frac1{2!} - \frac1{3!} + ... + (-1)^{n-k-1} \cdot \frac1{(n-k)!})$

Matematické Fórum

#1 24. 11. 2007 13:21

Pevný bod permutace

#2 24. 11. 2007 19:16

Re: Pevný bod permutace

#3 08. 12. 2007 19:11 — Editoval talcott (08. 12. 2007 19:24)

Re: Pevný bod permutace

Zápatí