Matematické Fórum

Optix · 20. 01. 2013 19:43 — Editoval Optix (20. 01. 2013 20:24)

Ahoj, nejak jsem se zasekl na vypoctu pevneho bodu permutace, tak opet prosim o vasi radu :)
Jedna se o ulohu kde mam zjistit urcity pocet permutaci na n-prvkove mnozine s danym poctem pevnych bodu, ja se to snazim spocitat pro dva nebo tri pevne body:
Pro dva mam vysledek takovy to
$n! - \begin{pmatrix}\\n\\1\end{pmatrix} (n-1) +$ $\begin{pmatrix}\\n\\2\end{pmatrix} (n-2)$
a pro tri je vysledek obdobny jen jsem pridal dalsi clen tedy:
$n! - \begin{pmatrix}\\n\\1\end{pmatrix} (n-1) +$ $\begin{pmatrix}\\n\\2\end{pmatrix} (n-2)-$ $\begin{pmatrix}\\n\\3\end{pmatrix} (n-3)$

Je ten vypocet spravne nebo popripade jak by mel vypadat, predem dekuji. :)

JohnPeca18 · 20. 01. 2013 22:56

No najprv si najdi funkciu bez pevného bodu, to je to čo si začal pomoci principu inkluze a exkluze. Necha P(n,m) je pocet permutaci n-prvkov s m pevnymi bodmy
potom $P(n,m)=\binom{n}{m}P(n-m,0)$ , vyberes m pevnych bodov a ostatne body permutujes bez pevneho bodu.

Bez toho pevneho bodu je to teda
$P(n,0)=n!-\sum_{i=1}^{n}\binom{n}{i}(-1)^{i+1}(n-i)!=$
$n!-\sum_{i=1}^{n}\frac{n!}{i!(n-i)!}(-1)^{i+1}(n-i)!= n!(1-\sum_{i=1}^{n}\frac{(-1)^{i+1}}{i!})=n!\sum_{i=2}^{n}\frac{(-1)^{i}}{i!}$
Takze
$P(n,m)=\binom{n}{m}(n-m)!\sum_{i=2}^{n-m}\frac{(-1)^{i}}{i!}=\frac{n!}{m!}\sum_{i=2}^{n-m}\frac{(-1)^{i}}{i!}$

Matematické Fórum

#1 20. 01. 2013 19:43 — Editoval Optix (20. 01. 2013 20:24)

Pevny bod permutace

#2 20. 01. 2013 22:56

Re: Pevny bod permutace

Zápatí