Witam, mam problem ponieważ do zrobienia mam zadanie z nieporządków, a w mojej książce do kombinatoryki nic o nich nie ma. Co większa w necie też informacji mało, a jak są to zawiłe... Wiem tylko tyle, że to "permutacja bez punktów stałych", niestety sama nazwa nie wystarczy..
Zadanie:
Nieporządki - podać definicję i przykłady. Wyprowadzić wzór na liczbę nieporządków rzędu \(\displaystyle{ D_{n}}\). Obliczyć \(\displaystyle{ D_{5} \ i \ D_{6}}\).
Wzór na liczność znalazłem i prezentuje się tak:
\(\displaystyle{ \begin{cases} D_{0}=1 \ \wedge \ D_{1}=0 \\ D_{n}=(n-1)(D_{n-1}+D_{n-2}) \end{cases}}\)
EDIT:
Znalazłem przypadkowo troche informacji na wazniaku, rozwialy moje watpliwosci co do tego czym są nieporządki.. teraz chodzi mi tylko o to od czego zacząć wyprowadzanie i jak powinno wyglądac?
nieporządki / permutacje bez punktów stałych
nieporządki / permutacje bez punktów stałych
Troche sie nad tym zastanawialem, starałem się zrozumieć co łączy kolejne wartości liczby nieporządków..
*
\(\displaystyle{ \\ D_{0}=1 \\
D_{1}=0 \\
D_{2}=(2-1)(0+1)=1 \ \ \ \ \ 2!=2 \ \ \ \ \ 2 \cdot \frac{1}{2}=D_{2} \\
D_{3}=(3-1)(1+0)=2 \ \ \ \ \ 3!=6 \ \ \ \ \ 6 \cdot \frac{1}{3}=D_{3}\\
D_{4}=(4-1)(2+1)=9 \ \ \ \ \ 4!=24 \ \ \ \ \ 24 \cdot \frac{3}{8}=D_{4}\\
D_{5}=(5-1)(9+2)=44 \ \ \ \ \ 5!=120 \ \ \ \ \ 120 \cdot \frac{11}{30}=D_{5}\\
D_{6}=(6-1)(44+9)=265 \ \ \ \ \ 6!=720 \ \ \ \ \ 720 \cdot \frac{55}{144}=D_{6}\\ \\
D_{n}=n!(1- \frac{1}{1!}+ \frac{1}{2!}- \frac{1}{3!} +... \frac{1}{n!} )}\)
Tylko jak mam krok po kroku dojśc do tego wzoru?
To \(\displaystyle{ n!}\) na początku rozumiem, wychodze od niego, bo to liczba mozliwych permutacji na zbiorze n-elementowym...
Liczba permutacji bez punktow stalych jest zawsze mniejsza od liczby wszytskich mozliwych permutacji. Aby do niej dojsc, musze wiec znac wspolczynnik zgodnie z ktorym liczba ta zostanie okreslona. Jak tylko mam dojsc do tego o ile mniejsza (jak dojsc do ponizszego wspolczynnika)?
\(\displaystyle{ (1- \frac{1}{1!}+ \frac{1}{2!}- \frac{1}{3!} +... \frac{1}{n!} ) \ \ a \ wlasciwie... \\
\\ (\frac{(-1)^{0}}{0!}+\frac{(-1)^{1}}{1!}+ \frac{(-1)^{2}}{2!}+ \frac{(-1)^{3}}{3!} +... +\frac{(-1)^{n}}{n!})}\)
Tak logicznie, skad sie bierze ten wspolczynnik?
Bylbym naprawde wdzieczny za pomoc. Ten dowod moze mnie kosztowac 6 punktow ECTS, ehh..
*
\(\displaystyle{ \\ D_{0}=1 \\
D_{1}=0 \\
D_{2}=(2-1)(0+1)=1 \ \ \ \ \ 2!=2 \ \ \ \ \ 2 \cdot \frac{1}{2}=D_{2} \\
D_{3}=(3-1)(1+0)=2 \ \ \ \ \ 3!=6 \ \ \ \ \ 6 \cdot \frac{1}{3}=D_{3}\\
D_{4}=(4-1)(2+1)=9 \ \ \ \ \ 4!=24 \ \ \ \ \ 24 \cdot \frac{3}{8}=D_{4}\\
D_{5}=(5-1)(9+2)=44 \ \ \ \ \ 5!=120 \ \ \ \ \ 120 \cdot \frac{11}{30}=D_{5}\\
D_{6}=(6-1)(44+9)=265 \ \ \ \ \ 6!=720 \ \ \ \ \ 720 \cdot \frac{55}{144}=D_{6}\\ \\
D_{n}=n!(1- \frac{1}{1!}+ \frac{1}{2!}- \frac{1}{3!} +... \frac{1}{n!} )}\)
Tylko jak mam krok po kroku dojśc do tego wzoru?
To \(\displaystyle{ n!}\) na początku rozumiem, wychodze od niego, bo to liczba mozliwych permutacji na zbiorze n-elementowym...
Liczba permutacji bez punktow stalych jest zawsze mniejsza od liczby wszytskich mozliwych permutacji. Aby do niej dojsc, musze wiec znac wspolczynnik zgodnie z ktorym liczba ta zostanie okreslona. Jak tylko mam dojsc do tego o ile mniejsza (jak dojsc do ponizszego wspolczynnika)?
\(\displaystyle{ (1- \frac{1}{1!}+ \frac{1}{2!}- \frac{1}{3!} +... \frac{1}{n!} ) \ \ a \ wlasciwie... \\
\\ (\frac{(-1)^{0}}{0!}+\frac{(-1)^{1}}{1!}+ \frac{(-1)^{2}}{2!}+ \frac{(-1)^{3}}{3!} +... +\frac{(-1)^{n}}{n!})}\)
Tak logicznie, skad sie bierze ten wspolczynnik?
Bylbym naprawde wdzieczny za pomoc. Ten dowod moze mnie kosztowac 6 punktow ECTS, ehh..
-
Xitami
nieporządki / permutacje bez punktów stałych
\(\displaystyle{ \lim _{n\to \infty}\sum_{k=0}^n\frac{(-1)^k}{k!}=\frac{1}{e}}\)
Tak sobie podumam
Ile będzie takich permutacji które mają przynajmniej jeden punkt stały?
a dalej to bzdury popisałem
Tak sobie podumam
Ile będzie takich permutacji które mają przynajmniej jeden punkt stały?
a dalej to bzdury popisałem
