Porównanie permutacji
- mol_ksiazkowy
- Użytkownik
- Posty: 11409
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
Porównanie permutacji
Niech \(\displaystyle{ D_n}\) będzie liczbą nieporządków (permutacji bez punktów stałych) zbioru \(\displaystyle{ X= \{1,..,n \}}\) zaś \(\displaystyle{ E_n}\) liczbą tych permutacji, które mają tylko jeden punkt stały. Udowodnić, że \(\displaystyle{ |D_n - E_n |=1}\)
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Porównanie permutacji
Łatwo zauważyć, że \(\displaystyle{ E_{n}=nD_{n-1}}\) – na \(\displaystyle{ n}\) sposobów wybieramy jedyny punkt stały permutacji, na \(\displaystyle{ D_{n-1}}\) sposobów mieszamy pozostałe. Ponadto mamy \(\displaystyle{ D_{n}=(n-1)\left(D_{n-1}+D_{n-2}\right)}\), co sugeruje, że zadziała tutaj prosta indukcja po \(\displaystyle{ n}\): istotnie,
dla \(\displaystyle{ n=2}\) jest \(\displaystyle{ D_{2}=1, \ E_{2}=0}\), więc rzeczywiście \(\displaystyle{ |D_{2}-E_{2}|=1}\). Przypuśćmy, że dla pewnego \(\displaystyle{ n\in \NN^{+}, \ n\ge 2}\) jest \(\displaystyle{ |D_{n}-E_{n}|=1}\), a innymi słowy, z powyższych zależności rekurencyjnych, \(\displaystyle{ |D_{n}-nD_{n-1}|=1}\). Mamy wówczas
\(\displaystyle{ |D_{n+1}-E_{n+1}|=|n(D_{n}+D_{n-1})-(n+1)D_{n}|=|nD_{n-1}-D_{n}|=|D_{n}-nD_{n-1}|=|D_{n}-E_{n}|=1}\)
c.k.d.
dla \(\displaystyle{ n=2}\) jest \(\displaystyle{ D_{2}=1, \ E_{2}=0}\), więc rzeczywiście \(\displaystyle{ |D_{2}-E_{2}|=1}\). Przypuśćmy, że dla pewnego \(\displaystyle{ n\in \NN^{+}, \ n\ge 2}\) jest \(\displaystyle{ |D_{n}-E_{n}|=1}\), a innymi słowy, z powyższych zależności rekurencyjnych, \(\displaystyle{ |D_{n}-nD_{n-1}|=1}\). Mamy wówczas
\(\displaystyle{ |D_{n+1}-E_{n+1}|=|n(D_{n}+D_{n-1})-(n+1)D_{n}|=|nD_{n-1}-D_{n}|=|D_{n}-nD_{n-1}|=|D_{n}-E_{n}|=1}\)
c.k.d.