Matematické Fórum

SnowSlider · 05. 01. 2015 21:25

ahoj, mám za úkol zjistit počet funkcí f : $\{1,...,n\} \Rightarrow \{1,...,n\}$ pokud n $\ge$ 10 a které mají 2 až 5 pevných bodů.... napadlo mě řešit ty pevné body s pomocí pravidla inkluze a exkluze, jenže právě nevím, kolik těch funkcí je, a nedaří se mi na to přijít... neměl by prosím někdo nějaké vodítko do začátku? děkuji

vanok · 06. 01. 2015 10:22 — Editoval vanok (06. 01. 2015 12:02)

Ahoj ↑ SnowSlider:,
Bijektivne aplikacie $f: \{1,...,n\} \to \{1,...,n\}$ sa volaju permutacie na $\{1,...,n\}$ .
Mozno najprv, aby si dobre assimiloval princip metody je najprv zaujimave vyjadrit LOPATISTCKY pocet " dérangement " = permutacie bez pevnych bodov. To sa pocita postupne:
Pocet vsetkych permutacii na $\{1,...,n\}$ je n!
Opocitajme vsetki permutacie co maju aspon jeden pevny bod :-n!/1!
Priratajme tie co maju 2 aspon pevne body :+n!/2!
Odratajme tie co maju aspon 3 pevne body:n!/3! ...

V kazdej etape raz mame alternativne, veci naviac, a raz nam zasa chybaju preto to odpocitanie, priratanie....
Prides k vysledku, ze pre velke n odpoved je blizky k n!/e.

Tak to vyskusaj numericky pre n, povedzme do 20.... A potom porozmyslaj ako pokracovat v tvojom cviceni.

Matematické Fórum

#1 05. 01. 2015 21:25

počet funkcí s pevnými body

#2 06. 01. 2015 10:22 — Editoval vanok (06. 01. 2015 12:02)

Re: počet funkcí s pevnými body

Zápatí