Strona 1 z 1
Porównanie permutacji
: 12 sie 2020, o 00:48
autor: mol_ksiazkowy
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}\)
Re: Porównanie permutacji
: 12 sie 2020, o 08:29
autor: Premislav
Ł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.