logowanie

matematyka » forum » forum zadaniowe - uczelnie wyższe » zadanie

Matematyka dyskretna, zadanie nr 1909

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / 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





© 2019 Mariusz Śliwiński      o serwisie | kontakt   drukuj