Matematyka dyskretna, zadanie nr 1909
ostatnie wiadomości | regulamin | latex
Autor | Zadanie / Rozwiązanie |
ktoslos postów: 3 | 2014-01-14 18:08:11 Niech Dn oznacza liczbę nieporządków (permutacji $\gamma$, takich, że dla każdego i$ \gamma\neq1$. Udowodnić, że $D_n=nD_{n-1} + (-1)^{n}$ |
tumor postów: 8070 | 2016-07-31 21:40:15 Istnieje wzór na liczbę nieporządków $D_n=(n-1)(D_{n-1}+D_{n-2})$ Uzasadniamy go jak następuje: Rozważmy zbiór $X=\{1,2,...,n\}$ i bijekcję $f:X\to X$. By był to nieporządek musimy mieć $f(1)\neq 1$. Wartość f(1) może być wybrana na n-1 sposobów, oznaczmy $f(1)=i$. Jeśli $f(i)=1$, to pozostaje n-2 elementów, które muszą być w nieporządku. Jeśli $f(i)\neq 1$, to redukujemy problem do n-1-elementowego. Bowiem nie może być $f(j)=j$ dla żadnego $j=2,3,...,i-1,i+1,...,n$, a także nie może być $f(i)=1$. Że $D_n=nD_{n-1}+(-1)^n$ uzasadnimy indukcyjnie. D_0=1 D_1=0 D_2=1 D_3=2 Widzimy zatem, że dla n=1,2,3 wzór obowiązuje. Załóżmy, że obowiązuje dla n-1 i dla n-2, wówczas $D_n=(n-1)(D_{n-1}+D_{n-2})=(n-1)D_{n-1}+(n-1)D_{n-2}+(-1)^{n-1}+(-1)^n=( n-1)D_{n-1}+((n-1)D_{n-2}+(-1)^{n-1})+(-1)^n= (n-1)D_{n-1}-D_{n-1}+(-1)^n=nD_{n-1}+(-1)^n$ |
strony: 1 |
Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj