Matematyka dyskretna, zadanie nr 1909
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
ktoslos post贸w: 3 |  2014-01-14 18:08:11Niech 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